The stochastic multi-armed bandit model captures the tradeoff between exploration and exploitation. We study the effects of competition and cooperation on this tradeoff. Suppose there are two arms, one predictable and one risky, and two players, Alice and Bob. In every round, each player pulls an arm, receives the resulting reward, and observes the choice of the other player but not their reward. Alice’s utility is $\Gamma_A + \lambda \Gamma_B$ (and similarly for Bob), where $\Gamma_A$ is Alice’s total reward and $\lambda \in [-1, 1]$ is a cooperation parameter. At $\lambda = -1$ the players are competing in a zero-sum game, at $\lambda = 1$, their interests are aligned, and at $\lambda = 0$, they are neutral: each player’s utility is their own reward. The model is related to the economics literature on strategic experimentation, where usually players observe each other’s rewards. Suppose the predictable arm has success probability $p$ and the risky arm has prior $\mu$. If the discount factor is $\beta$, then the value of $p$ where a single player is indifferent between the arms is the Gittins index $g = g(\mu,\beta) > m$, where $m$ is the mean of the risky arm. Our first result answers, in this setting, a fundamental question posed by Rothschild \cite{rotschild}. We show that competing and neutral players eventually settle on the same arm (even though it may not be the best arm) in every Nash equilibrium, while this can fail for players with aligned interests. Moreover, we show that \emph{competing players} explore \emph{less} than a single player: there is $p^* \in (m, g)$ so that for all $p > p^*$, the players stay at the predictable arm. However, the players are not myopic: they still explore for some $p > m$. On the other hand, \emph{cooperating players} (with $\lambda =1$) explore \emph{more} than a single player. We also show that \emph{neutral players} learn from each other, receiving strictly higher total rewards than they would playing alone, for all $ p\in (p^*, g)$, where $p^*$ is the threshold above which competing players do not explore.

We study the stabilization of a linear control system with an unbounded random system gain where the controller must act based on a rate-limited observation of the state. More precisely, we consider the system Xn+1=AnXn+Wn-Un, where the An's are drawn independently at random at each time n from a known distribution with unbounded support, and where the controller receives at most R bits about the system state at each time from an encoder. We provide a time-varying achievable strategy to stabilize the system in a second-moment sense with fixed, finite R. While our previous result provided a strategy to stabilize this system using a variable-rate code, this work provides an achievable strategy using a fixed-rate code. The strategy we employ to achieve this is time-varying and takes different actions depending on the value of the state. It proceeds in two modes: a normal mode (or zoom-in), where the realization of Anis typical, and an emergency mode (or zoom-out), where the realization of Anis exceptionally large. To analyze the performance of the scheme we construct an auxiliary sequence that bounds the state Xn, and then bound auxiliary sequence in both the zoom-in and zoom-out modes.

We consider the non-stochastic version of the (cooperative) multi-player multi-armed bandit problem. The model assumes no communication and no shared randomness at all between the players, and furthermore when two (or more) players select the same action this results in a maximal loss. We prove the first $\sqrt{T}$-type regret guarantee for this problem, assuming only two players, and under the feedback model where collisions are announced to the colliding players. We also prove the first sublinear regret guarantee for the feedback model where collision information is not available, namely $T^{1-\frac{1}{2m}}$ where $m$ is the number of players.

Recall the classical hypothesis testing setting with two sets of probability distributions P and Q. One receives either n i.i.d. samples from a distribution p E P or from a distribution q E Q and wants to decide from which set the points were sampled. It is known that the optimal exponential rate at which errors decrease can be achieved by a simple maximum-likelihood ratio test which does not depend on p or q, but only on the sets P and Q. We consider an adaptive generalization of this model where the choice of p E P and q E Q can change in each sample in some way that depends arbitrarily on the previous samples. In other words, in the kth round, an adversary, having observed all the previous samples in rounds 1, . . . , k - 1, chooses pk E P and qk E Q, with the goal of confusing the hypothesis test. We prove that even in this case, the optimal exponential error rate can be achieved by a simple maximum-likelihood test that depends only on P and Q. We then show that the adversarial model has applications in hypothesis testing for quantum states using restricted measurements. For example, it can be used to study the problem of distinguishing entangled states from the set of all separable states using only measurements that can be implemented with local operations and classical communication (LOCC). The basic idea is that in our setup, the deleterious effects of entanglement can be simulated by an adaptive classical adversary. We prove a quantum Stein's Lemma in this setting: In many circumstances, the optimal hypothesis testing rate is equal to an appropriate notion of quantum relative entropy between two states. In particular, our arguments yield an alternate proof of Li and Winter's recent strengthening of strong subadditivity for von Neumann entropy.

We consider the sorted top-$k$ problem whose goal is to recover the top-$k$ items with the correct order out of $n$ items using pairwise comparisons. In many applications, multiple rounds of interaction can be costly. We restrict our attention to algorithms with a constant number of rounds $r$ and try to minimize the sample complexity, i.e. the number of comparisons. When the comparisons are noiseless, we characterize how the optimal sample complexity depends on the number of rounds (up to a polylogarithmic factor for general $r$ and up to a constant factor for $r=1$ or 2). In particular, the sample complexity is $\Theta(n^2)$ for $r=1$, $\Theta(n\sqrt{k} + n^{4/3})$ for $r=2$ and $\tilde{\Theta}\left(n^{2/r} k^{(r-1)/r} + n\right)$ for $r \geq 3$. We extend our results of sorted top-$k$ to the noisy case where each comparison is correct with probability $2/3$. When $r=1$ or 2, we show that the sample complexity gets an extra $\Theta(\log(k))$ factor when we transition from the noiseless case to the noisy case. We also prove new results for top-$k$ and sorting in the noisy case. We believe our techniques can be generally useful for understanding the trade-off between round complexities and sample complexities of rank aggregation problems.

