A distribution over instances of a sampling problem is said to exhibit transport disorder chaos if perturbing the instance by a small amount of random noise dramatically changes the stationary distribution (in Wasserstein distance). Seeking to provide evidence that some sampling tasks are hard on average, a recent line of work has demonstrated that disorder chaos is sufficient to rule out “stable” sampling algorithms, such as gradient methods and some diffusion processes. We demonstrate that disorder chaos does not preclude polynomial-time sampling by canonical algorithms in canonical models. We show that with high probability over a random graph $\mathbf{G} \sim G(n,1/2)$: (1) the hardcore model (at fugacity $\lambda = 1$) on $\mathbf{G}$ exhibits disorder chaos, and (2) Glauber dynamics run for $O(n)$ time can approximately sample from the hardcore model on $\mathbf{G}$ (in Wasserstein distance).

We show that the shortest $s$-$t$ path problem has the overlap-gap property in (i) sparse $\mathbb{G}(n,p)$ graphs and (ii) complete graphs with i.i.d. Exponential edge weights. Furthermore, we demonstrate that in sparse $\mathbb{G}(n,p)$ graphs, shortest path is solved by $O(\log n)$-degree polynomial estimators, and a uniform approximate shortest path can be sampled in polynomial time. This constitutes the first example in which the overlap-gap property is not predictive of algorithmic intractability for a (non-algebraic) average-case optimization problem.

Approximate message passing (AMP) is a family of iterative algorithms that generalize matrix power iteration. AMP algorithms are known to optimally solve many average-case optimization problems. In this paper, we show that a large class of AMP algorithms can be simulated in polynomial time by local statistics hierarchy semidefinite programs (SDPs), even when an unknown principal minor of measure 1/polylog(dimension) is adversarially corrupted. Ours are the first robust guarantees for many of these problems. Further, our results offer an interesting counterpoint to strong lower bounds against less constrained SDP relaxations for average-case max-cut-gain (a.k.a. “optimizing the Sherrington-Kirkpatrick Hamiltonian”) and other problems.

Consider a random geometric 2-dimensional simplicial complex X sampled as follows: first, sample n vectors u1,…,un uniformly at random on Sd−1; then, for each triple i,j,k ∈ [n], add {i,j,k} and all of its subsets to X if and only if ⟨ ui,uj ⟩ ≥ τ, ⟨ ui,uk ⟩ ≥ τ, and ⟨ uj, uk ⟩ ≥ τ. We prove that for every ε > 0, there exists a choice of d = Θ(logn) and τ = τ(ε,d) so that with high probability, X is a high-dimensional expander of average degree nε in which each 1-link has spectral gap bounded away from 1/2.

We consider a very wide class of models for sparse random Boolean 2CSPs; equivalently, degree-2 optimization problems over~$\{\pm 1\}^n$. For each model $\mathcal{M}$, we identify the "high-probability value"~$s^*_{\mathcal{M}}$ of the natural SDP relaxation (equivalently, the quantum value). That is, for all $\varepsilon > 0$ we show that the SDP optimum of a random $n$-variable instance is (when normalized by~$n$) in the range $(s^*_{\mathcal{M}}-\varepsilon, s^*_{\mathcal{M}}+\varepsilon)$ with high probability. Our class of models includes non-regular CSPs, and ones where the SDP relaxation value is strictly smaller than the spectral relaxation value.

Many high-dimensional statistical inference problems are believed to possess inherent computational hardness. Various frameworks have been proposed to give rigorous evidence for such hardness, including lower bounds against restricted models of computation (such as low-degree functions), as well as methods rooted in statistical physics that are based on free energy landscapes. This paper aims to make a rigorous connection between the seemingly different low-degree and free-energy based approaches. We define a free-energy based criterion for hardness and formally connect it to the well-established notion of low-degree hardness for a broad class of statistical problems, namely all Gaussian additive models and certain models with a sparse planted signal. By leveraging these rigorous connections we are able to: establish that for Gaussian additive models the "algebraic" notion of low-degree hardness implies failure of "geometric" local MCMC algorithms, and provide new low-degree lower bounds for sparse linear regression which seem difficult to prove directly. These results provide both conceptual insights into the connections between different notions of hardness, as well as concrete technical tools such as new methods for proving low-degree lower bounds.

