Low-distortion Inference of Latent Similarities from a Multiplex Social Network (2012)
Ittai Abraham, Shiri Chechik, David Kempe and Aleksandrs Slivkins
It is commonly assumed that individuals tend to be more similar to their friends than to strangers. Thus, we can view an observed social network as a noisy signal about the latent underlying "social space": the way in which individuals are (dis)similar. This naturally raises the inverse question: given a social network, how accurately can we reconstruct the social space?
We begin to address this problem formally. We assume that each category (e.g., geography, profession, hobbies) is characterized by a latent metric capturing (dis)similarities in this category, and gives rise to a separate social network: a random graph parametrized by this metric. The algorithm only observes the unlabeled union of these graphs, and reconstructs each metric with provably low distortion.
Selection and influence in cultural dynamics (2012)
David Kempe, Jon Kleinberg, Sigal Oren and Aleksandrs Slivkins
One of the fundamental principles driving diversity or homogeneity in domains such as cultural differentiation, political affiliation, and product adoption is the tension between two forces: influence (the tendency of people to become similar to others they interact with) and selection (the tendency to interact with others who are already similar). Influence tends to promote homogeneity within a society, while selection frequently causes fragmentation. When both forces are in effect simultaneously, it becomes an interesting question to analyze which societal outcomes should be expected.
We analyze a natural class of models built upon active lines of work in political opinion formation, cultural diversity, and language evolution, due to Axelrod (1997), Deffuant et al. (2000) and Abrams and Strogatz (2003). Our basic model posits an arbitrary graph structure describing which "types" of people can influence one another (i.e., people are only influenced by sufficiently similar interaction partners). We achieve a complete characterization of (stable) equilibria and prove convergence from all starting states. We also obtain partial results for a more general model with a second graph structure describing which types of people can interact with one another.
The journal version includes results from:
Distributed Approaches to Triangulation and Embedding SODA 2005:
ACM-SIAM Symp. on Discrete Algorithms
We consider metric embeddings and triangulation-based distance estimation
in a distributed framework with low load on the participating nodes.
Our results provide theoretical insight into the empirical success of several recent
Internet-related projects.
The FOCS'05 version is merged with
(I.Abraham, Y.Bartal, O.Neiman).
Given any x, any metric admits a low-dim embedding
into Lp, p>=1 with disortion D(x) = O(log 1/x)
on all but an x-fraction of edges.
Moreover, any decomposable metric (e.g. any doubling metric)
admits a low-dim embedding such that
D(x) = O(log 1/x)^{1/p}
for all x.
Best Student Paper Award
(eligibility: at least one student author)
Special issue of "Distributed Computing"
Vol. 19, No. 4 (March 2007).
We approach several problems on distance estimation and object location with a unified technique called ''rings of neighbors''. Using this technique on metrics of low doubling dimension, we obtain significant improvements for low-stretch routing schemes, searchable small-world networks, distance labeling, and triangulation-based distance estimation.
Towards Fast Decentralized Construction of Locality-Aware Overlay Networks PODC 2007:
ACM Symp. on Principles of Distributed Computing
[slides]
We provide fast (polylog-time) distributed constructions for various locality-aware (low-stretch) distributed data structures, such as distance labeling schemes, name-independent routing schemes, and multicast trees.
Approximate Matching for Peer-to-Peer Overlays with Cubit (2009)
Bernard Wong, Aleksandrs Slivkins and Emin G. Sirer.
Cubit is a system that provides fully decentralized approximate keyword search capabilities to a peer-to-peer network. You can use Cubit to find a movie, song or artist even if you misspell the title or the name.
Congestion control in the Internet:
Oscillations with TCP-like Flow Control in Networks of Queues Matthew Andrews and Aleksandrs Slivkins
INFOCOM 2006
IEEE Conf. on Computer Communications
For a wide range of TCP-like fluid-based congestion control models,
we construct a network of sessions and (almost) FIFO routers such that
starting from a certain initial state, the system returns to the same
state eventually. Contrasting the prior work, in our example the total
sending rate of all sessions that come through any given router never
exceeds its capacity.
Network Failure Detection and Graph Connectivity Jon Kleinberg, Mark Sandler and Aleksandrs Slivkins.
SIAM J. on Computing, 38(4): 1330-1346, Aug 2008.
SODA 2004:
The ACM-SIAM Symp. on Discrete Algorithms
[slides]
We detect network partitions -- with strong provable guarantees -- using
a small set of 'agents' placed randomly on nodes of the network.
We parameterize our guarantees by edge- and
node-connectivity of the underlying graph.
Parameterized Tractability of Edge-Disjoint Paths on DAGs
SIAM J. on Discrete Math, 24(1): 146-157, Feb 2010.
ESA 2003:
The European Symp. on Algorithms
[slides]
We resolve a long-standing open question about the complexity of the k-edge-disjoint paths problem: we show that on DAGs it is W[1]-hard, hence unlikely to admit running time f(k)*poly(n). However, such running time can be achieved if the input+demands graph is almost Eulerian.
Online learning and its applications
We study multi-armed bandit (MAB) problems: sequential decision problems in which an algorithm repeatedly selects between a fixed set of alternatives ("arms"). We focus on MAB problems with known structure, such as similarity between arms or limited change over time.
Multi-armed Bandits in Metric Spaces Robert Kleinberg, Aleksandrs Slivkins and Eli Upfal.
STOC 2008:
ACM Symp. on Theory of Computing
We introduce the "Lipschitz MAB problem": a stochastic MAB problem, possibly with a very large set of arms, such that the expected payoffs obey a Lipschitz condition with respect to a given metric space. The goal is to minimize regret as a function of time, both in the worst case and for 'nice' problem instances.
Adapting to a Changing Environment: the Brownian Restless Bandits Aleksandrs Slivkins and Eli Upfal.
COLT 2008:
Conf. on Learning Theory.
We study a version of the stochastic MAB problem in which the expected reward of each arm evolves stochastically and gradually in time, following an independent Brownian motion or a similar process. Our benchmark is a hypothetical policy that chooses the best arm in each round.
Adapting to the Shifting Intent of Search Queries Umar Syed, Aleksandrs Slivkins and Nina Mishra
NIPS'09:
Annual Conf. on Neural Information Processing Systems
Query intent may shift over time. A classifier can use the available signals to predict a shift in intent. Then a bandit algorithm can be used to find the new relevant results. We present a meta-algorithm that combines such
classifier with a bandit algorithm in a feedback loop, with favorable regret guarantees.
Sharp Dichotomies for Regret Minimization in Metric Spaces Robert Kleinberg and Aleksandrs Slivkins
SODA 2010:
ACM-SIAM Symp. on Discrete Algorithms
We further study bandits and experts problems in metric spaces, focusing on the connections between online learning and metric topology. The main result is that the worst-case regret is either O(log t) or at least sqrt{t}, depending (essentially) on whether the metric space is countable.
Learning optimally diverse rankings over large document collections Aleksandrs Slivkins, Filip Radlinski and Sreenivas Gollapudi
ICML 2010:
Intl. Conf. on Machine Learning.
Preliminary version appeared in
NIPS 2009 Ranking Workshop.
We present a learning-to-rank framework for web search that incorporates similarity and correlation between documents and thus, unlike prior work, scales to large document collections.
Contextual bandits with similarity information COLT 2011:
Conf. on Learning Theory.
In each round nature reveals a 'context' x, algorithm chooses an 'arm' y, and the expected payoff is μ(x,y). Similarity info is given: a metric space over the (x,y) pairs such that μ is a Lipschitz function. Interpreting the current time as a part of the 'context', we obtain a very general bandit framework that includes slowly changing payoffs and variable sets of arms. The main algorithmic idea is to adapt the partitions of the metric space to frequent context arrivals and high-payoff regions.
Multi-armed bandits on implicit metric spaces NIPS 2011:
Conf. on Neural Information Processing Systems.
Suppose an MAB algorithm is given a tree-based classification of arms. This tree implicitly defines a "similarity distance" between arms, but the numeric distances are not revealed to the algorithm. Our algorithm (almost) matches the best known guarantees for the setting (Lipschitz MAB) in which the distances are revealed.
The best of both worlds: stochastic and adversarial bandits.
Sébastien Bubeck and Aleksandrs Slivkins
COLT 2012: Conf. on Learning Theory.
We present a new bandit algorithm whose regret is optimal both for adversarial rewards and for stochastic rewards, achieving, resp., square-root regret and polylog regret. Adversarial rewards and stochastic rewards are the two main settings for (non-Bayesian) multi-armed bandits; prior work treats them separately, and does not attempt to jointly optimize for both.
Algorithmic game theory
(Game-theoretic) mechanisms that learn over time.
We study settings in which the algorithmic challenges of online learning (and particularly the exploration-exploitation tradeoff) are combined with the game-theoretic challenges of interacting with self-interested agents.
Characterizing Truthful Multi-Armed Bandit Mechanisms Moshe Babaioff, Yogeshwer Sharma and Aleksandrs Slivkins
EC 2009: ACM Symp. on Electronic Commerce
We consider a natural strategic version of the MAB problem motivated by pay-per-click auctions. We show that requiring an MAB algorithm to be incentive-compatible has striking consequences both for structure and regret.
Truthful Mechanisms with Implicit Payment Computation Moshe Babaioff, Robert Kleinberg and Aleksandrs Slivkins
EC 2010: ACM Symp. on Electronic Commerce (Best paper award)
We show that creating a randomized single-parameter truthful mechanism
is essentially as easy as a single call to a monotone allocation function.
Applying this reduction to MAB mechanisms, we design truthful MAB mechanisms for stochastic payoffs.
Monotone multi-armed bandit allocations Open Question at COLT 2011:
Conf. on Learning Theory.
The reduction in the EC'10 paper opens up a problem of designing monotone (regret-minimizing) MAB allocation rules, a new twist on the familiar multi-armed bandit problem.
Dynamic pricing with limited supply Moshe Babaioff, Shaddin Dughmi, Robert Kleinberg and Aleksandrs Slivkins
EC 2012: ACM Symp. on Electronic Commerce Preliminary version appeared in WBMD 2011 (a workshop at ACM EC 2011).
We consider dynamic pricing with limited supply and unknown demand distribution.
We extend multi-armed bandit techniques to the limited supply setting, and obtain optimal regret rates.
