Search

Universality, namely distributional invariance, is a well-known property for many random structures. For example it is known to hold for a broad range of variational problems with random input. Much less is known about the universality of the performance of specific algorithms for solving such variational problems. Namely, do algorithms tuned to specific variational tasks produce the same asymptotic answer regardless of the underlying distribution? In this paper we show that the answer is yes for a class of models, which includes spin glass models and constraint satisfaction problems on sparse graphs, provided that an algorithm can be coded as a low-degree polynomial (LDP). We illustrate this specifically for the case of the Max-Cut problem in sparse Erd\"os-R\'enyi graph $\mathbb{G}(n, d/n)$. We use the fact that the Approximate Message Passing (AMP) algorithm, which is an effective algorithm for finding near-ground state of the Sherrington-Kirkpatrick (SK) model, is well approximated by an LDP. We then establish our main universality result: the performance of the LDP based algorithms exhibiting certain connectivity property, is the same in the mean-field (SK) and in the random graph $\mathbb{G}(n, d/n)$ setting, up to an appropriate rescaling. The main technical challenge which we address in this paper is showing that the output of the LDP algorithm on $\mathbb{G}(n, d/n)$ is truly discrete, namely it is close to the set of points in the binary cube.

Preparing thermal (Gibbs) states is a common task in physics and computer science. Recent algorithms mimic cooling via system-bath coupling, where the cost is determined by mixing time, akin to classical Metropolis-like algorithms. However, few methods exist to demonstrate slow mixing in quantum systems, unlike the well-established classical tools for systems like the Ising model and constraint satisfaction problems. We present a quantum generalization of these tools through a generic bottleneck lemma that implies slow mixing in quantum systems. This lemma focuses on quantum measures of distance, analogous to the classical Hamming distance but rooted in uniquely quantum principles and quantified either through Bohr spectrum jumps or operator locality. Using our bottleneck lemma, we establish unconditional lower bounds on the mixing times of Gibbs samplers for several families of Hamiltonians at low temperatures. For classical Hamiltonians with mixing time lower bounds $T_\mathrm{mix} = \exp[\Omega(n^\alpha)]$, we prove that quantum Gibbs samplers also have $T_\mathrm{mix} = \exp[\Omega(n^\alpha)]$. This applies to models like random $K$-SAT instances and spin glasses. For stabilizer Hamiltonians, we provide a concise proof of exponential lower bounds $T_\mathrm{mix} = \exp[\Omega(n)]$ on mixing times of good $n$-qubit stabilizer codes at low constant temperature. Finally, we consider constant-degree classical Hamiltonians and show how to lift classical slow mixing results in the presence of a transverse field using Poisson Feynman-Kac techniques. We show generic results for models with linear free energy barriers, and we demonstrate that our techniques extend to models with sublinear free energy barriers by proving $T_\mathrm{mix} = \exp[n^{1/2-o(1)}]$ for the ferromagnetic 2D transverse field Ising model., Comment: 59 pages. Arxiv abstract shortened. Fixed error in v1 for non-commuting results

We show that two related classes of algorithms, stable algorithms and Boolean circuits with bounded depth, cannot produce an approximate sample from the uniform measure over the set of solutions to the symmetric binary perceptron model at any constraint-to-variable density. This result is in contrast to the question of finding \emph{a} solution to the same problem, where efficient (and stable) algorithms are known to succeed at sufficiently low density. This result suggests that the solutions found efficiently -- whenever this task is possible -- must be highly atypical, and therefore provides an example of a problem where search is efficiently possible but approximate sampling from the set of solutions is not, at least within these two classes of algorithms., Comment: 18 pages

We consider the problem of estimating the ground state energy of quantum $p$-local spin glass random Hamiltonians, the quantum analogues of widely studied classical spin glass models. Our main result shows that the maximum energy achievable by product states has a well-defined limit (for even $p$) as $n\to\infty$ and is $E_{\text{product}}^\ast=\sqrt{2 \log p}$ in the limit of large $p$. This value is interpreted as the maximal energy of a much simpler so-called Random Energy Model, widely studied in the setting of classical spin glasses. The proof of the limit existing follows from an extension of Fekete's Lemma after we demonstrate near super-additivity of the (normalized) quenched free energy. The proof of the value follows from a second moment method on the number of states achieving a given energy when restricting to an $\epsilon$-net of product states. Furthermore, we relate the maximal energy achieved over all states to a $p$-dependent constant $\gamma\left(p\right)$, which is defined by the degree of violation of a certain asymptotic independence ansatz over graph matchings. We show that the maximal energy achieved by all states $E^\ast\left(p\right)$ in the limit of large $n$ is at most $\sqrt{\gamma\left(p\right)}E_{\text{product}}^\ast$. We also prove using Lindeberg's interpolation method that the limiting $E^\ast\left(p\right)$ is robust with respect to the choice of the randomness and, for instance, also applies to the case of sparse random Hamiltonians. This robustness in the randomness extends to a wide range of random Hamiltonian models including SYK and random quantum max-cut., Comment: 54 pages, 0 figures. arXiv admin note: substantial text overlap with arXiv:2309.11709