From traditional Web search engines to virtual assistants and Web accelerators, services that rely on online information need to continually keep track of remote content changes by explicitly requesting content updates from remote sources (e.g., web pages). We propose a novel optimization objective for this setting that has several practically desirable properties, and efficient algorithms for it with optimality guarantees even in the face of mixed content change observability and initially unknown change model parameters. Experiments on 18.5M URLs crawled daily for 14 weeks show significant advantages of this approach over prior art.

A Web crawler is an essential part of a search engine that procures information subsequently served by the search engine to its users. As the Web is becoming increasingly more dynamic, in addition to discovering new web pages a crawler needs to keep revisiting those already in the search engine's index, in order to keep the index fresh by picking up the pages' changed content. Determining how often to recrawl pages requires making tradeoffs based on the pages' relative importance and change rates, subject to multiple resource constraints - the limited daily budget of crawl requests on the search engine's end and politeness constraints restricting the rate at which pages can be requested from a given host. In this paper, we introduce PoliteBinaryLambdaCrawl, the first optimal algorithm for freshness crawl scheduling in the presence of politeness constraints as well as non-uniform page importance scores and the crawler's own crawl request limit. We also propose an approximation for it, stating its theoretical optimality conditions and in the process discovering a connection to an approach previously thought of as a mere heuristic for freshness crawl scheduling. We explore the relative performance of PoliteBinaryLambdaCrawl and other methods for handling politeness constraints on a dataset collected by crawling over 18.5M URLs daily over 14 weeks.

The deletion-insertion channel takes as input a bit string ${\bf x}\in \{0,1\}^{n}$, and outputs a string where bits have been deleted and inserted independently at random. The trace reconstruction problem is to recover $\bf x$ from many independent outputs (called “traces”) of the deletion-insertion channel applied to $\bf x$. We show that if $\bf x$ is chosen uniformly at random, then $\exp(O(\log^{1/3} n))$ traces suffice to reconstruct $\bf x$ with high probability. For the deletion channel with deletion probability $q<1/2$ the earlier upper bound was $\exp(O(\log^{1/2} n))$. The case of $q\geq 1/2$ or the case where insertions are allowed has not been previously analysed, and therefore the earlier upper bound was as for worst-case strings, i.e., $\exp(O( n^{1/3}))$. A key ingredient in our proof is a delicate two-step alignment procedure where we estimate the location in each trace corresponding to a given bit of $\bf x$. The alignment is done by viewing the strings as random walks, and comparing the increments in the walk associated with the input string and the trace, respectively.