The random geometric graph model GRGd(n,p) is a distribution over graphs in which the edges capture a latent geometry. To sample G ∼ GRGd(n,p), we identify each of our n vertices with an independently and uniformly sampled vector from the d-dimensional unit sphere Sd−1, and we connect pairs of vertices whose vectors are “sufficiently close,” such that the marginal probability of an edge is p. Because of the underlying geometry, this model is natural for applications in data science and beyond.

Researchers currently use a number of approaches to predict and substantiate information-computation gaps in high-dimensional statistical estimation problems. A prominent approach is to characterize the limits of restricted models of computation, which on the one hand yields strong computational lower bounds for powerful classes of algorithms and on the other hand helps guide the development of efficient algorithms. In this paper, we study two of the most popular restricted computational models, the statistical query framework and low-degree polynomials, in the context of high-dimensional hypothesis testing. Our main result is that under mild conditions on the testing problem, the two classes of algorithms are essentially equivalent in power. As corollaries, we obtain new statistical query lower bounds for sparse PCA, tensor PCA and several variants of the planted clique problem.

We study the extent to which wide neural networks may be approximated by Gaussian processes, when initialized with random weights. It is a well-established fact that as the width of a network goes to infinity, its law converges to that of a Gaussian process. We make this quantitative by establishing explicit convergence rates for the central limit theorem in an infinite-dimensional functional space, metrized with a natural transportation distance. We identify two regimes of interest; when the activation function is polynomial, its degree determines the rate of convergence, while for non-polynomial activations, the rate is governed by the smoothness of the function.

We formulate a new hardness assumption, the Strongish Planted Clique Hypothesis (SPCH), which postulates that any algorithm for planted clique must run in time $n^{Ω(\log{n})}$ (so that the state-of-the-art running time of $n^{O(\log n)}$ is optimal up to a constant in the exponent). We provide two sets of applications of the new hypothesis. First, we show that SPCH implies (nearly) tight inapproximability results for the following well-studied problems in terms of the parameter $k$: Densest $k$-Subgraph, Smallest $k$-Edge Subgraph, Densest $k$-Subhypergraph, Steiner $k$-Forest, and Directed Steiner Network with $k$ terminal pairs. For example, we show, under SPCH, that no polynomial time algorithm achieves $o(k)$-approximation for Densest $k$-Subgraph. This inapproximability ratio improves upon the previous best $k^{o(1)}$ factor from (Chalermsook et al., FOCS 2017). Furthermore, our lower bounds hold even against fixed-parameter tractable algorithms with parameter $k$. Our second application focuses on the complexity of graph pattern detection. For both induced and non-induced graph pattern detection, we prove hardness results under SPCH, which improves the running time lower bounds obtained by (Dalirrooyfard et al., STOC 2019) under the Exponential Time Hypothesis.

We study fast algorithms for statistical regression problems under the strong contamination model, where the goal is to approximately optimize a generalized linear model (GLM) given adversarially corrupted samples. Prior works in this line of research were based on the \emph{robust gradient descent} framework of \cite{PrasadSBR20}, a first-order method using biased gradient queries, or the \emph{Sever} framework of \cite{DiakonikolasKK019}, an iterative outlier-removal method calling a stationary point finder. We present nearly-linear time algorithms for robust regression problems with improved runtime or estimation guarantees compared to the state-of-the-art. For the general case of smooth GLMs (e.g.\ logistic regression), we show that the robust gradient descent framework of \cite{PrasadSBR20} can be \emph{accelerated}, and show our algorithm extends to optimizing the Moreau envelopes of Lipschitz GLMs (e.g.\ support vector machines), answering several open questions in the literature. For the well-studied case of robust linear regression, we present an alternative approach obtaining improved estimation rates over prior nearly-linear time algorithms. Interestingly, our algorithm starts with an identifiability proof introduced in the context of the sum-of-squares algorithm of \cite{BakshiP21}, which achieved optimal error rates while requiring large polynomial runtime and sample complexity. We reinterpret their proof within the Sever framework and obtain a dramatically faster and more sample-efficient algorithm under fewer distributional assumptions.