We design a Quasi-Polynomial time deterministic approximation algorithm for computing the integral of a multi-dimensional separable function, supported by some underlying hyper-graph structure, appropriately defined. Equivalently, our integral is the partition function of a graphical model with continuous potentials. While randomized algorithms for high-dimensional integration are widely known, deterministic counterparts generally do not exist. We use the correlation decay method applied to the Riemann sum of the function to produce our algorithm. For our method to work, we require that the domain is bounded and the hyper-edge potentials are positive and bounded on the domain. We further assume that upper and lower bounds on the potentials separated by a multiplicative factor of $1 + O(1/\Delta^2)$, where $\Delta$ is the maximum degree of the graph. When $\Delta = 3$, our method works provided the upper and lower bounds are separated by a factor of at most $1.0479$. To the best of our knowledge, our algorithm is the first deterministic algorithm for high-dimensional integration of a continuous function, apart from the case of trivial product form distributions.

We construct a quasi-polynomial time deterministic approximation algorithm for computing the volume of an independent set polytope with restrictions. Randomized polynomial time approximation algorithms for computing the volume of a convex body have been known now for several decades, but the corresponding deterministic counterparts are not available, and our algorithm is the first of this kind. The class of polytopes for which our algorithm applies arises as linear programming relaxation of the independent set problem with the additional restriction that each variable takes value in the interval $[0,1-\alpha]$ for some $\alpha<1/2$. (We note that the $\alpha\ge 1/2$ case is trivial). We use the correlation decay method for this problem applied to its appropriate and natural discretization. The method works provided $\alpha> 1/2-O(1/\Delta^2)$, where $\Delta$ is the maximum degree of the graph. When $\Delta=3$ (the sparsest non-trivial case), our method works provided $0.488<\alpha<0.5$. Interestingly, the interpolation method, which is based on analyzing complex roots of the associated partition functions, fails even in the trivial case when the underlying graph is a singleton.

We show that sharp thresholds for Boolean functions directly imply average-case circuit lower bounds. More formally we show that any Boolean function exhibiting a sharp enough threshold at \emph{arbitrary} critical density cannot be computed by Boolean circuits of bounded depth and polynomial size. We also prove a partial converse: if a monotone graph invariant Boolean function does not have a sharp threshold then it can be computed on average by a Boolean circuit of bounded depth and polynomial size. Our general result also implies new average-case bounded depth circuit lower bounds in a variety of settings. (a) ($k$-cliques) For $k=\Theta(n)$, we prove that any circuit of depth $d$ deciding the presence of a size $k$ clique in a random graph requires exponential-in-$n^{\Theta(1/d)}$ size. (b)(random 2-SAT) We prove that any circuit of depth $d$ deciding the satisfiability of a random 2-SAT formula requires exponential-in-$n^{\Theta(1/d)}$ size. To the best of our knowledge, this is the first bounded depth circuit lower bound for random $k$-SAT for any value of $k \geq 2.$ Our results also provide the first rigorous lower bound in agreement with a conjectured, but debated, "computational hardness" of random $k$-SAT around its satisfiability threshold. (c)(Statistical estimation -- planted $k$-clique) Over the recent years, multiple statistical estimation problems have also been proven to exhibit a "statistical" sharp threshold, called the All-or-Nothing (AoN) phenomenon. We show that AoN also implies circuit lower bounds for statistical problems. As a simple corollary of that, we prove that any circuit of depth $d$ that solves to information-theoretic optimality a "dense" variant of the celebrated planted $k$-clique problem requires exponential-in-$n^{\Theta(1/d)}$ size., Comment: Added a partial converse result, showing that for monotone graph properties if they do not have a sharp threshold then they are computed on average by a bounded depth and polynomial size circuit

We consider the problem of estimating the maximal energy of quantum $p$-local spin glass random Hamiltonians, the quantum analogues of widely studied classical spin glass models. Denoting by $E^*(p)$ the (appropriately normalized) maximal energy in the limit of a large number of qubits $n$, we show that $E^*(p)$ approaches $\sqrt{2\log 6}$ as $p$ increases. This value is interpreted as the maximal energy of a much simpler so-called Random Energy Model, widely studied in the setting of classical spin glasses. Our most notable and (arguably) surprising result proves the existence of near-maximal energy states which are product states, and thus not entangled. Specifically, we prove that with high probability as $n\to\infty$, for any $E

We study the Ising pure $p$-spin model for large $p$. We investigate the landscape of the Hamiltonian of this model. We show that for any $\gamma>0$ and any large enough $p$, the model exhibits an intricate geometrical property known as the multi Overlap Gap Property above the energy value $\gamma\sqrt{2\ln 2}$. We then show that for any inverse temperature $\sqrt{\ln 2}<\beta<\sqrt{2\ln 2}$ and any large $p$, the model exhibits shattering: w.h.p. as $n\to\infty$, there exists exponentially many well-separated clusters such that (a) each cluster has exponentially small Gibbs mass, and (b) the clusters collectively contain all but a vanishing fraction of Gibbs mass. Moreover, these clusters consist of configurations with energy near $\beta$. Range of temperatures for which shattering occurs is within the replica symmetric region. To the best of our knowledge, this is the first shattering result regarding the Ising $p$-spin models. Our proof is elementary, and in particular based on simple applications of the first and the second moment methods.