We consider the problem of testing graph cluster structure: given access to a graph G = (V, E), can we quickly determine whether the graph can be partitioned into a few clusters with good inner conductance, or is far from any such graph? This is a generalization of the well-studied problem of testing graph expansion, where one wants to distinguish between the graph having good expansion (i.e. being a good single cluster) and the graph having a sparse cut (i.e. being a union of at least two clusters). A recent work of Czumaj, Peng, and Sohler (STOC'15) gave an ingenious sublinear time algorithm for testing k-clusterability in time Õ(n^1/2 poly(k)). Their algorithm implicitly embeds a random sample of vertices of the graph into Euclidean space, and then clusters the samples based on estimates of Euclidean distances between the points. This yields a very efficient testing algorithm, but only works if the cluster structure is very strong: it is necessary to assume that the gap between conductances of accepted and rejected graphs is at least logarithmic in the size of the graph G. In this paper we show how one can leverage more refined geometric information, namely angles as opposed to distances, to obtain a sublinear time tester that works even when the gap is a sufficiently large constant. Our tester is based on the singular value decomposition of a natural matrix derived from random walk transition probabilities from a small sample of seed nodes. We complement our algorithm with a matching lower bound on the query complexity of testing clusterability. Our lower bound is based on a novel property testing problem, which we analyze using Fourier analytic tools. As a byproduct of our techniques, we also achieve new lower bounds for the problem of approximating MAX-CUT value in sublinear time.

We study the stabilization of an unpredictable linear control system where the controller must act based on a rate-limited observation of the state. More precisely, we consider the system X_(n+1) = A_n X_n +W_n –U_n, where the A_n's are drawn independently at random at each time n from a known distribution with unbounded support, and where the controller receives at most R bits about the system state at each time from an encoder. We provide a time-varying achievable strategy to stabilize the system in a second-moment sense with fixed, finite R. While our previous result provided a strategy to stabilize this system using a variable-rate code, this work provides an achievable strategy using a fixed-rate code. The strategy we employ to achieve this is time-varying and takes different actions depending on the value of the state. It proceeds in two modes: a normal mode (or zoom-in), where the realization of A_n is typical, and an emergency mode (or zoom-out), where the realization of A_n is exceptionally large.

Il est naturel de s’attendre à ce que la marche aléatoire sans rebroussement mélange plus vite que la marche aléatoire simple, mais jusqu’ici, cela n’était prouvé que dans le cas des graphes réguliers. Pour analyser le cas de graphes irréguliers typiques, soit $G$ un graphe aléatoire à $n$ sommets de degrés au moins $3$ et distribués selon une loi à queue exponentielle. On détermine le temps de mélange partant du pire point de départ pour la marche aléatoire simple sur $G$, et l’on montre qu’avec grande probabilité, cette marche présente le phénomène de cutoff au temps ${\mathbf{h}}^{-1}\log n$, où ${\mathbf{h}}$ est l’entropie asymptotique de la marche aléatoire simple sur un arbre de Galton–Watson qui est une approximation locale de $G$. (Précédemment, cela n’était connu que pour des points de départ typiques.) De plus, on montre que ce temps de mélange est strictement plus grand que celui de la marche aléatoire sans rebroussement, via une comparison délicate des entropies sur l’arbre de Galton–Watson.

In this paper we discuss the problem of estimating graph parameters from a random walk with restarts. In this setting, an algorithm observes the trajectory of a random walk over an unknown graph G, starting from a vertex x. The algorithm also sees the degrees along the trajectory. The only other power that the algorithm has is to request that the random walk be reset to its initial state at any given time, based on what it has seen so far. Our main results are as follows. For regular graphs G, one can estimate the number of vertices nG and the ℓ2 mixing time of G from x in steps, where is the uniform mixing time of the random walk on G. The algorithm is based on the number of intersections of random walk paths X, Y, ie. the number of times (t, s) such that Xt = Ys. Our method improves on previous methods by various authors which only consider collisions (ie. times t with Xt = Yt). We also show that the time complexity of our algorithm is optimal (up to log factors) for 3-regular graphs with prescribed mixing times. For general graphs, we adapt the intersections algorithm to compute the number of edges mG and the ℓ2 mixing time from the starting vertex x in steps. Under mild additional assumptions (which hold e.g. for sparse graphs) the number of vertices can also be estimated by this time. Finally, we show that these algorithms, which may take sublinear time, have a fundamental limitation: it is not possible to devise a sublinear stopping time at which one can be reasonably sure that our parameters are well estimated. On the other hand, we show that, given either ma or the mixing time of G, we can compute the “other parameter” with a self-stopping algorithm.

La dynamique de Swendsen–Wang a été proposée à la fin des années 1980 comme une alternative à la dynamique du bain-de-chaleur à un site, dans laquelle des mises à jour globales permettent à cet algorithme MCMC de passer plus vite d’un état métastable à un état de mélange idéal. Gore et Jerrum (J. Stat. Phys. 97 (1999) 67–86) ont trouvé que cette dynamique peut en fait montrer un mélange lent: ils ont montré, pour le modèle de Potts à $q\geq 3$ couleurs sur le graphe complet sur $n$ sommets au point critique $\beta_{c}(q)$, que la dynamique de Swendsen–Wang vérifie $t_{\mathrm{mix}}\geq \exp(c\sqrt{n})$. Galanis et al. (In Proc. of the 19th International Workshop on Randomization and Computation (RANDOM 2015) (2015) 815–828) a montré que $t_{\mathrm{mix}}\geq \exp(cn^{1/3})$ dans toute la fenêtre critique $(\beta_{s},\beta_{S})$ autour de $\beta_{c}$, et Blanca et Sinclair (In Proc. of the 19th International Workshop on Randomization and Computation (RANDOM 2015) (2015) 528–543) ont établit que $t_{\mathrm{mix}}\geq \exp(c\sqrt{n})$ dans la fenêtre critique pour le modèle de champs moyen FK, ce qui implique la même borne pour Swendsen–Wang grâce des estimées de comparaison connues. Dans les deux cas, une borne supérieure de $t_{\mathrm{mix}}\leq \exp(c'n)$ était connue. Dans cet article, nous montrons que le temps de mélange est vraiment exponentiel en $n$: plus précisément, $t_{\mathrm{mix}}\geq \exp (cn)$ pour la dynamique de Swendsen–Wang quand $q\geq 3$ et $\beta\in(\beta_{s},\beta_{S})$, et la même borne est vraie pour l’algorithme MCMC associé pour le modèle de champs moyen FK quand $q>2$.

Let $X$ be a lazy random walk on a graph $G$. If $G$ is undirected, then the mixing time is upper bounded by the maximum hitting time of the graph. This fails for directed chains, as the biased random walk on the cycle $\mathbb{Z}_n$ shows. However, we establish that for Eulerian digraphs, the mixing time is $O(mn)$, where $m$ is the number of edges and $n$ is the number of vertices. In the reversible case, the mixing time is robust to the change of the laziness parameter. Surprisingly, in the directed setting the mixing time can be sensitive to such changes. We also study exploration and cover times for random walks on Eulerian digraphs and prove universal upper bounds in analogy to the undirected case.

Starting from a unit mass on a vertex of a graph, we investigate the minimum number of controlled diffusion steps needed to transport a constant mass $p$ outside of the ball of radius $n$. In a step of a controlled diffusion process we may select any vertex with positive mass and topple its mass equally to its neighbors. Our initial motivation comes from the maximum overhang question in one dimension, but the more general case arises from optimal mass transport problems. On $\mathbb{Z}^{d}$ we show that $\Theta( n^{d+2} )$ steps are necessary and sufficient to transport the mass. We also give sharp bounds on the comb graph and $d$-ary trees. Furthermore, we consider graphs where a simple random walk has positive speed and entropy and which satisfy Shannon's theorem, and show that the minimum number of controlled diffusion steps is $\exp{( n \cdot h / \ell ( 1 + o(1) ) )}$, where $h$ is the Avez asymptotic entropy and $\ell$ is the speed of a random walk. As examples, we give precise results on Galton--Watson trees and the product of trees $\mathbb{T}_d \times \mathbb{T}_k$.

For a rumor spreading protocol, the spread time is defined as the first time that everyone learns the rumor. We compare the synchronous push&pull rumor spreading protocol with its asynchronous variant, and show that for any n-vertex graph and any starting vertex, the ratio between their expected spread times is bounded by O(n^{1/3} log^{2/3} n). This improves the O(sqrt n) upper bound of Giakkoupis, Nazari, and Woelfel (in Proceedings of ACM Symposium on Principles of Distributed Computing, 2016). Our bound is tight up to a factor of O(log n), as illustrated by the string of diamonds graph.

We consider the random walk on the hypercube which moves by picking an ordered pair (i,j) of distinct coordinates uniformly at random and adding the bit at location i to the bit at location j, modulo 2. We show that this Markov chain has cutoff at time (3/2)n*log(n) with window of size n, solving a question posed by Chung and Graham (1997).

The deletion channel takes as input a bit string x ∈ {0, 1}n, and deletes each bit independently with probability q, yielding a shorter string. The trace reconstruction problem is to recover an unknown string x from many independent outputs (called “traces”) of the deletion channel applied to x. We show that if x is drawn uniformly at random and qO(log1/2 n)traces suffice to reconstruct x with high probability. The previous best bound, established in 2008 by Holenstein, Mitzenmacher, Panigrahy, and Wieder [1], uses nO(1)traces and only applies for q less than a smaller threshold (it seems that q <; 0.07 is needed). Our algorithm combines several ideas: 1) an alignment scheme for “greedily” fitting the output of the deletion channel as a subsequence of the input; 2) a version of the idea of “anchoring” used in [1]; and 3) complex analysis techniques from recent work of Nazarov and Peres [2] and De, O'Donnell, and Servedio [3].