We give an algorithm for solving unique games (UG) instances whenever low-degree sum-of-squares proofs certify good bounds on the small-set-expansion of the underlying constraint graph via a hypercontractive inequality. Our algorithm is in fact more versatile, and succeeds even when the constraint graph is not a small-set expander as long as the structure of non-expanding small sets is (informally speaking) “characterized” by a low-degree sum-of-squares proof. Our results are obtained by rounding low-entropy solutions — measured via a new global potential function — to sum-of-squares (SoS) semidefinite programs. This technique adds to the (currently short) list of general tools for analyzing SoS relaxations for worst-case optimization problems.

We show that for every ε > 0, the degree-nεSherali-Adams linear program (with exp(Õ(nε)) variables and constraints) approximates the maximum cut problem within a factor of ([1/2]+ε'), for some ε'(ε)>0. Our result provides a surprising converse to known lower bounds against all linear programming relaxations of Max-Cut [1], [2], and hence resolves the extension complexity of approximate Max-Cut for approximation factors close to [1/2] (up to the function ε'(ε)). Previously, only semidefinite programs and spectral methods were known to yield approximation factors better than [1/2] for Max-Cut in time 2o(n). We also show that constant-degree Sherali-Adams linear programs (with poly(n) variables and constraints) can solve Max-Cut with approximation factor close to 1 on graphs of small threshold rank: this is the first connection of which we are aware between threshold rank and linear programming-based algorithms. Our results separate the power of Sherali-Adams versus Lovász-Schrijver hierarchies for approximating Max-Cut, since it is known [3] that ([1/2]+ε) approximation of Max Cut requires Ωε(n) rounds in the Lovász-Schrijver hierarchy. We also provide a subexponential time approximation for Khot's Unique Games problem [4]: we show that for every ε>0 the degree-(nεlog q) Sherali-Adams linear program distinguishes instances of Unique Games of value ≥ 1-ε'from instances of value ≤ ε', for some ε'(ε)>0, where q is the alphabet size. Such guarantees are qualitatively similar to those of previous subexponential-time algorithms for Unique Games but our algorithm does not rely on semidefinite programming or subspace enumeration techniques [5]-[6]-[7].

Let $G$ be any $n$-vertex graph whose random walk matrix has its nontrivial eigenvalues bounded in magnitude by $1/\sqrtΔ$ (for example, a random graph $G$ of average degree~$Θ(Δ)$ typically has this property). We show that the $\exp\Big(c \frac{\log n}{\log Δ}\Big)$-round Sherali--Adams linear programming hierarchy certifies that the maximum cut in such a~$G$ is at most $50.1\%$ (in fact, at most $\tfrac12 + 2^{-Ω(c)}$). For example, in random graphs with $n^{1.01}$ edges, $O(1)$ rounds suffice; in random graphs with $n \cdot \text{polylog}(n)$ edges, $n^{O(1/\log \log n)} = n^{o(1)}$ rounds suffice. Our results stand in contrast to the conventional beliefs that linear programming hierarchies perform poorly for \maxcut and other CSPs, and that eigenvalue/SDP methods are needed for effective refutation. Indeed, our results imply that constant-round Sherali--Adams can strongly refute random Boolean $k$-CSP instances with $n^{\lceil k/2 \rceil + δ}$ constraints; previously this had only been done with spectral algorithms or the SOS SDP hierarchy.

We give a spectral algorithm for decomposing overcomplete order-4 tensors, so long as their components satisfy an algebraic non-degeneracy condition that holds for nearly all (all but an algebraic set of measure $0$) tensors over $(\mathbb{R}^d)^{\otimes 4}$ with rank $n \le d^2$. Our algorithm is robust to adversarial perturbations of bounded spectral norm. Our algorithm is inspired by one which uses the sum-of-squares semidefinite programming hierarchy (Ma, Shi, and Steurer STOC’16), and we achieve comparable robustness and overcompleteness guarantees under similar algebraic assumptions. However, our algorithm avoids semidefinite programming and may be implemented as a series of basic linear-algebraic operations. We consequently obtain a much faster running time than semidefinite programming methods: our algorithm runs in time $\tilde O(n^2d^3) \le \tilde O(d^7)$, which is subquadratic in the input size $d^4$ (where we have suppressed factors related to the condition number of the input tensor).

Many previous Sum-of-Squares (SOS) lower bounds for CSPs had two deficiencies related to global constraints. First, they were not able to support a "cardinality constraint", as in, say, the Min-Bisection problem. Second, while the pseudoexpectation of the objective function was shown to have some value beta, it did not necessarily actually "satisfy" the constraint "objective = beta". In this paper we show how to remedy both deficiencies in the case of random CSPs, by translating global constraints into local constraints. Using these ideas, we also show that degree-Omega(sqrt{n}) SOS does not provide a (4/3 - epsilon)-approximation for Min-Bisection, and degree-Omega(n) SOS does not provide a (11/12 + epsilon)-approximation for Max-Bisection or a (5/4 - epsilon)-approximation for Min-Bisection. No prior SOS lower bounds for these problems were known.

We consider the graph matching/similarity problem of determining how similar two given graphs $G_0,G_1$ are and recovering the permutation $\pi$ on the vertices of $G_1$ that minimizes the symmetric difference between the edges of $G_0$ and $\pi(G_1)$. Graph matching/similarity has applications for pattern matching, vision, social network anonymization, malware analysis, and more. We give the first efficient algorithms proven to succeed in the correlated Erdös-Rényi model (Pedarsani and Grossglauser, 2011). Specifically, we give a polynomial time algorithm for the graph similarity/hypothesis testing task which works for every constant level of correlation between the two graphs that can be arbitrarily close to zero. We also give a quasi-polynomial ($n^{O(\log n)}$ time) algorithm for the graph matching task of recovering the permutation minimizing the symmetric difference in this model. This is the first algorithm to do so without requiring as additional input a ``seed'' of the values of the ground truth permutation on at least $n^{\Omega(1)}$ vertices. Our algorithms follow a general framework of counting the occurrences of subgraphs from a particular family of graphs allowing for tradeoffs between efficiency and accuracy.

Unlike its cousin 3SAT, the NAE-3SAT (not-all-equal-3SAT) problem has the property that spectral/SDP algorithms can efficiently refute random instances when the constraint density is a large constant (with high probability). But do these methods work immediately above the “satisfiability threshold”, or is there still a range of constraint densities for which random NAE-3SAT instances are unsatisfiable but hard to refute? We show that the latter situation prevails, at least in the context of random regular instances and SDP-based refutation. More precisely, whereas a random d-regular instance of NAE-3SAT is easily shown to be unsatisfiable (whp) once d ≥ 8, we establish the following sharp threshold result regarding efficient refutation: If d < 13.5 then the basic SDP, even augmented with triangle inequalities, fails to refute satisfiability (whp); if d > 13.5 then even the most basic spectral algorithm refutes satisfiability (whp).

We give query-efficient algorithms for the global min-cut and the s-t cut problem in unweighted, undirected graphs. Our oracle model is inspired by the submodular function minimization problem: on query S \subset V, the oracle returns the size of the cut between S and V \ S. We provide algorithms computing an exact minimum $s$-$t$ cut in $G$ with ~{O}(n^{5/3}) queries, and computing an exact global minimum cut of G with only ~{O}(n) queries (while learning the graph requires ~{\Theta}(n^2) queries).

The problem of finding large cliques in random graphs and its “planted” variant, where one wants to recover a clique of size ω > log ( n ) added to an Erdős-Rényi graph G ∼ G ( n ,1/2), have been intensely studied. Nevertheless, existing polynomial time algorithms can only recover planted cliques of size ω = Ω (√ n ). By contrast, information theoretically, one can recover planted cliques so long as ω > log ( n ). In this work, we continue the investigation of algorithms from the Sum of Squares hierarchy for solving the planted clique problem begun by Meka, Potechin, and Wigderson [2] and Deshpande and Montanari [25]. Our main result is that degree four SoS does not recover the planted clique unless ω > √ n / polylog n , improving on the bound ω > n 1/3 due to Reference [25]. An argument of Kelner shows that the this result cannot be proved using the same certificate as prior works. Rather, our proof involves constructing and analyzing a new certificate that yields the nearly tight lower bound by “correcting” the certificate of References [2, 25, 27].

We develop fast spectral algorithms for tensor decomposition that match the robustness guarantees of the best known polynomial-time algorithms for this problem based on the sum-of-squares (SOS) semidefinite programming hierarchy. Our algorithms can decompose a 4-tensor with $n$-dimensional orthonormal components in the presence of error with constant spectral norm (when viewed as an $n^2$-by-$n^2$ matrix). The running time is $n^5$ which is close to linear in the input size $n^4$. We also obtain algorithms with similar running time to learn sparsely-used orthogonal dictionaries even when feature representations have constant relative sparsity and non-independent coordinates. The only previous polynomial-time algorithms to solve these problem are based on solving large semidefinite programs. In contrast, our algorithms are easy to implement directly and are based on spectral projections and tensor-mode rearrangements. Or work is inspired by recent of Hopkins, Schramm, Shi, and Steurer (STOC’16) that shows how fast spectral algorithms can achieve the guarantees of SOS for average-case problems. In this work, we introduce general techniques to capture the guarantees of SOS for worst-case problems.

We study planted problems-finding hidden structures in random noisy inputs-through the lens of the sum-of-squares semidefinite programming hierarchy (SoS). This family of powerful semidefinite programs has recently yielded many new algorithms for planted problems, often achieving the best known polynomial-time guarantees in terms of accuracy of recovered solutions and robustness to noise. One theme in recent work is the design of spectral algorithms which match the guarantees of SoS algorithms for planted problems. Classical spectral algorithms are often unable to accomplish this: the twist in these new spectral algorithms is the use of spectral structure of matrices whose entries are low-degree polynomials of the input variables. We prove that for a wide class of planted problems, including refuting random constraint satisfaction problems, tensor and sparse PCA, densest-ksubgraph, community detection in stochastic block models, planted clique, and others, eigenvalues of degree-d matrix polynomials are as powerful as SoS semidefinite programs of degree d. For such problems it is therefore always possible to match the guarantees of SoS without solving a large semidefinite program. Using related ideas on SoS algorithms and lowdegree matrix polynomials (and inspired by recent work on SoS and the planted clique problem [BHK+16]), we prove a new SoS lower bound for the tensor PCA problem.

Random constraint satisfaction problems (CSPs) are known to exhibit threshold phenomena: given a uniformly random instance of a CSP with n variables and m clauses, there is a value of m = Ω(n) beyond which the CSP will be unsatisfiable with high probability. Strong refutation is the problem of certifying that no variable assignment satisfies more than a constant fraction of clauses; this is the natural algorithmic problem in the unsatisfiable regime (when m/n = ω(1)).

The problem of finding large cliques in random graphs and its “planted” variant, where one wants to recover a clique of size ω ≫ log (n) added to an Erdős-Rényi graph , have been intensely studied. Nevertheless, existing polynomial time algorithms can only recover planted cliques of size . By contrast, information theoretically, one can recover planted cliques so long as ω ≫ log (n). In this work, we continue the investigation of algorithms from the sum of squares hierarchy for solving the planted clique problem begun by Meka, Potechin, and Wigderson [MPW15] and Deshpande and Montanari [DM15b]. Our main results improve upon both these previous works by showing: 1. Degree four SoS does not recover the planted clique unless , improving upon the bound ω ≫ n1/3 due to [DM15b]. 2. For , degree 2d SoS does not recover the planted clique unless ω ≫ n1/(d+1)/(2d polylog n), improving upon the bound due to [MPW15]. Our proof for the second result is based on a fine spectral analysis of the certificate used in the prior works [MPW15, DM15b, FK03] by decomposing it along an appropriately chosen basis. Along the way, we develop combinatorial tools to analyze the spectrum of random matrices with dependent entries and to understand the symmetries in the eigenspaces of the set symmetric matrices inspired by work of Grigoriev [Gri01a] An argument of Kelner shows that the first result cannot be proved using the same certificate. Rather, our proof involves constructing and analyzing a new certificate that yields the nearly tight lower bound by “correcting” the certificate of [MPW15, DM15b, FK03]

We consider two problems that arise in machine learning applications: the problem of recovering a planted sparse vector in a random linear subspace and the problem of decomposing a random low-rank overcomplete 3-tensor. For both problems, the best known guarantees are based on the sum-of-squares method. We develop new algorithms inspired by analyses of the sum-of-squares method. Our algorithms achieve the same or similar guarantees as sum-of-squares for these problems but the running time is significantly faster.

The stochastic block model is a classical cluster exhibiting random graph model that has been widely studied in statistics, physics, and computer science. In its simplest form, the model is a random graph with two equal-sized clusters, with intracluster edge probability p, and intercluster edge probability q. We focus on the sparse case, i.e., p, q = O(1/n), which is practically more relevant and also mathematically more challenging. A conjecture of Decelle, Krzakala, Moore, and Zdeborová, based on ideas from statistical physics, predicted a specific threshold for clustering. The negative direction of the conjecture was proved by Mossel, Neeman, and Sly (2012), and more recently, the positive direction was independently proved by Massoulié and Mossel, Neeman, and Sly. In many real network clustering problems, nodes contain information as well. We study the interplay between node and network information in clustering by studying a labeled block model, where in addition to the edge information, the true cluster labels of a small fraction of the nodes are revealed. In the case of two clusters, we show that below the threshold, a small amount of node information does not affect recovery. On the other hand, we show that for any small amount of information, efficient local clustering is achievable as long as the number of clusters is sufficiently large (as a function of the amount of revealed information).

We give new rounding schemes for the standard linear programming relaxation of the correlation clustering problem, achieving approximation factors almost matching the integrality gaps: For complete graphs our approximation is 2.06 - ε, which almost matches the previously known integrality gap of 2. For complete k-partite graphs our approximation is 3. We also show a matching integrality gap. For complete graphs with edge weights satisfying triangle inequalities and probability constraints, our approximation is 1.5, and we show an integrality gap of 1.2.

The stochastic block model is a classical cluster-exhibiting random graph model that has been widely studied in statistics, physics and computer science. In its simplest form, the model is a random graph with two equal-sized clusters, with intra-cluster edge probability p, and inter-cluster edge probability q. We focus on the sparse case, i.e. p, q = O(1/n), which is practically more relevant and also mathematically more challenging. A conjecture of Decelle, Krzakala, Moore and Zdeborova, based on ideas from statistical physics, predicted a specific threshold for clustering. The negative direction of the conjecture was proved by Mossel, Neeman and Sly (2012), and more recently the positive direction was proven independently by Massoulie and Mossel, Neeman, and Sly. In many real network clustering problems, nodes contain information as well. We study the interplay between node and network information in clustering by studying a labeled block model, where in addition to the edge information, the true cluster labels of a small fraction of the nodes are revealed. In the case of two clusters, we show that below the threshold, a small amount of node information does not affect recovery. On the other hand, we show that for any small amount of information efficient local clustering is achievable as long as the number of clusters is sufficiently large (as a function of the amount of revealed information).

In this work, we achieve gap amplification for the Small-Set Expansion problem. Specifically, we show that an instance of the Small-Set Expansion Problem with completeness epsilon and soundness 1/2 is at least as difficult as Small-Set Expansion with completeness epsilon and soundness f(epsilon), for any function f(epsilon) which grows faster than (epsilon)^(1/2). We achieve this amplification via random walks--the output graph corresponds to taking random walks on the original graph. An interesting feature of our reduction is that unlike gap amplification via parallel repetition, the size of the instances (number of vertices) produced by the reduction remains the same.