Recently graph neural network (GNN) based algorithms were proposed to solve a variety of combinatorial optimization problems, including Maximum Cut problem, Maximum Independent Set problem and similar other problems~\cite{schuetz2022combinatorial},\cite{schuetz2022graph}. The publication~\cite{schuetz2022combinatorial} stirred a debate whether GNN based method was adequately benchmarked against best prior methods. In particular, critical commentaries~\cite{angelini2023modern} and~\cite{boettcher2023inability} point out that simple greedy algorithm performs better than GNN in the setting of random graphs, and in fact stronger algorithmic performance can be reached with more sophisticated methods. A response from the authors~\cite{schuetz2023reply} pointed out that GNN performance can be improved further by tuning up the parameters better. We do not intend to discuss the merits of arguments and counter-arguments in~\cite{schuetz2022combinatorial},\cite{angelini2023modern},\cite{boettcher2023inability},\cite{schuetz2023reply}. Rather in this note we establish a fundamental limitation for running GNN on random graphs considered in these references, for a broad range of choices of GNN architecture. These limitations arise from the presence of the Overlap Gap Property (OGP) phase transition, which is a barrier for many algorithms, both classical and quantum. As we demonstrate in this paper, it is also a barrier to GNN due to its local structure. We note that at the same time known algorithms ranging from simple greedy algorithms to more sophisticated algorithms based on message passing, provide best results for these problems \emph{up to} the OGP phase transition. This leaves very little space for GNN to outperform the known algorithms, and based on this we side with the conclusions made in~\cite{angelini2023modern} and~\cite{boettcher2023inability}., Comment: 5 pages

We provide a unified analysis of stable local optima of Ising spins with Hamiltonians having pair-wise interactions and partitions in random weighted graphs where a large number of vertices possess sufficient single spin-flip stability. For graphs, we consider partitions on random graphs where almost all vertices possess sufficient appropriately defined friendliness/unfriendliness. For spin glasses, we characterize approximate local optima having almost all local magnetic fields of sufficiently large magnitude. For $n$ nodes, as $n \rightarrow \infty$, we prove that the maximum number of vertices possessing such stability undergoes a phase transition from $n-o(n)$ to $n-\Theta(n)$ around a certain value of the stability, proving a conjecture from Behrens et al. [2022].Through a universality argument, we further prove that such a phase transition occurs around the same value of the stability for different choices of interactions, specifically ferromagnetic and anti-ferromagnetic, for sparse graphs, as $n \rightarrow \infty$ in the large degree limit. Furthermore, we show that after appropriate re-scaling, the same value of the threshold characterises such a phase transition for the case of fully connected spin-glass models. Our results also allow the characterization of possible energy values of maximally stable approximate local optima. Our work extends and proves seminal results in statistical physics related to metastable states, in particular, the work of Bray and Moore [1981].

In an important recent development, Anshu, Breuckmann, and Nirkhe [ABN22] resolved positively the so-called No Low-Energy Trivial State (NLTS) conjecture by Freedman and Hastings. The conjecture postulated the existence of linear-size local Hamiltonians on n qubit systems for which no near-ground state can be prepared by a shallow (sublogarithmic depth) circuit. The construction in [ABN22] is based on recently developed good quantum codes. Earlier results in this direction included the constructions of the so-called Combinatorial NLTS -- a weaker version of NLTS -- where a state is defined to have low energy if it violates at most a vanishing fraction of the Hamiltonian terms [AB22]. These constructions were also based on codes. In this paper we provide a "non-code" construction of a class of Hamiltonians satisfying the Combinatorial NLTS. The construction is inspired by one in [AB22], but our proof uses the complex solution space geometry of random K-SAT instead of properties of codes. Specifically, it is known that above a certain clause-to-variables density the set of satisfying assignments of random K-SAT exhibits an overlap gap property, which implies that it can be partitioned into exponentially many clusters each constituting at most an exponentially small fraction of the total set of satisfying solutions. We establish a certain robust version of this clustering property for the space of near-satisfying assignments and show that for our constructed Hamiltonians every combinatorial near-ground state induces a near-uniform distribution supported by this set. Standard arguments then are used to show that such distributions cannot be prepared by quantum circuits with depth o(log n). Since the clustering property is exhibited by many random structures, including proper coloring and maximum cut, we anticipate that our approach is extendable to these models as well., Comment: 19 pages, 2 figures, Quantum submission

The semi-random graph process is a single player game in which the player is initially presented an empty graph on $n$ vertices. In each round, a vertex $u$ is presented to the player independently and uniformly at random. The player then adaptively selects a vertex $v$, and adds the edge $uv$ to the graph. For a fixed monotone graph property, the objective of the player is to force the graph to satisfy this property with high probability in as few rounds as possible. In this paper, we investigate the following three properties: containing a complete graph of order $k$, having the chromatic number at least $k$, and not having an independent set of size at least $k$.

For many computational problems involving randomness, intricate geometric features of the solution space have been used to rigorously rule out powerful classes of algorithms. This is often accomplished through the lens of the multi Overlap Gap Property ($m$-OGP), a rigorous barrier against algorithms exhibiting input stability. In this paper, we focus on the algorithmic tractability of two models: (i) discrepancy minimization, and (ii) the symmetric binary perceptron (\texttt{SBP}), a random constraint satisfaction problem as well as a toy model of a single-layer neural network. Our first focus is on the limits of online algorithms. By establishing and leveraging a novel geometrical barrier, we obtain sharp hardness guarantees against online algorithms for both the \texttt{SBP} and discrepancy minimization. Our results match the best known algorithmic guarantees, up to constant factors. Our second focus is on efficiently finding a constant discrepancy solution, given a random matrix $\mathcal{M}\in\mathbb{R}^{M\times n}$. In a smooth setting, where the entries of $\mathcal{M}$ are i.i.d. standard normal, we establish the presence of $m$-OGP for $n=\Theta(M\log M)$. Consequently, we rule out the class of stable algorithms at this value. These results give the first rigorous evidence towards a conjecture of Altschuler and Niles-Weed~\cite[Conjecture~1]{altschuler2021discrepancy}. Our methods use the intricate geometry of the solution space to prove tight hardness results for online algorithms. The barrier we establish is a novel variant of the $m$-OGP. Furthermore, it regards $m$-tuples of solutions with respect to correlated instances, with growing values of $m$, $m=\omega(1)$. Importantly, our results rule out online algorithms succeeding even with an exponentially small probability.