We study the fundamental problem of prediction with expert advice and develop regret lower bounds for a large family of algorithms for this problem. We develop simple adversarial primitives, that lend themselves to various combinations leading to sharp lower bounds for many algorithmic families. We use these primitives to show that the classic Multiplicative Weights Algorithm (MWA) has a regret of (T*ln(k)/2)^{0.5} (where T is the time horizon and k is the number of experts), there by completely closing the gap between upper and lower bounds. We further show a regret lower bound of (2/3)* (T*ln(k)/2)^{0.5} for a much more general family of algorithms than MWA, where the learning rate can be arbitrarily varied over time, or even picked from arbitrary distributions over time. We also use our primitives to construct adversaries in the geometric horizon setting for MWA to precisely characterize the regret at 0.391/(\delta)^{0.5} for the case of 2 experts and a lower bound of (1/2)*(ln(k)/(2*\delta))^{0.5}, for the case of arbitrary number of experts k (here \delta is the probability that the game ends in any given round).

We present a Gaussian random walk in a polytope that starts at a point inside and continues until it gets absorbed at a vertex. Our main result is that the probability distribution induced on the vertices by this random walk has strong negative dependence properties for matroid polytopes. Such distributions are highly sought after in randomized algorithms as they imply concentration properties. Our random walk is simple to implement, computationally efficient and can be viewed as an algorithm to round the starting point in an unbiased manner. The proof relies on a simple inductive argument that synthesizes the combinatorial structure of matroid polytopes with the geometric structure of multivariate Gaussian distributions. Our result not only implies a long line of past results in a unified and transparent manner, but also implies new results about constructing negatively associated distributions for all matroids.

In 1988, Johnson, Papadimitriou and Yannakakis wrote that "Practically all the empirical evidence would lead us to conclude that finding locally optimal solutions is much easier than solving NP-hard problems". Since then the empirical evidence has continued to amass, but formal proofs of this phenomenon have remained elusive. A canonical (and indeed complete) example is the local max-cut problem, for which no polynomial time method is known. In a breakthrough paper, Etscheid and Röglin proved that the smoothed complexity of local max-cut is quasi-polynomial, i.e., if arbitrary bounded weights are randomly perturbed, a local maximum can be found in ϕ nO(logn) steps where ϕ is an upper bound on the random edge weight density. In this paper we prove smoothed polynomial complexity for local max-cut, thus confirming that finding local optima for max-cut is much easier than solving it.

In the trace reconstruction problem, an unknown bit string x ∈ {0,1}n is observed through the deletion channel, which deletes each bit of x with some constant probability q, yielding a contracted string x. How many independent copies of x are needed to reconstruct x with high probability? Prior to this work, the best upper bound, due to Holenstein, Mitzenmacher, Panigrahy, and Wieder (2008), was exp(O(n1/2)). We improve this bound to exp(O(n1/3)) using statistics of individual bits in the output and show that this bound is sharp in the restricted model where this is the only information used. Our method, that uses elementary complex analysis, can also handle insertions. Similar results were obtained independently and simultaneously by Anindya De, Ryan O'Donnell and Rocco Servedio.

This paper considers the stabilization of an unstable discrete-time linear system that is observed over a channel corrupted by continuous multiplicative noise. The main result is a converse bound that shows that if the system growth is large enough the system cannot be stabilized in a mean-squared sense. This is done by showing that the probability of the state magnitude remains bounded must go to zero with time. It was known that a system with multiplicative observation noise can be stabilized using a simple linear strategy if the system growth is suitably bounded. However, it was not clear whether non-linear controllers could overcome arbitrarily large growth factors. One difficulty with using the standard approach for a data-rate theorem style converse is that the mutual information per round between the system state and the observation is potentially unbounded with a multiplicative noise observation channel. Our proof technique recursively bounds the conditional density of the system state (instead of focusing on the second moment) to bound the progress the controller can make.

We study the classical problem of prediction with expert advice in the adversarial setting with a geometric stopping time. In 1965, Cover gave the optimal algorithm for the case of 2 experts. In this paper, we design the optimal algorithm, adversary and regret for the case of 3 experts. Further, we show that the optimal algorithm for 2 and 3 experts is a probability matching algorithm (analogous to Thompson sampling) against a particular randomized adversary. Remarkably, our proof shows that the probability matching algorithm is not only optimal against this particular randomized adversary, but also minimax optimal. Our analysis develops upper and lower bounds simultaneously, analogous to the primal-dual method. Our analysis of the optimal adversary goes through delicate asymptotics of the random walk of a particle between multiple walls. We use the connection we develop to random walks to derive an improved algorithm and regret bound for the case of 4 experts, and, provide a general framework for designing the optimal algorithm and adversary for an arbitrary number of experts.

