BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
We extend Caffarelli's contraction theorem, by proving that there exists a Lipschitz changes of variables between the Gaussian measure and certain perturbations of it. Our approach is based on an argument due to Kim and Milman, in which the changes of variables are constructed using a heat flow.
We prove moderate deviations bounds for the lower tail of the number of odd cycles in a $\calG(n, m)$ random graph. We show that the probability of decreasing triangle density by t3, is exp(−Θ(n2t2)) whenever n−3/4≪t3≪1, while for k≥5 we give the same estimate for the probability of decreasing the k-cycle density by tk, but for the larger range n−1≪tk≪1. When m≥21(2n), we also find the leading coefficient in the exponent. This complements results of Goldschmidt et al., who showed that for n−3/2≪tk≪n−1, the probability is exp(−Θ(n3t2k)). That is, deviations of order smaller than n−1 behave like small deviations, and deviations of order larger than n−3/4 (for triangles) or n−1 (for k-cycles with k≥5) behave like large deviations. For triangles, we conjecture that a sharp change between the two regimes occurs for deviations of size n−3/4, which we associate with a single large negative eigenvalue of the adjacency matrix becoming responsible for almost all of the cycle deficit. Our results can be interpreted as finite size effects in phase transitions in constrained random graphs.
The analysis of large simple graphs with extreme values of the densities of edges and triangles has been extended to the statistical structure of typical graphs of fixed intermediate densities, by the use of large deviations of Erdoes-Renyi graphs. We prove that the typical graph exhibits sharp singularities as the constraining densities vary between different curves of extreme values, and we determine the precise nature of the singularities. The extension to graphs with fixed densities of edges and k-cycles for odd k>3 is straightforward and we note the simple changes in the proof.
A natural problem in high-dimensional inference is to decide if a classifier f:Rn→{−1,1} depends on a small number of linear directions of its input data. Call a function g:Rn→{−1,1}, a linear k-junta if it is completely determined by some k-dimensional subspace of the input space. A recent work of the authors showed that linear k-juntas are testable. Thus there exists an algorithm to distinguish between: 1. f:Rn→{−1,1} which is a linear k-junta with surface area s, 2. f is ε-far from any linear k-junta with surface area (1+ε)s, where the query complexity of the algorithm is independent of the ambient dimension n. Following the surge of interest in noise-tolerant property testing, in this paper we prove a noise-tolerant (or robust) version of this result. Namely, we give an algorithm which given any c>0, ε>0, distinguishes between 1. f:Rn→{−1,1} has correlation at least c with some linear k-junta with surface area s. 2. f has correlation at most c−ε with any linear k-junta with surface area at most s. The query complexity of our tester is kpoly(s/ε). Using our techniques, we also obtain a fully noise tolerant tester with the same query complexity for any class C of linear k-juntas with surface area bounded by s. As a consequence, we obtain a fully noise tolerant tester with query complexity kO(poly(logk/ε)) for the class of intersection of k-halfspaces (for constant k) over the Gaussian space. Our query complexity is independent of the ambient dimension n. Previously, no non-trivial noise tolerant testers were known even for a single halfspace.
The planted bisection model is a random graph model in which the nodes are divided into two equal-sized communities and then edges are added randomly in a way that depends on the community membership. We establish necessary and sufficient conditions for the asymptotic recoverability of the planted bisection in this model. When the bisection is asymptotically recoverable, we give an efficient algorithm that successfully recovers it. We also show that the planted bisection is recoverable asymptotically if and only if with high probability every node belongs to the same community as the majority of its neighbors. Our algorithm for finding the planted bisection runs in time almost linear in the number of edges. It has three stages: spectral clustering to compute an initial guess, a "replica" stage to get almost every vertex correct, and then some simple local moves to finish the job. An independent work by Abbe, Bandeira, and Hall establishes similar (slightly weaker) results but only in the case of logarithmic average degree.
We prove Ehrhard's inequality using interpolation along the Ornstein-Uhlenbeck semi-group. We also provide an improved Jensen inequality for Gaussian variables that might be of independent interest.
We consider the problem of reconstructing sparse symmetric block models with two blocks and connection probabilities a/n and b/n for inter- and intra-block edge probabilities, respectively. It was recently shown that one can do better than a random guess if and only if (a−b)2>2(a+b). Using a variant of belief propagation, we give a reconstruction algorithm that is optimal in the sense that if (a−b)2>C(a+b) for some constant C then our algorithm maximizes the fraction of the nodes labeled correctly. Ours is the only algorithm proven to achieve the optimal fraction of nodes labeled correctly. Along the way, we prove some results of independent interest regarding robust reconstruction for the Ising model on regular and Poisson trees.
We give upper and lower bounds on the information-theoretic threshold for community detection in the stochastic block model. Specifically, consider the symmetric stochastic block model with q groups, average degree d, and connection probabilities cin/n and cout/n for within-group and between-group edges respectively; let λ=(cin−cout)/(qd). We show that, when q is large, and λ=O(1/q), the critical value of d at which community detection becomes possible---in physical terms, the condensation threshold---is dc=Θ(qλ2logq), with tighter results in certain regimes. Above this threshold, we show that any partition of the nodes into q groups which is as `good' as the planted one, in terms of the number of within- and between-group edges, is correlated with it. This gives an exponential-time algorithm that performs better than chance; specifically, community detection becomes possible below the Kesten-Stigum bound for q≥5 in the disassortative case λ<0, and for q≥11 in the assortative case λ>0 (similar upper bounds were obtained independently by Abbe and Sandon). Conversely, below this threshold, we show that no algorithm can label the vertices better than chance, or even distinguish the block model from an \ER\ random graph with high probability. Our lower bound on dc uses Robinson and Wormald's small subgraph conditioning method, and we also give (less explicit) results for non-symmetric stochastic block models. In the symmetric case, we obtain explicit results by using bounds on certain functions of doubly stochastic matrices due to Achlioptas and Naor; indeed, our lower bound on dc is their second moment lower bound on the q-colorability threshold for random graphs with a certain effective degree.
Benjamini, Kalai and Schramm showed that a monotone function f:{−1,1}n→{−1,1} is noise stable if and only if it is correlated with a half-space (a set of the form {x:⟨x,a⟩≤b}). We study noise stability in terms of correlation with half-spaces for general (not necessarily monotone) functions. We show that a function f:{−1,1}n→{−1,1} is noise stable if and only if it becomes correlated with a half-space when we modify f by randomly restricting a constant fraction of its coordinates. Looking at random restrictions is necessary: we construct noise stable functions whose correlation with any half-space is o(1). The examples further satisfy that different restrictions are correlated with different half-spaces: for any fixed half-space, the probability that a random restriction is correlated with it goes to zero. We also provide quantitative versions of the above statements, and versions that apply for the Gaussian measure on Rn instead of the discrete cube. Our work is motivated by questions in learning theory and a recent question of Khot and Moshkovitz.
We study a random graph model named the "block model" in statistics and the "planted partition model" in theoretical computer science. In its simplest form, this is a random graph with two equal-sized clusters, with a between-class edge probability of q and a within-class edge probability of p. A striking conjecture of Decelle, Krzkala, Moore and Zdeborová based on deep, non-rigorous ideas from statistical physics, gave a precise prediction for the algorithmic threshold of clustering in the sparse planted partition model. In particular, if p=a/n and q=b/n, s=(a−b)/2 and p=(a+b)/2 then Decelle et al.\ conjectured that it is possible to efficiently cluster in a way correlated with the true partition if s2>p and impossible if s2<p. By comparison, the best-known rigorous result is that of Coja-Oghlan, who showed that clustering is possible if s2>Cplnp for some sufficiently large C. In a previous work, we proved that indeed it is information theoretically impossible to to cluster if s2<p and furthermore it is information theoretically impossible to even estimate the model parameters from the graph when s2<p. Here we complete the proof of the conjecture by providing an efficient algorithm for clustering in a way that is correlated with the true partition when s2>p. A different independent proof of the same result was recently obtained by Laurent Massoulie.
In this paper we consider the collaborative ranking setting: a pool of users each provides a small number of pairwise preferences between d possible items; from these we need to predict preferences of the users for items they have not yet seen. We do so by fitting a rank r score matrix to the pairwise data, and provide two main contributions: (a) we show that an algorithm based on convex optimization provides good generalization guarantees once each user provides as few as O(rlog2d) pairwise comparisons -- essentially matching the sample complexity required in the related matrix completion setting (which uses actual numerical as opposed to pairwise information), and (b) we develop a large-scale non-convex implementation, which we call AltSVM, that trains a factored form of the matrix via alternating minimization (which we show reduces to alternating SVM problems), and scales and parallelizes very well to large problem settings. It also outperforms common baselines on many moderately large popular collaborative filtering datasets in both NDCG and in other measures of ranking performance.
We prove the first robust dimension free isoperimetric result for the standard Gaussian measure γn and the corresponding boundary measure γn+ in Rn. The main result in the theory of Gaussian isoperimetry (proven in the 1970s by Sudakov and Tsirelson, and independently by Borell) states that if γn(A)=1/2 then the surface area of A is bounded by the surface area of a half-space with the same measure, γn+(A)≤(2π)−1/2. Our results imply in particular that if A⊂Rn satisfies γn(A)=1/2 and γn+(A)≤(2π)−1/2+δ then there exists a half-space B⊂Rn such that γn(AΔB)≤Clog−1/2(1/δ) for an absolute constant C. Since the Gaussian isoperimetric result was established, only recently a robust version of the Gaussian isoperimetric result was obtained by Cianchi et al., who showed that γn(AΔB)≤C(n)δ for some function C(n) with no effective bounds. Compared to the results of Cianchi et al., our results have optimal (i.e., no) dependence on the dimension, but worse dependence on δ.
We consider the problem of clustering (or reconstruction) in the stochastic block model, in the regime where the average degree is constant. For the case of two clusters with equal sizes, recent results by Mossel, Neeman and Sly, and by Massoulie, show that reconstructability undergoes a phase transition at the Kesten-Stigum bound of λ22d=1, where λ2 is the second largest eigenvalue of a related stochastic matrix and d is the average degree. In this paper, we address the general case of more than two clusters and/or unbalanced cluster sizes. Our main result is a sufficient condition for clustering to be impossible, which matches the existing result for two clusters of equal sizes. A key ingredient in our result is a new connection between non-reconstructability and non-distinguishability of the block model from an Erdős-Rényi model with the same average degree. We also show that it is some times possible to reconstruct even when λ22d<1. Our results provide evidence supporting a series of conjectures made by Decelle, Krzkala, Moore and Zdeborová regarding reconstructability and distinguishability of stochastic block models (but do not settle them).
The Standard Simplex Conjecture and the Plurality is Stablest Conjecture are two conjectures stating that certain partitions are optimal with respect to Gaussian and discrete noise stability respectively. These two conjectures are natural generalizations of the Gaussian noise stability result by Borell (1985) and the Majority is Stablest Theorem (2004). Here we show that the standard simplex is not the most stable partition in Gaussian space and that Plurality is not the most stable low influence partition in discrete space for every number of parts k≥3, for every value ρ=0 of the noise and for every prescribed measures for the different parts as long as they are not all equal to 1/k. Our results do not contradict the original statements of the Plurality is Stablest and Standard Simplex Conjectures in their original statements concerning partitions to sets of equal measure. However, they indicate that if these conjectures are true, their veracity and their proofs will crucially rely on assuming that the sets are of equal measures, in stark contrast to Borell's result, the Majority is Stablest Theorem and many other results in isoperimetric theory. Given our results it is natural to ask for (conjectured) partitions achieving the optimum noise stability.
Recently, Kothari et al.\ gave an algorithm for testing the surface area of an arbitrary set A⊂[0,1]n. Specifically, they gave a randomized algorithm such that if A's surface area is less than S then the algorithm will accept with high probability, and if the algorithm accepts with high probability then there is some perturbation of A with surface area at most κnS. Here, κn is a dimension-dependent constant which is strictly larger than 1 if n≥2, and grows to 4/π as n→∞. We give an improved analysis of Kothari et al.'s algorithm. In doing so, we replace the constant κn with 1+η for η>0 arbitrary. We also extend the algorithm to more general measures on Riemannian manifolds.
We give a multivariate generalization of Borell's noise stability theorem for Gaussian vectors. As a consequence we recover two inequalities, also due to Borell, for exit times of the Ornstein-Uhlenbeck process.
We prove that under the Gaussian measure, half-spaces are uniquely the most noise stable sets. We also prove a quantitative version of uniqueness, showing that a set which is almost optimally noise stable must be close to a half-space. This extends a theorem of Borell, who proved the same result but without uniqueness, and it also answers a question of Ledoux, who asked whether it was possible to prove Borell's theorem using a direct semigroup argument. Our quantitative uniqueness result has various applications in diverse fields.
Spectral algorithms are classic approaches to clustering and community detection in networks. However, for sparse networks the standard versions of these algorithms are suboptimal, in some cases completely failing to detect communities even when other algorithms such as belief propagation can do so. Here we introduce a new class of spectral algorithms based on a non-backtracking walk on the directed edges of the graph. The spectrum of this operator is much better-behaved than that of the adjacency matrix or other commonly used matrices, maintaining a strong separation between the bulk eigenvalues and the eigenvalues relevant to community structure even in the sparse case. We show that our algorithm is optimal for graphs generated by the stochastic block model, detecting communities all the way down to the theoretical limit. We also show the spectrum of the non-backtracking operator for some real-world networks, illustrating its advantages over traditional spectral clustering.
Consider an election between k candidates in which each voter votes randomly (but not necessarily independently) and suppose that there is a single candidate that every voter prefers (in the sense that each voter is more likely to vote for this special candidate than any other candidate). Suppose we have a voting rule that takes all of the votes and produces a single outcome and suppose that each individual voter has little effect on the outcome of the voting rule. If the voting rule is a weighted plurality, then we show that with high probability, the preferred candidate will win the election. Conversely, we show that this statement fails for all other reasonable voting rules. This result is an extension of Häggström, Kalai and Mossel, who proved the above in the case k=2.
Consider n individuals who, by popular vote, choose among q >= 2 alternatives, one of which is "better" than the others. Assume that each individual votes independently at random, and that the probability of voting for the better alternative is larger than the probability of voting for any other. It follows from the law of large numbers that a plurality vote among the n individuals would result in the correct outcome, with probability approaching one exponentially quickly as n tends to infinity. Our interest in this paper is in a variant of the process above where, after forming their initial opinions, the voters update their decisions based on some interaction with their neighbors in a social network. Our main example is "majority dynamics", in which each voter adopts the most popular opinion among its friends. The interaction repeats for some number of rounds and is then followed by a population-wide plurality vote. The question we tackle is that of "efficient aggregation of information": in which cases is the better alternative chosen with probability approaching one as n tends to infinity? Conversely, for which sequences of growing graphs does aggregation fail, so that the wrong alternative gets chosen with probability bounded away from zero? We construct a family of examples in which interaction prevents efficient aggregation of information, and give a condition on the social network which ensures that aggregation occurs. For the case of majority dynamics we also investigate the question of unanimity in the limit. In particular, if the voters' social network is an expander graph, we show that if the initial population is sufficiently biased towards a particular alternative then that alternative will eventually become the unanimous preference of the entire population.
The Majority is Stablest Theorem has numerous applications in hardness of approximation and social choice theory. We give a new proof of the Majority is Stablest Theorem by induction on the dimension of the discrete cube. Unlike the previous proof, it uses neither the "invariance principle" nor Borell's result in Gaussian space. The new proof is general enough to include all previous variants of majority is stablest such as "it ain't over until it's over" and "Majority is most predictable". Moreover, the new proof allows us to derive a proof of Majority is Stablest in a constant level of the Sum of Squares hierarchy.This implies in particular that Khot-Vishnoi instance of Max-Cut does not provide a gap instance for the Lasserre hierarchy.
Suppose Alice and Bob receive strings X=(X1,...,Xn) and Y=(Y1,...,Yn) each uniformly random in [s]n but so that X and Y are correlated . For each symbol i, we have that Yi=Xi with probability $1-\eps$ and otherwise Yi is chosen independently and uniformly from [s]. Alice and Bob wish to use their respective strings to extract a uniformly chosen common sequence from [s]k but without communicating. How well can they do? The trivial strategy of outputting the first k symbols yields an agreement probability of $(1 - \eps + \eps/s)^k$. In a recent work by Bogdanov and Mossel it was shown that in the binary case where s=2 and $k = k(\eps)$ is large enough then it is possible to extract k bits with a better agreement probability rate. In particular, it is possible to achieve agreement probability $(k\eps)^{-1/2} \cdot 2^{-k\eps/(2(1 - \eps/2))}$ using a random construction based on Hamming balls, and this is optimal up to lower order terms. In the current paper we consider the same problem over larger alphabet sizes s and we show that the agreement probability rate changes dramatically as the alphabet grows. In particular we show no strategy can achieve agreement probability better than $(1-\eps)^k (1+δ(s))^k$ where δ(s)→0 as s→∞. We also show that Hamming ball based constructions have {\em much lower} agreement probability rate than the trivial algorithm as s→∞. Our proofs and results are intimately related to subtle properties of hypercontractive inequalities.
The planted partition model (also known as the stochastic blockmodel) is a classical cluster-exhibiting random graph model that has been extensively studied in statistics, physics, and computer science. In its simplest form, the planted partition model is a model for random graphs on n nodes with two equal-sized clusters, with an between-class edge probability of q and a within-class edge probability of p. Although most of the literature on this model has focused on the case of increasing degrees (ie.\ pn,qn→∞ as n→∞), the sparse case p,q=O(1/n) is interesting both from a mathematical and an applied point of view. A striking conjecture of Decelle, Krzkala, Moore and Zdeborová based on deep, non-rigorous ideas from statistical physics gave a precise prediction for the algorithmic threshold of clustering in the sparse planted partition model. In particular, if p=a/n and q=b/n, then Decelle et al.\ conjectured that it is possible to cluster in a way correlated with the true partition if (a−b)2>2(a+b), and impossible if (a−b)2<2(a+b). By comparison, the best-known rigorous result is that of Coja-Oghlan, who showed that clustering is possible if (a−b)2>C(a+b) for some sufficiently large C. We prove half of their prediction, showing that it is indeed impossible to cluster if (a−b)2<2(a+b). Furthermore we show that it is impossible even to estimate the model parameters from the graph when (a−b)2<2(a+b); on the other hand, we provide a simple and efficient algorithm for estimating a and b when (a−b)2>2(a+b). Following Decelle et al, our work establishes a rigorous connection between the clustering problem, spin-glass models on the Bethe lattice and the so called reconstruction problem. This connection points to fascinating applications and open problems.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.