We consider the problem of estimating the edge density of densest $K$-node subgraphs of an Erd\"os-R\'{e}nyi graph $\mathbb{G}(n,1/2)$. The problem is well-understood in the regime $K=\Theta(\log n)$ and in the regime $K=\Theta(n)$. In the former case it can be reduced to the problem of estimating the size of largest cliques, and its extensions. In the latter case the full answer is known up to the order $n^{3\over 2}$ using sophisticated methods from the theory of spin glasses. The intermediate case $K=n^\alpha, \alpha\in (0,1)$ however is not well studied and this is our focus. We establish that that in this regime the density (that is the maximum number of edges supported by any $K$-node subgraph) is ${1\over 4}K^2+{1+o(1)\over 2}K^{3\over 2}\sqrt{\log (n/K)}$, w.h.p. as $n\to\infty$, and provide more refined asymptotics under the $o(\cdot)$, for various ranges of $\alpha$. This extends earlier similar results where this asymptotics was confirmed only when $\alpha$ is a small constant. We extend our results to the case of ''weighted'' graphs, when the weights have either Gaussian or arbitrary sub-Gaussian distributions. The proofs are based on the second moment method combined with concentration bounds, the Borell-TIS inequality for the Gaussian case and the Talagrand's inequality for the case of distributions with bounded support (including the $\mathbb{G}(n,1/2)$ case). The case of general distribution is treated using a novel symmetrized version of the Lindeberg argument, which reduces the general case to the Gaussian case. Finally, using the results above we conduct the landscape analysis of the related Hidden Clique Problem, and establish that it exhibits an overlap gap property when the size of the clique is $O(n^{2\over 3})$, confirming a hypothesis stated in a previous related work., Comment: 63 pages, 1 figure

In this review article, we discuss connections between the physics of disordered systems, phase transitions in inference problems, and computational hardness. We introduce two models representing the behavior of glassy systems, the spiked tensor model and the generalized linear model. We discuss the random (non-planted) versions of these problems as prototypical optimization problems, as well as the planted versions (with a hidden solution) as prototypical problems in statistical inference and learning. Based on ideas from physics, many of these problems have transitions where they are believed to jump from easy (solvable in polynomial time) to hard (requiring exponential time). We discuss several emerging ideas in theoretical computer science and statistics that provide rigorous evidence for hardness by proving that large classes of algorithms fail in the conjectured hard regime. This includes the overlap gap property, a particular mathematization of clustering or dynamical symmetry-breaking, which can be used to show that many algorithms that are local or robust to changes in their input fail. We also discuss the sum-of-squares hierarchy, which places bounds on proofs or algorithms that use low-degree polynomials such as standard spectral methods and semidefinite relaxations, including the Sherrington-Kirkpatrick model. Throughout the manuscript, we present connections to the physics of disordered systems and associated replica symmetry breaking properties., Comment: 42 pages

The Quantum Approximate Optimization Algorithm (QAOA) is a general purpose quantum algorithm designed for combinatorial optimization. We analyze its expected performance and prove concentration properties at any constant level (number of layers) on ensembles of random combinatorial optimization problems in the infinite size limit. These ensembles include mixed spin models and Max-$q$-XORSAT on sparse random hypergraphs. Our analysis can be understood via a saddle-point approximation of a sum-over-paths integral. This is made rigorous by proving a generalization of the multinomial theorem, which is a technical result of independent interest. We then show that the performance of the QAOA at constant levels for the pure $q$-spin model matches asymptotically the ones for Max-$q$-XORSAT on random sparse Erd\H{o}s-R\'{e}nyi hypergraphs and every large-girth regular hypergraph. Through this correspondence, we establish that the average-case value produced by the QAOA at constant levels is bounded away from optimality for pure $q$-spin models when $q\ge 4$ and is even. This limitation gives a hardness of approximation result for quantum algorithms in a new regime where the whole graph is seen., Comment: 13+47 pages, updated introduction