Spectral partitioning is a simple, nearly linear time algorithm to find sparse cuts, and the Cheeger inequalities provide a worst-case guarantee for the quality of the approximation found by the algorithm. A local graph partitioning algorithm finds a set of vertices with small conductance (i.e., a sparse cut) by adaptively exploring part of a large graph G , starting from a specified vertex. For the algorithm to be local, its complexity must be bounded in terms of the size of the set that it outputs, with at most a weak dependence on the number n of vertices in G . Previous local partitioning algorithms find sparse cuts using random walks and personalized PageRank [Spielman and Teng 2013; Andersen et al. 2006]. In this article, we introduce a simple randomized local partitioning algorithm that finds a sparse cut by simulating the volume-biased evolving set process , which is a Markov chain on sets of vertices. We prove that for any ϵ > 0, and any set of vertices A that has conductance at most φ, for at least half of the starting vertices in A our algorithm will output (with constant probability) a set of conductance O (√φ /ϵ). We prove that for a given run of the algorithm, the expected ratio between its computational complexity and the volume of the set that it outputs is vol( A ) ϵ φ -1/2 polylog( n ), where vol( A ) = Σ v ∈ A d ( v ) is the volume of the set A . This gives an algorithm with the same guarantee (up to a constant factor) as the Cheeger's inequality that runs in time slightly superlinear in the size of the output. This is the first sublinear (in the size of the input) time algorithm with almost the same guarantee as the Cheeger's inequality. In comparison, the best previous local partitioning algorithm, by Andersen et al. [2006], has a worse approximation guarantee of O (√φ log n ) and a larger ratio of φ -1 polylog( n ) between the complexity and output volume. As a by-product of our results, we prove a bicriteria approximation algorithm for the expansion profile of any graph. For 0 < k ≤ vol( V )/2, let φ( k ) : min S : vol( S ) ≤ k φ( S ). There is a polynomial time algorithm that, for any k , ϵ > 0, finds a set S of volume vol( S ) ≤ O ( k 1 + ϵ ) and expansion φ( S )≤ O (√φ ( k )/ϵ). As a new technical tool, we show that for any set S of vertices of a graph, a lazy t -step random walk started from a randomly chosen vertex of S will remain entirely inside S with probability at least (1 - φ( S )/2) t . This itself provides a new lower bound to the uniform mixing time of any finite state reversible Markov chain.

We analyze the minimax regret of the adversarial bandit convex optimization problem. Focusing on the one-dimensional case, we prove that the minimax regret is \widetildeΘ(\sqrtT) and partially resolve a decade-old open problem. Our analysis is non-constructive, as we do not present a concrete algorithm that attains this regret rate. Instead, we use minimax duality to reduce the problem to a Bayesian setting, where the convex loss functions are drawn from a worst-case distribution, and then we solve the Bayesian version of the problem with a variant of Thompson Sampling. Our analysis features a novel use of convexity, formalized as a “local-to-global” property of convex functions, that may be of independent interest.

The growing need for labeled training data has made crowdsourcing an important part of machine learning. The quality of crowdsourced labels is, however, adversely affected by three factors: (1) the workers are not experts; (2) the incentives of the workers are not aligned with those of the requesters; and (3) the interface does not allow workers to convey their knowledge accurately, by forcing them to make a single choice among a set of options. In this paper, we address these issues by introducing approval voting to utilize the expertise of workers who have partial knowledge of the true answer, and coupling it with a ("strictly proper") incentive-compatible compensation mechanism. We show rigorous theoretical guarantees of optimality of our mechanism together with a simple axiomatic characterization. We also conduct preliminary empirical studies on Amazon Mechanical Turk which validate our approach.

A sequence of Markov chains is said to exhibit (total variation) cutoff if the convergence to stationarity in total variation distance is abrupt. We consider reversible lazy chains. We prove a necessary and sufficient condition for the occurrence of the cutoff phenomena in terms of concentration of hitting time of “worst” (in some sense) sets of stationary measure at least α, for some α ∊ (0,1). We also give general bounds on the total variation distance of a reversible chain at time t in terms of the probability that some “worst” set of stationary measure at least α was not hit by time t. As an application of our techniques we show that a sequence of lazy Markov chains on finite trees exhibits a cutoff iff the product of their spectral gaps and their (lazy) mixing-times tends to ∞.

A special case of Myerson's classic result describes the revenue-optimal equilibrium when a seller offers a single item to a buyer. We study a natural repeated sales extension of this model: a seller offers to sell a single fresh copy of an item to the same buyer every day via a posted price. The buyer's value for the item is unknown to the seller but is drawn initially from a publicly known distribution F and remains the same throughout. One key aspect of this game is revelation of the buyer's type through his actions: while the seller might try to learn this value to extract more revenue, the buyer is motivated to hide it to induce lower prices. If the seller is able to commit to future prices, then it is known that the best he can do is extract the Myerson optimal revenue each day. In a more realistic scenario, the seller is unable to commit and must play a perfect Bayesian equilibrium. It is known that not committing to future prices does not help the seller. Thus extracting Myerson optimal revenue each day is a natural upper bound and revenue benchmark in a setting without commitment. We study this setting without commitment and find several suprises. First, if the horizon is fixed, previous work showed that an equilibrium always exists, and all equilibria yield a very low revenue, often times only a constant amount of revenue. This is unintuitive and a far cry from the linearly growing benchmark of obtaining Myerson optimal revenue each day. Our first result shows that this is because the buyer strategies in these equilibria are necessarily unnatural. We restrict to a natural class of buyer strategies, which we call threshold strategies, and show that pure strategy threshold equilibria rarely exist. This offers an explanation for the non-prevalence of bizarre outcomes predicted by previous results. Second, if the seller can commit not to raise prices upon purchase, while still retaining the possibility of lowering prices in future, we recover the natural threshold equilibria by showing that they exist for a large class of distributions including the power law family of distributions. As an example, if the distribution F is uniform in [0,1], the seller can extract revenue of order in n rounds as opposed to the constant revenue obtainable when he is unable to make any commitments. Finally, we consider the infinite horizon game with partial commitment, where both the seller and the buyer discount the future utility by a factor of 1 – δ ∊ [0,1). When the value distribution is uniform in [0, 1], there exists a threshold equilibrium with expected revenue at least of the Myerson optimal revenue benchmark. Under some mild assumptions, this equilibrium is also unique.