The symmetric binary perceptron ($\texttt{SBP}$) exhibits a dramatic statistical-to-computational gap: the densities at which known efficient algorithms find solutions are far below the threshold for the existence of solutions. Furthermore, the $\texttt{SBP}$ exhibits a striking structural property: at all positive constraint densities almost all of its solutions are 'totally frozen' singletons separated by large Hamming distance \cite{perkins2021frozen,abbe2021proof}. This suggests that finding a solution to the $\texttt{SBP}$ may be computationally intractable. At the same time, the $\texttt{SBP}$ does admit polynomial-time search algorithms at low enough densities. A conjectural explanation for this conundrum was put forth in \cite{baldassi2020clustering}: efficient algorithms succeed in the face of freezing by finding exponentially rare clusters of large size. However, it was discovered recently that such rare large clusters exist at all subcritical densities, even at those well above the limits of known efficient algorithms \cite{abbe2021binary}. Thus the driver of the statistical-to-computational gap exhibited by this model remains a mystery. In this paper, we conduct a different landscape analysis to explain the algorithmic tractability of this problem. We show that at high enough densities the $\texttt{SBP}$ exhibits the multi Overlap Gap Property ($m-$OGP), an intricate geometrical property known to be a rigorous barrier for large classes of algorithms. Our analysis shows that the $m-$OGP threshold (a) is well below the satisfiability threshold; and (b) matches the best known algorithmic threshold up to logarithmic factors as $m\to\infty$. We then prove that the $m-$OGP rules out the class of stable algorithms for the $\texttt{SBP}$ above this threshold. We conjecture that the $m \to \infty$ limit of the $m$-OGP threshold marks the algorithmic threshold for the problem.

We consider the problem of finding a near ground state of a $p$-spin model with Rademacher couplings by means of a low-depth circuit. As a direct extension of the authors' recent work [Gamarnik, Jagannath, Wein 2020], we establish that any poly-size $n$-output circuit that produces a spin assignment with objective value within a certain constant factor of optimality, must have depth at least $\log n/(2\log\log n)$ as $n$ grows. This is stronger than the known state of the art bounds of the form $\Omega(\log n/(k(n)\log\log n))$ for similar combinatorial optimization problems, where $k(n)$ depends on the optimality value. For example, for the largest clique problem $k(n)$ corresponds to the square of the size of the clique [Rossman 2010]. At the same time our results are not quite comparable since in our case the circuits are required to produce a solution itself rather than solving the associated decision problem. As in our earlier work, the approach is based on the overlap gap property (OGP) exhibited by random $p$-spin models, but the derivation of the circuit lower bound relies further on standard facts from Fourier analysis on the Boolean cube, in particular the Linial-Mansour-Nisan Theorem. To the best of our knowledge, this is the first instance when methods from spin glass theory have ramifications for circuit complexity., Comment: 14 pages

The problem of optimizing over random structures emerges in many areas of science and engineering, ranging from statistical physics to machine learning and artificial intelligence. For many such structures finding optimal solutions by means of fast algorithms is not known and often is believed not possible. At the same time the formal hardness of these problems in form of say complexity-theoretic $NP$-hardness is lacking. In this introductory article a new approach for algorithmic intractability in random structures is described, which is based on the topological disconnectivity property of the set of pair-wise distances of near optimal solutions, called the Overlap Gap Property. The article demonstrates how this property a) emerges in most models known to exhibit an apparent algorithmic hardness b) is consistent with the hardness/tractability phase transition for many models analyzed to the day, and importantly c) allows to mathematically rigorously rule out large classes of algorithms as potential contenders, in particular the algorithms exhibiting the input stability (insensitivity)., Comment: 26 pages, 6 figures, 1 table

We consider the problem of finding a two-layer neural network with sigmoid, rectified linear unit (ReLU), or binary step activation functions that "fits" a training data set as accurately as possible as quantified by the training error; and study the following question: \emph{does a low training error guarantee that the norm of the output layer (outer norm) itself is small?} We answer affirmatively this question for the case of non-negative output weights. Using a simple covering number argument, we establish that under quite mild distributional assumptions on the input/label pairs; any such network achieving a small training error on polynomially many data necessarily has a well-controlled outer norm. Notably, our results (a) have a polynomial (in $d$) sample complexity, (b) are independent of the number of hidden units (which can potentially be very high), (c) are oblivious to the training algorithm; and (d) require quite mild assumptions on the data (in particular the input vector $X\in\mathbb{R}^d$ need not have independent coordinates). We then leverage our bounds to establish generalization guarantees for such networks through \emph{fat-shattering dimension}, a scale-sensitive measure of the complexity class that the network architectures we investigate belong to. Notably, our generalization bounds also have good sample complexity (polynomials in $d$ with a low degree), and are in fact near-linear for some important cases of interest., Comment: 34 pages. Some of the results in the present paper are significantly strengthened versions of certain results appearing in arXiv:2003.10523

We consider the algorithmic problem of finding a near-optimal solution for the number partitioning problem (NPP). The NPP appears in many applications, including the design of randomized controlled trials, multiprocessor scheduling, and cryptography; and is also of theoretical significance. It possesses a so-called statistical-to-computational gap: when its input $X$ has distribution $\mathcal{N}(0,I_n)$, its optimal value is $\Theta(\sqrt{n}2^{-n})$ w.h.p.; whereas the best polynomial-time algorithm achieves an objective value of only $2^{-\Theta(\log^2 n)}$, w.h.p. In this paper, we initiate the study of the nature of this gap. Inspired by insights from statistical physics, we study the landscape of NPP and establish the presence of the Overlap Gap Property (OGP), an intricate geometric property which is known to be a rigorous evidence of an algorithmic hardness for large classes of algorithms. By leveraging the OGP, we establish that (a) any sufficiently stable algorithm, appropriately defined, fails to find a near-optimal solution with energy below $2^{-\omega(n \log^{-1/5} n)}$; and (b) a very natural MCMC dynamics fails to find near-optimal solutions. Our simulations suggest that the state of the art algorithm achieving $2^{-\Theta(\log^2 n)}$ is indeed stable, but formally verifying this is left as an open problem. OGP regards the overlap structure of $m-$tuples of solutions achieving a certain objective value. When $m$ is constant we prove the presence of OGP in the regime $2^{-\Theta(n)}$, and the absence of it in the regime $2^{-o(n)}$. Interestingly, though, by considering overlaps with growing values of $m$ we prove the presence of the OGP up to the level $2^{-\omega(\sqrt{n\log n})}$. Our proof of the failure of stable algorithms at values $2^{-\omega(n \log^{-1/5} n)}$ employs methods from Ramsey Theory from the extremal combinatorics, and is of independent interest., Comment: 84 pages, 3 figures

Absence of (complex) zeros property is at the heart of the interpolation method developed by Barvinok \cite{barvinok2017combinatorics} for designing deterministic approximation algorithms for various graph counting and computing partition functions problems. Earlier methods for solving the same problem include the one based on the correlation decay property. Remarkably, the classes of graphs for which the two methods apply sometimes coincide or nearly coincide. In this paper we show that this is more than just a coincidence. We establish that if the interpolation method is valid for a family of graphs satisfying the self-reducibility property, then this family exhibits a form of correlation decay property which is asymptotic Strong Spatial Mixing (SSM) at distances $\omega(\log n)$, where $n$ is the number of nodes of the graph. This applies in particular to amenable graphs, such as graphs which are finite subsets of lattices. Our proof is based on a certain graph polynomial representation of the associated partition function. This representation is at the heart of the design of the polynomial time algorithms underlying the interpolation method itself. We conjecture that our result holds for all, and not just amenable graphs., Comment: 27 pages

We consider a heterogeneous distributed service system, consisting of $n$ servers with unknown and possibly different processing rates. Jobs with unit mean and independent processing times arrive as a renewal process of rate $\lambda n$, with $0<\lambda<1$, to the system. Incoming jobs are immediately dispatched to one of several queues associated with the $n$ servers. We assume that the dispatching decisions are made by a central dispatcher endowed with a finite memory, and with the ability to exchange messages with the servers. We study the fundamental resource requirements (memory bits and message exchange rate) in order for a dispatching policy to be {\bf maximally stable}, i.e., stable whenever the processing rates are such that the arrival rate is less than the total available processing rate. First, for the case of Poisson arrivals and exponential service times, we present a policy that is maximally stable while using a positive (but arbitrarily small) message rate, and $\log_2(n)$ bits of memory. Second, we show that within a certain broad class of policies, a dispatching policy that exchanges $o\big(n^2\big)$ messages per unit of time, and with $o(\log(n))$ bits of memory, cannot be maximally stable. Thus, as long as the message rate is not too excessive, a logarithmic memory is necessary and sufficient for maximal stability., Comment: arXiv admin note: text overlap with arXiv:1807.02882

In a multi-index model with $k$ index vectors, the input variables are transformed by taking inner products with the index vectors. A transfer function $f: \mathbb{R}^k \to \mathbb{R}$ is applied to these inner products to generate the output. Thus, multi-index models are a generalization of linear models. In this paper, we consider monotone multi-index models. Namely, the transfer function is assumed to be coordinate-wise monotone. The monotone multi-index model therefore generalizes both linear regression and isotonic regression, which is the estimation of a coordinate-wise monotone function. We consider the case of nonnegative index vectors. We provide an algorithm based on integer programming for the estimation of monotone multi-index models, and provide guarantees on the $L_2$ loss of the estimated function relative to the ground truth., Comment: 20 pages

The Quantum Approximate Optimization Algorithm can be applied to search problems on graphs with a cost function that is a sum of terms corresponding to the edges. When conjugating an edge term, the QAOA unitary at depth p produces an operator that depends only on the subgraph consisting of edges that are at most p away from the edge in question. On random d-regular graphs, with d fixed and with p a small constant time log n, these neighborhoods are almost all trees and so the performance of the QAOA is determined only by how it acts on an edge in the middle of tree. Both bipartite random d-regular graphs and general random d-regular graphs locally are trees so the QAOA's performance is the same on these two ensembles. Using this we can show that the QAOA with $(d-1)^{2p} < n^A$ for any $A<1$, can only achieve an approximation ratio of 1/2 for Max-Cut on bipartite random d-regular graphs for d large. For Maximum Independent Set, in the same setting, the best approximation ratio is a d-dependent constant that goes to 0 as d gets big., Comment: 6 pages, no figures

We consider the problem of finding nearly optimal solutions of optimization problems with random objective functions. Two concrete problems we consider are (a) optimizing the Hamiltonian of a spherical or Ising $p$-spin glass model, and (b) finding a large independent set in a sparse Erd\H{o}s-R\'{e}nyi graph. The following families of algorithms are considered: (a) low-degree polynomials of the input; (b) low-depth Boolean circuits; (c) the Langevin dynamics algorithm. We show that these families of algorithms fail to produce nearly optimal solutions with high probability. For the case of Boolean circuits, our results improve the state-of-the-art bounds known in circuit complexity theory (although we consider the search problem as opposed to the decision problem). Our proof uses the fact that these models are known to exhibit a variant of the overlap gap property (OGP) of near-optimal solutions. Specifically, for both models, every two solutions whose objectives are above a certain threshold are either close or far from each other. The crux of our proof is that the classes of algorithms we consider exhibit a form of stability. We show by an interpolation argument that stable algorithms cannot overcome the OGP barrier. The stability of Langevin dynamics is an immediate consequence of the well-posedness of stochastic differential equations. The stability of low-degree polynomials and Boolean circuits is established using tools from Gaussian and Boolean analysis -- namely hypercontractivity and total influence, as well as a novel lower bound for random walks avoiding certain subsets. In the case of Boolean circuits, the result also makes use of Linal-Mansour-Nisan's classical theorem. Our techniques apply more broadly to low influence functions and may apply more generally., Comment: 41 pages; v1 is the conference paper "Low-Degree Hardness of Random Optimization Problems" (FOCS 2020); v2 is a journal version which adds circuit lower bounds for max independent set, based on ideas from our note arXiv:2109.01342