In a Markov chain started at a state x, the hitting time τ(y) is the first time that the chain reaches another state y. We study the probability Px(τ(y) = t) that the first visit to y occurs precisely at a given time t. Informally speaking, the event that a new state is visited at a large time t may be considered a “surprise”. We prove the following three bounds: In any Markov chain with n states, In a reversible chain with n states, For random walk on a simple graph with n ≥ 2 vertices, We construct examples showing that these bounds are close to optimal. The main feature of our bounds is that they require very little knowledge of the structure of the Markov chain. To prove the bound for random walk on graphs, we establish the following estimate conjectured by Aldous, Ding and Oveis-Gharan (private communication): For random walk on an n-vertex graph, for every initial vertex x,

We study a new class of online learning problems where each of the online algorithm’s actions is assigned an adversarial value, and the loss of the algorithm at each step is a known and deterministic function of the values assigned to its recent actions. This class includes problems where the algorithm’s loss is the \emphminimum over the recent adversarial values, the \emphmaximum over the recent values, or a \emphlinear combination of the recent values. We analyze the minimax regret of this class of problems when the algorithm receives bandit feedback, and prove that when the \emphminimum or \emphmaximum functions are used, the minimax regret is \widetilde Ω(T^2/3) (so called \emphhard online learning problems), and when a linear function is used, the minimax regret is \widetilde O(\sqrtT) (so called \empheasy learning problems). Previously, the only online learning problem that was known to be provably hard was the multi-armed bandit with switching costs.

Recall the classical hypothesis testing setting with two convex sets of probability distributions P and Q. One receives either n i.i.d. samples from a distribution p ∈ P or from a distribution q ∈ Q and wants to decide from which set the points were sampled. It is known that the optimal exponential rate at which errors decrease can be achieved by a simple maximum-likelihood ratio test which does not depend on p or q, but only on the sets P and Q.

We study the adversarial multi-armed bandit problem in a setting where the player incurs a unit cost each time he switches actions. We prove that the player's T-round minimax regret in this setting is [EQUATION], thereby closing a fundamental gap in our understanding of learning with bandit feedback. In the corresponding full-information version of the problem, the minimax regret is known to grow at a much slower rate of Θ(√T). The difference between these two rates provides the first indication that learning with bandit feedback can be significantly harder than learning with full information feedback (previous results only showed a different dependence on the number of actions, but not on T.)

Consider a random regular graph with degree $d$ and of size $n$. Assign to each edge an independent and identically distributed exponential random variable with mean one. In this paper we establish a precise asymptotic expression for the maximum number of edges on the shortest-weight paths between a fixed vertex and all the other vertices, as well as between any pair of vertices. Namely, for any fixed $d \geq 3$, we show that the longest of these shortest-weight paths has about $\widehat{\alpha} \log n$ edges, where $\widehat{\alpha} $ is the unique solution of the equation $\alpha \log\big(\frac{d-2}{d-1}\alpha\big) - \alpha = \frac{d-3}{d-2}$ for $\alpha > \frac{d-1}{d-2}$.

Rotor walk is a deterministic analogue of random walk. We study its recurrence and transience properties on ${\mathbb Z}^d$ for the initial configuration of all rotors aligned. If $n$ particles in turn perform rotor walks starting from the origin, we show that the number that escape (i.e., never return to the origin) is of order $n$ in dimensions $d \geq 3$ and of order $n/\log n$ in dimension $2$.

We present an all-pairs shortest path algorithm whose running time on a complete directed graph on n vertices whose edge weights are chosen independently and uniformly at random from [0,1] is O ( n 2 ), in expectation and with high probability. This resolves a long-standing open problem. The algorithm is a variant of the dynamic all-pairs shortest paths algorithm of Demetrescu and Italiano [2006]. The analysis relies on a proof that the number of locally shortest paths in such randomly weighted graphs is O ( n 2 ), in expectation and with high probability. We also present a dynamic version of the algorithm that recomputes all shortest paths after a random edge update in O (log 2 n ) expected time.

We consider the problem of online sublinear expander reconstruction and its relation to random walks in “noisy" expanders. Given access to an adjacency list representation of a bounded-degree graph $G$, we want to convert this graph into a bounded-degree expander $G'$ changing $G$ as little as possible. The graph $G'$ will be output by a distributed filter: this is a sublinear time procedure that, given a query vertex, outputs all its neighbors in $G'$ and can do so even in a distributed manner, ensuring consistency in all the answers. One of the main tools in our analysis is a result on the behavior of random walks in graph that are almost expanders: graphs that are formed by arbitrarily connecting a small unknown graph (the noise) to a large expander. We show that a random walk from almost any vertex in the expander part will have fast mixing properties, in the general setting of irreducible finite Markov chains. We also design sublinear time procedures to distinguish vertices of the expander part from those in the noise part and use this procedure in the reconstruction algorithm.