The Quantum Approximate Optimization Algorithm can naturally be applied to combinatorial search problems on graphs. The quantum circuit has p applications of a unitary operator that respects the locality of the graph. On a graph with bounded degree, with p small enough, measurements of distant qubits in the state output by the QAOA give uncorrelated results. We focus on finding big independent sets in random graphs with dn/2 edges keeping d fixed and n large. Using the Overlap Gap Property of almost optimal independent sets in random graphs, and the locality of the QAOA, we are able to show that if p is less than a d-dependent constant times log n, the QAOA cannot do better than finding an independent set of size .854 times the optimal for d large. Because the logarithm is slowly growing, even at one million qubits we can only show that the algorithm is blocked if p is in single digits. At higher p the algorithm "sees" the whole graph and we have no indication that performance is limited., Comment: 19 pages, no figures

In the context of neural network models, overparametrization refers to the phenomena whereby these models appear to generalize well on the unseen data, even though the number of parameters significantly exceeds the sample sizes, and the model perfectly fits the in-training data. A conventional explanation of this phenomena is based on self-regularization properties of algorithms used to train the data. In this paper we prove a series of results which provide a somewhat diverging explanation. Adopting a teacher/student model where the teacher network is used to generate the predictions and student network is trained on the observed labeled data, and then tested on out-of-sample data, we show that any student network interpolating the data generated by a teacher network generalizes well, provided that the sample size is at least an explicit quantity controlled by data dimension and approximation guarantee alone, regardless of the number of internal nodes of either teacher or student network. Our claim is based on approximating both teacher and student networks by polynomial (tensor) regression models with degree depending on the desired accuracy and network depth only. Such a parametrization notably does not depend on the number of internal nodes. Thus a message implied by our results is that parametrizing wide neural networks by the number of hidden nodes is misleading, and a more fitting measure of parametrization complexity is the number of regression coefficients associated with tensorized data. In particular, this somewhat reconciles the generalization ability of neural networks with more classical statistical notions of data complexity and generalization bounds. Our empirical results on MNIST and Fashion-MNIST datasets indeed confirm that tensorized regression achieves a good out-of-sample performance, even when the degree of the tensor is at most two., Comment: 59 pages, 3 figures

We consider the teacher-student setting of learning shallow neural networks with quadratic activations and planted weight matrix $W^*\in\mathbb{R}^{m\times d}$, where $m$ is the width of the hidden layer and $d\le m$ is the data dimension. We study the optimization landscape associated with the empirical and the population squared risk of the problem. Under the assumption the planted weights are full-rank we obtain the following results. First, we establish that the landscape of the empirical risk admits an "energy barrier" separating rank-deficient $W$ from $W^*$: if $W$ is rank deficient, then its risk is bounded away from zero by an amount we quantify. We then couple this result by showing that, assuming number $N$ of samples grows at least like a polynomial function of $d$, all full-rank approximate stationary points of the empirical risk are nearly global optimum. These two results allow us to prove that gradient descent, when initialized below the energy barrier, approximately minimizes the empirical risk and recovers the planted weights in polynomial-time. Next, we show that initializing below this barrier is in fact easily achieved when the weights are randomly generated under relatively weak assumptions. We show that provided the network is sufficiently overparametrized, initializing with an appropriate multiple of the identity suffices to obtain a risk below the energy barrier. At a technical level, the last result is a consequence of the semicircle law for the Wishart ensemble and could be of independent interest. Finally, we study the minimizers of the empirical risk and identify a simple necessary and sufficient geometric condition on the training data under which any minimizer has necessarily zero generalization error. We show that as soon as $N\ge N^*=d(d+1)/2$, randomly generated data enjoys this geometric condition almost surely, while that ceases to be true if $N

We consider the algorithmic problem of finding a near ground state (near optimal solution) of a $p$-spin model. We show that for a class of algorithms broadly defined as Approximate Message Passing (AMP), the presence of the Overlap Gap Property (OGP), appropriately defined, is a barrier. We conjecture that when $p\ge 4$ the model does indeed exhibits OGP (and prove it for the space of binary solutions). Assuming the validity of this conjecture, as an implication, the AMP fails to find near ground states in these models, per our result. We extend our result to the problem of finding pure states by means of Thouless, Anderson and Palmer (TAP) based iterations, which is yet another example of AMP type algorithms. We show that such iterations fail to find pure states approximately, subject to the conjecture that the space of pure states exhibits the OGP, appropriately stated, when $p\ge 4$., Comment: 27 pages

We focus on the high-dimensional linear regression problem, where the algorithmic goal is to efficiently infer an unknown feature vector $\beta^*\in\mathbb{R}^p$ from its linear measurements, using a small number $n$ of samples. Unlike most of the literature, we make no sparsity assumption on $\beta^*$, but instead adopt a different regularization: In the noiseless setting, we assume $\beta^*$ consists of entries, which are either rational numbers with a common denominator $Q\in\mathbb{Z}^+$ (referred to as $Q$-rationality); or irrational numbers supported on a rationally independent set of bounded cardinality, known to learner; collectively called as the mixed-support assumption. Using a novel combination of the PSLQ integer relation detection, and LLL lattice basis reduction algorithms, we propose a polynomial-time algorithm which provably recovers a $\beta^*\in\mathbb{R}^p$ enjoying the mixed-support assumption, from its linear measurements $Y=X\beta^*\in\mathbb{R}^n$ for a large class of distributions for the random entries of $X$, even with one measurement $(n=1)$. In the noisy setting, we propose a polynomial-time, lattice-based algorithm, which recovers a $\beta^*\in\mathbb{R}^p$ enjoying $Q$-rationality, from its noisy measurements $Y=X\beta^*+W\in\mathbb{R}^n$, even with a single sample $(n=1)$. We further establish for large $Q$, and normal noise, this algorithm tolerates information-theoretically optimal level of noise. We then apply these ideas to develop a polynomial-time, single-sample algorithm for the phase retrieval problem. Our methods address the single-sample $(n=1)$ regime, where the sparsity-based methods such as LASSO and Basis Pursuit are known to fail. Furthermore, our results also reveal an algorithmic connection between the high-dimensional linear regression problem, and the integer relation detection, randomized subset-sum, and shortest vector problems., Comment: 56 pages. Parts of the material of this manuscript were presented at NeurIPS 2018, and ISIT 2019. This submission subsumes the content of arXiv:1803.06716

We study support recovery for a $k \times k$ principal submatrix with elevated mean $\lambda/N$, hidden in an $N\times N$ symmetric mean zero Gaussian matrix. Here $\lambda>0$ is a universal constant, and we assume $k = N \rho$ for some constant $\rho \in (0,1)$. We establish that {there exists a constant $C>0$ such that} the MLE recovers a constant proportion of the hidden submatrix if $\lambda {\geq C} \sqrt{\frac{1}{\rho} \log \frac{1}{\rho}}$, {while such recovery is information theoretically impossible if $\lambda = o( \sqrt{\frac{1}{\rho} \log \frac{1}{\rho}} )$}. The MLE is computationally intractable in general, and in fact, for $\rho>0$ sufficiently small, this problem is conjectured to exhibit a \emph{statistical-computational gap}. To provide rigorous evidence for this, we study the likelihood landscape for this problem, and establish that for some $\varepsilon>0$ and $\sqrt{\frac{1}{\rho} \log \frac{1}{\rho} } \ll \lambda \ll \frac{1}{\rho^{1/2 + \varepsilon}}$, the problem exhibits a variant of the \emph{Overlap-Gap-Property (OGP)}. As a direct consequence, we establish that a family of local MCMC based algorithms do not achieve optimal recovery. Finally, we establish that for $\lambda > 1/\rho$, a simple spectral method recovers a constant proportion of the hidden submatrix., Comment: 42 pages, 1 figure

We consider the problem of estimating an unknown coordinate-wise monotone function given noisy measurements, known as the isotonic regression problem. Often, only a small subset of the features affects the output. This motivates the sparse isotonic regression setting, which we consider here. We provide an upper bound on the expected VC entropy of the space of sparse coordinate-wise monotone functions, and identify the regime of statistical consistency of our estimator. We also propose a linear program to recover the active coordinates, and provide theoretical recovery guarantees. We close with experiments on cancer classification, and show that our method significantly outperforms standard methods., Comment: 28 pages, 3 figures

In this paper we study the computational-statistical gap of the planted clique problem, where a clique of size $k$ is planted in an Erdos Renyi graph $G(n,\frac{1}{2})$ resulting in a graph $G\left(n,\frac{1}{2},k\right)$. The goal is to recover the planted clique vertices by observing $G\left(n,\frac{1}{2},k\right)$ . It is known that the clique can be recovered as long as $k \geq \left(2+\epsilon\right)\log n $ for any $\epsilon>0$, but no polynomial-time algorithm is known for this task unless $k=\Omega\left(\sqrt{n} \right)$. Following a statistical-physics inspired point of view as an attempt to understand this computational-statistical gap, we study the landscape of the "sufficiently dense" subgraphs of $G$ and their overlap with the planted clique. Using the first moment method, we study the densest subgraph problems for subgraphs with fixed, but arbitrary, overlap size with the planted clique, and provide evidence of a phase transition for the presence of Overlap Gap Property (OGP) at $k=\Theta\left(\sqrt{n}\right)$. OGP is a concept introduced originally in spin glass theory and known to suggest algorithmic hardness when it appears. We establish the presence of OGP when $k$ is a small positive power of $n$ by using a conditional second moment method. As our main technical tool, we establish the first, to the best of our knowledge, concentration results for the $K$-densest subgraph problem for the Erdos-Renyi model $G\left(n,\frac{1}{2}\right)$ when $K=n^{0.5-\epsilon}$ for arbitrary $\epsilon>0$. Finally, to study the OGP we employ a certain form of overparametrization, which is conceptually aligned with a large body of recent work in learning theory and optimization., Comment: 70 pages, 3 Figures. Added Figure 1 (phase diagram), and a new result proving that the OGP implies the failure of an MCMC family to recover the planted clique