The time it takes a random walker in a lattice to reach the origin from another vertex x has infinite mean. If the walker can restart the walk at x at will, then the minimum expected hitting time $\gamma(x,0)$ (minimized over restarting strategies) is finite; it was called the “grade” of x by Dumitriu, Tetali, and Winkler. They showed that in a more general setting, the grade (a variant of the “Gittins index”) plays a crucial role in control problems involving several Markov chains. Here we establish several conjectures of Dumitriu, Tetali, and Winkler on the asymptotics of the grade in Euclidean lattices. In particular, we show that in the planar square lattice, $\gamma(x,0)$ is asymptotic to $2|x|^2\log|x|$ as $|x| \to \infty$. The proof hinges on the local variance of the potential kernel h being almost constant on the level sets of h. We also show how the same method yields precise second order asymptotics for hitting times of a random walk (without restarts) in a lattice disk.

Static wireless networks are by now quite well understood mathematically through the random geometric graph model. By contrast, there are relatively few rigorous results on the practically important case of mobile networks. In this paper we consider a natural extension of the random geometric graph model to the mobile setting by allowing nodes to move in space according to Brownian motion. We study three fundamental questions in this model: detection (the time until a given target point—which may be either fixed or moving—is detected by the network), coverage (the time until all points inside a finite box are detected by the network), and percolation (the time until a given node is able to communicate with the giant component of the network). We derive precise asymptotics for these problems by combining ideas from stochastic geometry, coupling and multi-scale analysis. We also give an application of our results to analyze the time to broadcast a message in a mobile network.

We exhibit a strong connection between cover times of graphs, Gaussian processes, and Talagrand's theory of majorizing measures. In particular, we show that the cover time of any graph G is equivalent, up to universal constants, to the square of the expected maximum of the Gaussian free field on G, scaled by the number of edges in G.

We present an all-pairs shortest path algorithm whose running time on a complete directed graph on n vertices whose edge weights are chosen independently and uniformly at random from [0,1] is O(n2), in expectation and with high probability. This resolves a long standing open problem. The algorithm is a variant of the dynamic all-pairs shortest paths algorithm of Demetrescu and Italiano. The analysis relies on a proof that the number of locally shortest paths in such randomly weighted graphs is O(n2), in expectation and with high probability. We also present a dynamic version of the algorithm that recomputes all shortest paths after a random edge update in O(log2n) expected time.

Suppose m balls are sequentially thrown into n bins where each ball goes into a random bin. It is well-known that the gap between the load of the most loaded bin and the average is , or large m. If each ball goes to the lesser loaded of two random bins, this gap dramatically reduces to Θ(log log n) independent of m. Consider now the following “(1 + β)-choice” process for some parameter β ∊ (0, 1): each ball goes to a random bin with probability (1 – β) and the lesser loaded of two random bins with probability β. How does the gap for such a process behave? Suppose that the weight of each ball was drawn from a geometric distribution. How is the gap (now defined in terms of weight) affected? In this work, we develop general techniques for analyzing such balls-into-bins processes. Specifically, we show that for the (1 + β)-choice process above, the gap is Θ(log n/β), irrespective of m. Moreover the gap stays at Θ(log n/β) in the weighted case for a large class of weight distributions. No non-trivial explicit bounds were previously known in the weighted case, even for the 2-choice paradigm.

Bargaining games on exchange networks have been studied by both economists and sociologists. A Balanced Outcome for such a game is an equilibrium concept that combines notions of stability and fairness. In a recent paper, Kleinberg and Tardos introduced balanced outcomes to the computer science community and provided a polynomial-time algorithm to compute the set of such outcomes. Their work left open a pertinent question: are there natural, local dynamics that converge quickly to a balanced outcome? In this paper, we provide a partial answer to this question by showing that simple edge-balancing dynamics converge to a balanced outcome whenever one exists.

1 Three questions. Let G be a d-regular graph on n vertices where 3 ≤ d < n. Perform bond percolation with and let C1 be the largest open cluster. Is E|C1| = O(n2/3)? (This is well known, and sharp, for d = n − 1, the Erdös-Renyi random graph.)

A local graph partitioning algorithm finds a set of vertices with small conductance (i.e. a sparse cut) by adaptively exploring part of a large graph G, starting from a specified vertex. For the algorithm to be local, its complexity must be bounded in terms of the size of the set that it outputs, with at most a weak dependence on the number n of vertices in G. Previous local partitioning algorithms find sparse cuts using random walks and personalized PageRank. In this paper, we introduce a randomized local partitioning algorithm that finds a sparse cut by simulating the volume-biased evolving set process, which is a Markov chain on sets of vertices. We prove that for any set of vertices A that has conductance at most φ, for at least half of the starting vertices in A our algorithm will output (with probability at least half), a set of conductance O(φ 1/2 log 1/2 n). We prove that for a given run of the algorithm, the expected ratio between its computational complexity and the volume of the set that it outputs is O(φ −1/2 polylog(n)). In comparison, the best previous local partitioning algorithm, due to Andersen, Chung, and Lang, has the same approximation guarantee, but a larger ratio of O(φ −1 polylog(n)) between the complexity and output volume. Using our local partitioning algorithm as a subroutine, we construct a fast algorithm for finding balanced cuts. Given a fixed value of φ, the resulting algorithm has complexity (m + nφ −1/2)) · O(polylog(n)) and returns a cut with conductance O(φ 1/2 log 1/2 n) and volume at least vφ/2, where vφ is the largest volume of any set with conductance at most φ. 1 1

We consider the problem of online sublinear expander reconstruction and its relation to random walks in ``noisy" expanders. Given access to an adjacency list representation of a bounded-degree graph G, we want to convert this graph into a bounded-degree expander G' changing G as little aspossible. The graph G' will be output by a distributed filter: this is sublinear time procedure that given a query vertex, outputs all its neighbors in G', and can do so even in a distributed manner, ensuring consistency in all the answers.One of the main tools in our analysis is a result on the behavior of random walks in graph that are almost expanders: graphs that are formed by arbitrarily connecting a small unknown graph (the noise) to a large expander. We show that a random walk from almost any vertex in the expander part will have fast mixing properties, in the general setting of irreducible finite Markov chains. We alsodesign sublinear time procedures to distinguish vertices of the expander part from those in the noise part, and use this procedure in the reconstruction algorithm.

We study the mixing time of some Markov chains converging to critical physical models. These models are indexed by a parameter beta and there exists some critical value betacwhere the model undergoes a phase transition. According to physics lore, the mixing time of such Markov chains is often of logarithmic order outside the critical regime, when beta ne betac, and satisfies-some power law at criticality, when beta = betac. We prove this in the two following settings: 1. Lazy random walk on the critical percolation cluster of "mean-field" graphs, which include the complete graph and random d-regular graphs. The critical mixing time here is of order Theta(n). This answers a question of Benjamini, Kozma and Wormald. 2. Swendsen-Wang dynamics on the complete, graph. The critical mixing time, here is of order Theta(n1/4). This improves results of Cooper, Dyer, Frieze and Rue. In both settings, the main tool is understanding the Markov chain dynamics via properties of critical percolation on the underlying graph.

Say that a k -CNF a formula is p-satisfiable if there exists a truth assignment satisfying a fraction 1 − 2 − k + p 2 − k of its clauses (note that every k -CNF formula is 0-satisfiable). Let F k ( n , m ) denote a random k -CNF formula on n variables with m clauses. For every k ≥2 and every r >0 we determine p and δ=δ( k )= O ( k 2 − k /2 ) such that with probability tending to 1 as n →∞, a random k -CNF formula F k ( n , rn ) is p -satisfiable but not ( p +δ)-satisfiable.

In the cyclic-to-random shuffle, we are given n cards arranged in a circle. At step k, we exchange the kth card along the circle with a uniformly chosen random card. The problem of determining the mixing time of the cyclic-to-random shuffle was raised by Aldous and Diaconis in 1986. Mironov used this shuffle as a model for the cryptographic system known as RC4, and proved an upper bound of O(n log n) for the mixing time. We prove a matching lower bound, thus establishing that the mixing time is indeed of order /spl Theta/(n log n). We also prove an upper bound of O(n log n) for the mixing time of any "semirandom transposition shuffle", i.e., any shuffle in which a random card is exchanged with another card chosen according to an arbitrary (deterministic or random) rule. To prove our lower bound, we exhibit an explicit complex-valued test function which typically takes very different values for permutations arising from few iterations of the cyclic-to-random-shuffle and for uniform random permutations. Perhaps surprisingly, the proof hinges on the fact that the function e/sup z/ - 1 has nonzero fixed points in the complex plane. A key insight from our work is the importance of complex analysis tools for uncovering structure in nonreversible Markov chains.

Maximum satisfiability is a canonical NP-complete problem that appears empirically hard for random instances. At the same time, it is rapidly becoming a canonical problem for statistical physics. In both of these realms, evaluating new ideas relies crucially on knowing the maximum number of clauses one can typically satisfy in a random k-CNF formula. In this paper we give asymptotically tight estimates for this quantity. Our result gives very tight bounds for the fraction of satisfiable clauses in a random k-CNF. In particular, for k > 2 it improves upon all previously known such bound.

Let Fk(n,m) be a random k-SAT formula on n variables formed by selecting uniformly and independently m out of all possible k-clauses. It is well-known that for r ≥ 2k ln 2, Fk(n,rn) is unsatisfiable with probability 1-o(1). We prove that there exists a sequence tk = O(k) such that for r ≥ 2k ln 2 - tk, Fk(n,rn) is satisfiable with probability 1-o(1).Our technique yields an explicit lower bound for every k which for k > 3 improves upon all previously known bounds. For example, when k=10 our lower bound is 704.94 while the upper bound is 708.94.

We show that a new probabilistic technique, recently introduced by the first author, yields the sharpest bounds obtained to date on mixing times in terms of isoperimetric properties of the state space (also known as conductance bounds or Cheeger inequalities). We prove that the bounds for mixing time in total variation obtained by Lovasz and Kannan, can be refined to apply to the maximum relative deviation |pn(x,y)/π(y)-1| of the distribution at time n from the stationary distribution π. Our approach also yields a direct link between isoperimetric inequalities and heat kernel bounds; previously, this link rested on analytic estimates known as Nash inequalities.

We study discrete time Glauber dynamics for random configurations with local constraints (e.g. proper coloring, Ising and Potts models) on finite graphs with n vertices and of bounded degree. We show that the relaxation time (defined as the reciprocal of the spectral gap 1-/spl lambda//sub 2/) for the dynamics on trees and on certain hyperbolic graphs, is polynomial in n. For these hyperbolic graphs, this yields a general polynomial sampling algorithm for random configurations. We then show that if the relaxation time /spl tau//sub 2/ satisfies /spl tau//sub 2/=O(n), then the correlation coefficient, and the mutual information, between any local function (which depends only on the configuration in a fixed window) and the boundary conditions, decays exponentially in the distance between the window and the boundary. For the Ising model on a regular tree, this condition is sharp.