Pruning and quantization techniques have been broadly successful in reducing the number of parameters needed for large neural networks, yet theoretical justification for their empirical success falls short. We consider a randomized greedy compression algorithm for pruning and quantization post-training and use it to rigorously show the existence of pruned/quantized subnetworks of multilayer perceptrons (MLPs) with competitive performance. We further extend our results to structured pruning of MLPs and convolutional neural networks (CNNs), thus providing a unified analysis of pruning in wide networks. Our results are free of data assumptions, and showcase a tradeoff between compressibility and network width. The algorithm we consider bears some similarities with Optimal Brain Damage (OBD) and can be viewed as a post-training randomized version of it. The theoretical results we derive bridge the gap between theory and application for pruning/quantization, and provide a justification for the empirical success of compression in wide multilayer perceptrons.

Dynamical Mean Field Theory (DMFT) provides an asymptotic description of the dynamics of macroscopic observables in certain disordered systems. Originally pioneered in the context of spin glasses, it has since been used to derive asymptotic dynamical equations for a wide range of models in physics, high-dimensional statistics and machine learning. One of the main tools used by physicists to obtain these equations is the dynamical cavity method, which has remained largely non-rigorous. In contrast, existing mathematical formalizations have relied on alternative approaches, including Gaussian conditioning, large deviations over paths, or Fourier analysis. In this work, we formalize the dynamical cavity method and use it to give a new proof of the DMFT equations for General First Order Methods, a broad class of dynamics encompassing algorithms such as Gradient Descent and Approximate Message Passing.

We study the problem of efficiently finding large common induced subgraphs of two independent Erdős–Rényi random graphs $G_1, G_2 \sim \mathbb{G}(n,1/2)$. Recently, Chatterjee and Diaconis (2023) showed that the largest common induced subgraph of $G_1$ and $G_2$ has size $(4-o(1))\log_2 n$ with high probability. We first show that a simple greedy online algorithm finds a common induced subgraph of $G_1$ and $G_2$ of size $(2-o(1)) \log_2 n$ with high probability. Our main result shows that no online algorithm can find a common induced subgraph of $G_1$ and $G_2$ of size at least $(2+\varepsilon) \log_2 n$ with probability bounded away from $0$ as $n \to \infty$. Together, these results provide evidence that this problem exhibits a computation-to-optimization gap. To prove the impossibility result, we show that the solution space of the problem exhibits a version of the (multi) overlap gap property (OGP), and utilize an interpolation argument recently developed by Gamarnik, K{ı}z{ı}ldağ, and Warnke (2025) that connects OGP and online algorithms.

The overlap gap property (OGP) is a statement about the geometry of near-optimal solutions. Exhibiting OGP implies failure of a class of local algorithms; and has been observed to coincide with conjectured algorithmic limits in problems with statistical computational gap. We consider the Stochastic Block Model (SBM), where the graph has a planted partition with k equal-size blocks which form the "communities", and where, for parameters p > q, vertices within the same community connect with probability p, while vertices in different communities connect with probability q, independently across pairs of vertices. Modularity-based clustering algorithms have become ubiquitous in applications. This article studies theoretical limits of local algorithms based on the modularity score on the SBM. We establish that modularity exhibits OGP on the SBM. This rules out a class of local algorithms based on modularity for recovery in the SBM, and shows slow mixing time for a related Markov Chain. Theoretically this is one of the few instances where OGP has been established for a "planted" model, as most such analyses to date consider the "null" model. As part of our analysis, we extend a result by Bickel and Chen 2009, who established that with high probability, the modularity optimal partition of SBM is o(n) local moves away from the planted partition, where n is the graph size. We show that, with high probability, any partition with modularity score sufficiently near the optimal value is close to the planted partition.

We consider the problem of recovering the support of a sparse signal using noisy projections. While extensive work has been done on the dense measurement matrix setting, the sparse setting remains less explored. In this work, we establish sufficient conditions on the sample size for successful sparse recovery using sparse measurement matrices. Bringing together our result with previously known necessary conditions, we discover that, in the regime where $ds/p \rightarrow +\infty$, sparse recovery using a sparse design exhibits a phase transition at an information-theoretic threshold of $n_{\text{INF}}^{\text{SP}} = \Theta\left(s\log\left(p/s\right)/\log\left(ds/p\right)\right)$ for the number of measurements, where \(p\) denotes the signal dimension, $s$ the number of non-zero components of the signal, and $d$ the expected number of non-zero components per row of measurement. This expression makes the price of sparsity explicit: restricting each measurement to $d$ non‑zeros inflates the required sample size by a factor of $\log{s}/\log\left(ds/p\right)$, revealing a precise trade‑off between sampling complexity and measurement sparsity. Additionally, we examine the effect of sparsifying an originally dense measurement matrix on sparse signal recovery. We prove in the regime of $s = \alpha p$ and $d = \psi p$ with $\alpha, \psi \in \left(0,1\right)$ and $\psi$ small that a sample of size $n^{\text{Sp-ified}}_{\text{INF}} = \Theta\left(p / \psi^2\right)$ is sufficient for recovery, subject to a certain uniform integrability conjecture, the proof of which is work in progress.

Abstract. We consider the problem of estimating the edge density of densest [Formula: see text]-node subgraphs of an Erdös–Rényi graph [Formula: see text]. The problem is well-understood in the regime [Formula: see text] and in the regime [Formula: see text]. In the former case it can be reduced to the problem of estimating the size of largest cliques, and its extensions [P. Balister, B. Bollobás, K. Gunderson, I. Leader, and M. Walters, Trans. Amer. Math. Soc., 370 (2018), pp. 7361–7389]. In the latter case the full answer is known up to the order [Formula: see text] using sophisticated methods from the theory of spin glasses. The intermediate case [Formula: see text], however, is not well studied and this is our focus. We establish that in this regime the density (that is the maximum number of edges supported by any [Formula: see text]-node subgraph) is [Formula: see text], w.h.p. as [Formula: see text], and provide more refined asymptotics under the [Formula: see text], for various ranges of [Formula: see text]. This extends earlier similar results in [D. Gamarnik and I. Zadik, The Landscape of the Planted Clique Problem: Dense Subgraphs and the Overlap Gap Property, preprint, https://arxiv.org/abs/1904.07174 , 2019] where this asymptotic was confirmed only when [Formula: see text] 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 [Formula: see text] 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 [Formula: see text], confirming a hypothesis stated in [D. Gamarnik and I. Zadik, The Landscape of the Planted Clique Problem: Dense Subgraphs and the Overlap Gap Property, preprint, https://arxiv.org/abs/1904.07174 , 2019].

Abstract. We consider the problem of finding nearly optimal solutions of optimization problems with random objective functions. Such problems arise widely in the theory of random graphs, theoretical computer science, and statistical physics. Two concrete problems we consider are (a) optimizing the Hamiltonian of a spherical or Ising [Formula: see text]-spin glass model and (b) finding a large independent set in a sparse Erdős–Rényi graph. The following families of algorithms are considered: (a) low-degree polynomials of the input—a general framework that captures many prior algorithms; (b) low-depth Boolean circuits; (c) the Langevin dynamics algorithm, a canonical Monte Carlo analogue of the gradient descent algorithm. We show that these families of algorithms cannot have high success 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 to or far from each other. The crux of our proof is that the classes of algorithms we consider exhibit a form of stability (noise-insensitivity): a small perturbation of the input induces a small perturbation of the output. 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, which we expect to be of independent interest. In the case of Boolean circuits, the result also makes use of Linial–Mansour–Nisan’s classical theorem. Our techniques apply more broadly to low influence functions, and we expect that they may apply more generally.

Abstract. The semi-random graph process is a single player game in which the player is initially presented an empty graph on [Formula: see text] vertices. In each round, a vertex [Formula: see text] is presented to the player independently and uniformly at random. The player then adaptively selects a vertex [Formula: see text] and adds the edge [Formula: see text] 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 [Formula: see text], having the chromatic number at least [Formula: see text], and not having an independent set of size at least [Formula: see text].

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\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 \citet[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.

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 saddlepoint 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ôs-Ré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\geq 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.

The binary (or Ising) perceptron is a toy model of a single-layer neural network and can be viewed as a random constraint satisfaction problem with a high degree of connectivity. The model and its symmetric variant, the symmetric binary perceptron (SBP), have been studied widely in statistical physics, mathematics, and machine learning.The 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 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 [1], [2]. This suggests that finding a solution to the SBP may be computationally intractable. At the same time, however, the SBP does admit polynomial-time search algorithms at low enough densities. A conjectural explanation for this conundrum was put forth in [3]: 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 [4]. 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 statistical-to-computational gap exhibited by this problem. We show that at high enough densities the 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\rightarrow\infty$. We then prove that the m-OGP rules out the class of stable algorithms for the SBP above this threshold. We conjecture that the $m\rightarrow\infty$ limit of the m-OGP threshold marks the algorithmic threshold for the problem. Furthermore, we investigate the stability of known efficient algorithms for perceptron models and show that the Kim-Roche algorithm [5], devised for the asymmetric binary perceptron, is stable in the sense we consider.

We focus on the problem of algorithmically finding a near-optimal solution for the (random) number partitioning problem (NPP), a problem that is of great practical and theoretical significance. The NPP possesses a striking gap between the existential and best algorithmic guarantee: when its input has i.i.d. standard Gaussian entries, the optimal value of NPP is $\Theta \left( {\sqrt n {2^{ - n}}} \right)$ (w.h.p.); whereas the best polynomial-time algorithm achieves an exponentially worse value of only ${2^{ - \Theta \left( {{{\log }^2}n} \right)}}$ (w.h.p.). In this paper, we inquire into the origin of this gap by studying the landscape of the NPP through the lens of statistical physics and establish the presence of the Overlap Gap Property (OGP), a topological barrier for large classes of algorithms. We then leverage the OGP to establish that (a) sufficiently stable algorithms fail to find a near-optimal solution with value below $\left. {{2^{ - \omega (n\log - 1/5}}n} \right)$; and (b) a very natural Monte Carlo Markov Chain dynamics mixes slowly. A technical innovation of our paper is that we consider the overlap structure of m–tuples of near- optimal solutions where m itself grows in n. Our hardness result for stable algorithms is based on a Ramsey-theoretic argument from extremal combinatorics. To the best of our knowledge, this is the first usage of Ramsey Theory to show algorithmic hardness.

We consider the problem of finding a two-layer neural network with sigmoid, rectified linear unit, 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: does a low training error guarantee that the norm of the output layer (outer norm) itself is small? We address 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 good sample complexity, (b) are independent of the number of hidden units, (c) are oblivious to the training algorithm; and (d) require quite mild assumptions on the data (in particular the input vector$X$∊ Rdneed not have independent coordinates). We then show how our bounds can be leveraged to yield generalization guarantees for such networks.

We consider 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 taking values in a rationally independent set of bounded cardinality, known to learner; collectively called as the mixed-range assumption. Using a novel combination of the Partial Sum of Least Squares (PSLQ) integer relation detection, and the Lenstra-Lenstra-Lovász (LLL) lattice basis reduction algorithms, we propose a polynomial-time algorithm which provably recovers a$\beta ^{*}\in \mathbb {R}^{p}$enjoying the mixed-range 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 the$Q-$rationality property, from its noisy measurements$Y=X\beta ^{*}+W\in \mathbb {R}^{n}$, even from a single sample ($n=1$). We further establish that 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 the Least Absolute Shrinkage and Selection Operator (LASSO) and the Basis Pursuit are known to fail. Furthermore, our results also reveal algorithmic connections between the high-dimensional linear regression problem, and the integer relation detection, randomized subset-sum, and shortest vector problems.

We consider the problem of finding nearly optimal solutions of optimization problems with random objective functions. Such problems arise widely in the theory of random graphs, theoretical computer science, and statistical physics. 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 Erdos-Renyi graph. Two families of algorithms are considered: (a) low-degree polynomials of the input-a general framework that captures methods such as approximate message passing and local algorithms on sparse graphs, among others; and (b) the Langevin dynamics algorithm, a canonical Monte Carlo analogue of the gradient descent algorithm (applicable only for the spherical p-spin glass Hamiltonian). We show that neither family of algorithms can produce nearly optimal solutions with high probability. Our proof uses the fact that both 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 objective values are above a certain threshold are either close or far from each other. The crux of our proof is the stability of both algorithms: a small perturbation of the input induces a small perturbation of the output. By an interpolation argument, such a stable algorithm cannot overcome the OGP barrier. The stability of the Langevin dynamics is an immediate consequence of the well-posedness of stochastic differential equations. The stability of low-degree polynomials is established using concepts from Gaussian and Boolean Fourier analysis, including noise sensitivity, hypercontractivity, and total influence.

We establish the average-case hardness of the algorithmic problem of exact computation of the partition function associated with the Sherrington–Kirkpatrick model of spin glasses with Gaussian couplings and random external field. In particular, we establish that unless P=#P, there does not exist a polynomial-time algorithm to exactly compute the partition function on average. This is done by showing that if there exists a polynomial time algorithm, which exactly computes the partition function for inverse polynomial fraction (1/nO(1)) of all inputs, then there is a polynomial time algorithm, which exactly computes the partition function for all inputs, with high probability, yielding P=#P. The computational model that we adopt is finite-precision arithmetic, where the algorithmic inputs are truncated first to a certain level N of digital precision. The ingredients of our proof include the random and downward self-reducibility of the partition function with random external field; an argument of Cai et al. (In STACS 99 (Trier) (1999) 90–99 Springer) for establishing the average-case hardness of computing the permanent of a matrix; a list-decoding algorithm of Sudan (In 37th Annual Symposium on Foundations of Computer Science (Burlington, VT, 1996) (1996) 164–172 IEEE Comput. Soc. Press), for reconstructing polynomials intersecting a given list of numbers at sufficiently many points; and near-uniformity of the log-normal distribution, modulo a large prime p. To the best of our knowledge, our result is the first one establishing a provable hardness of a model arising in the field of spin glasses. Furthermore, we extend our result to the same problem under a different real-valued computational model, for example, using a Blum–Shub–Smale machine (In [Proceedings 1988] 29th Annual Symposium on Foundations of Computer Science (1988) 387–397 IEEE) operating over real-valued inputs. We establish that, if there exists a polynomial time algorithm which exactly computes the partition function for 34+1nO(1) fraction of all inputs, then there exists a polynomial time algorithm, which exactly computes the partition function for all inputs, with high probability, yielding P=#P. Our proof uses the random self-reducibility of the partition function, together with a control over the total variation distance for log-normal random variables in presence of a convex perturbation, and the Berlekamp–Welch algorithm.

We study high-dimensional linear regression problem without sparsity, and address the question of efficient recovery with small number of measurements. We propose an algorithm which efficiently recovers an unknown feature vector β* ∈ ℝpfrom its linear measurements Y = Xβ* in polynomially many steps, with high probability (as p → ∞), even with a single measurement, provided elements of β* are supported on a rationally independent set of at most polynomial in p size known to learner. We use a combination of PSLQ integer relation and LLL lattice basis reduction algorithms to achieve our goal. We then apply our ideas to develop an efficient, single-sample algorithm for the phase retrieval problem, where β* ∈ Cpis to to be recovered from magnitude-only observations Y = |〈X, β*〉|.

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 several standard methods.

We consider a high dimensional linear regression problem where the goal is to efficiently recover an unknown vector \beta^* from n noisy linear observations Y=X \beta^+W in R^n, for known X in R^{n \times p} and unknown W in R^n. Unlike most of the literature on this model we make no sparsity assumption on \beta^. Instead we adopt a regularization based on assuming that the underlying vectors \beta^* have rational entries with the same denominator Q. We call this Q-rationality assumption. We propose a new polynomial-time algorithm for this task which is based on the seminal Lenstra-Lenstra-Lovasz (LLL) lattice basis reduction algorithm. We establish that under the Q-rationality assumption, our algorithm recovers exactly the vector \beta^* for a large class of distributions for the iid entries of X and non-zero noise W. We prove that it is successful under small noise, even when the learner has access to only one observation (n=1). Furthermore, we prove that in the case of the Gaussian white noise for W, n=o(p/\log p) and Q sufficiently large, our algorithm tolerates a nearly optimal information-theoretic level of the noise.

We consider a sparse linear regression model $Y=Xβ^*+W$ where $X$ is $n\times p$ matrix Gaussian i.i.d. entries, $W$ is $n\times 1$ noise vector with i.i.d. mean zero Gaussian entries and standard deviation $σ$, and $β^*$ is $p\times 1$ binary vector with support size (sparsity) $k$. Using a novel conditional second moment method we obtain a tight up to a multiplicative constant approximation of the optimal squared error $\min_β\|Y-Xβ\|_2$, where the minimization is over all $k$-sparse binary vectors $β$. The approximation reveals interesting structural properties of the underlying regression problem. In particular, \beginenumerate \item [(a)] We establish that $n^*=2k\log p/\log (2k/σ^2+1)$ is a phase transition point with the following “all-or-nothing” property. When $n$ exceeds $n^*$, $(2k)^-1\|\beta_2-β^*\|_0≈0$, and when $n$ is below $n^*$, $(2k)^-1\|\beta_2-β^*\|_0≈1$, where $\beta_2$ is the optimal solution achieving the smallest squared error. As a corollary $n^*$ is the asymptotic threshold for recovering $β^*$ information theoretically. Note that $n^*$ is asymptotically below the threshold $n_\text{LASSO}/CS=(2k+σ^2)\log p$, above which the LASSO and Compressive Sensing methods are able to recover $β^*$. \item [(b)] We compute the squared error for an intermediate problem $\min_β\|Y-Xβ\|_2$ where the minimization is restricted to vectors $β$ with $\|β-β^*\|_0=2k ζ$, for some fixed ratio $ζ∈[0,1]$. We show that a lower bound part $Γ(ζ)$ of the estimate, which essentially corresponds to the estimate based on the first moment method, undergoes a phase transition at three different thresholds, namely $n_\text{inf},1=σ^2\log p$, which is information theoretic bound for recovering $β^*$ when $k=1$ and $σ$ is large, then at $n^*$ and finally at $n_\text{LASSO}/CS$. \item [(c)] We establish a certain Overlap Gap Property (OGP) on the space of all $k$-sparse binary vectors $β$ when $n\le ck\log p$ for sufficiently small constant $c$. By drawing a connection with a similar OGP exhibited by many randomly generated constraint satisfaction problems and statistical physics models, we conjecture that OGP is the source of algorithmic hardness of solving the minimization problem $\min_β\|Y-Xβ\|_2$ in the regime $n Cite this Paper BibTeX @InProceedings{pmlr-v65-david17a, title = {High Dimensional Regression with Binary Coefficients. Estimating Squared Error and a Phase Transtition}, author = {David, Gamarnik and Ilias, Zadik}, booktitle = {Proceedings of the 2017 Conference on Learning Theory}, pages = {948--953}, year = {2017}, editor = {Kale, Satyen and Shamir, Ohad}, volume = {65}, series = {Proceedings of Machine Learning Research}, month = {07--10 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v65/david17a/david17a.pdf}, url = {https://proceedings.mlr.press/v65/david17a.html}, abstract = {We consider a sparse linear regression model $Y=Xβ^*+W$ where $X$ is $n\times p$ matrix Gaussian i.i.d. entries, $W$ is $n\times 1$ noise vector with i.i.d. mean zero Gaussian entries and standard deviation $σ$, and $β^*$ is $p\times 1$ binary vector with support size (sparsity) $k$. Using a novel conditional second moment method we obtain a tight up to a multiplicative constant approximation of the optimal squared error $\min_β\|Y-Xβ\|_2$, where the minimization is over all $k$-sparse binary vectors $β$. The approximation reveals interesting structural properties of the underlying regression problem. In particular, \beginenumerate \item [(a)] We establish that $n^*=2k\log p/\log (2k/σ^2+1)$ is a phase transition point with the following “all-or-nothing” property. When $n$ exceeds $n^*$, $(2k)^-1\|\beta_2-β^*\|_0≈0$, and when $n$ is below $n^*$, $(2k)^-1\|\beta_2-β^*\|_0≈1$, where $\beta_2$ is the optimal solution achieving the smallest squared error. As a corollary $n^*$ is the asymptotic threshold for recovering $β^*$ information theoretically. Note that $n^*$ is asymptotically below the threshold $n_\text{LASSO}/CS=(2k+σ^2)\log p$, above which the LASSO and Compressive Sensing methods are able to recover $β^*$. \item [(b)] We compute the squared error for an intermediate problem $\min_β\|Y-Xβ\|_2$ where the minimization is restricted to vectors $β$ with $\|β-β^*\|_0=2k ζ$, for some fixed ratio $ζ∈[0,1]$. We show that a lower bound part $Γ(ζ)$ of the estimate, which essentially corresponds to the estimate based on the first moment method, undergoes a phase transition at three different thresholds, namely $n_\text{inf},1=σ^2\log p$, which is information theoretic bound for recovering $β^*$ when $k=1$ and $σ$ is large, then at $n^*$ and finally at $n_\text{LASSO}/CS$. \item [(c)] We establish a certain Overlap Gap Property (OGP) on the space of all $k$-sparse binary vectors $β$ when $n\le ck\log p$ for sufficiently small constant $c$. By drawing a connection with a similar OGP exhibited by many randomly generated constraint satisfaction problems and statistical physics models, we conjecture that OGP is the source of algorithmic hardness of solving the minimization problem $\min_β\|Y-Xβ\|_2$ in the regime $n Copy to Clipboard Download Endnote %0 Conference Paper %T High Dimensional Regression with Binary Coefficients. Estimating Squared Error and a Phase Transtition %A Gamarnik David %A Zadik Ilias %B Proceedings of the 2017 Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2017 %E Satyen Kale %E Ohad Shamir %F pmlr-v65-david17a %I PMLR %P 948--953 %U https://proceedings.mlr.press/v65/david17a.html %V 65 %X We consider a sparse linear regression model $Y=Xβ^*+W$ where $X$ is $n\times p$ matrix Gaussian i.i.d. entries, $W$ is $n\times 1$ noise vector with i.i.d. mean zero Gaussian entries and standard deviation $σ$, and $β^*$ is $p\times 1$ binary vector with support size (sparsity) $k$. Using a novel conditional second moment method we obtain a tight up to a multiplicative constant approximation of the optimal squared error $\min_β\|Y-Xβ\|_2$, where the minimization is over all $k$-sparse binary vectors $β$. The approximation reveals interesting structural properties of the underlying regression problem. In particular, \beginenumerate \item [(a)] We establish that $n^*=2k\log p/\log (2k/σ^2+1)$ is a phase transition point with the following “all-or-nothing” property. When $n$ exceeds $n^*$, $(2k)^-1\|\beta_2-β^*\|_0≈0$, and when $n$ is below $n^*$, $(2k)^-1\|\beta_2-β^*\|_0≈1$, where $\beta_2$ is the optimal solution achieving the smallest squared error. As a corollary $n^*$ is the asymptotic threshold for recovering $β^*$ information theoretically. Note that $n^*$ is asymptotically below the threshold $n_\text{LASSO}/CS=(2k+σ^2)\log p$, above which the LASSO and Compressive Sensing methods are able to recover $β^*$. \item [(b)] We compute the squared error for an intermediate problem $\min_β\|Y-Xβ\|_2$ where the minimization is restricted to vectors $β$ with $\|β-β^*\|_0=2k ζ$, for some fixed ratio $ζ∈[0,1]$. We show that a lower bound part $Γ(ζ)$ of the estimate, which essentially corresponds to the estimate based on the first moment method, undergoes a phase transition at three different thresholds, namely $n_\text{inf},1=σ^2\log p$, which is information theoretic bound for recovering $β^*$ when $k=1$ and $σ$ is large, then at $n^*$ and finally at $n_\text{LASSO}/CS$. \item [(c)] We establish a certain Overlap Gap Property (OGP) on the space of all $k$-sparse binary vectors $β$ when $n\le ck\log p$ for sufficiently small constant $c$. By drawing a connection with a similar OGP exhibited by many randomly generated constraint satisfaction problems and statistical physics models, we conjecture that OGP is the source of algorithmic hardness of solving the minimization problem $\min_β\|Y-Xβ\|_2$ in the regime $n Copy to Clipboard Download APA David, G. & Ilias, Z.. (2017). High Dimensional Regression with Binary Coefficients. Estimating Squared Error and a Phase Transtition. Proceedings of the 2017 Conference on Learning Theory, in Proceedings of Machine Learning Research 65:948-953 Available from https://proceedings.mlr.press/v65/david17a.html. Copy to Clipboard Download Related Material Download PDF This site last compiled Sun, 05 Jul 2026 15:10:29 +0000 Github Account Copyright © The authors and PMLR 2026. MLResearchPress

We consider the problem of reconstructing a rank-$k$ $n \times n$ matrix $M$ from a sampling of its entries. Under a certain incoherence assumption on $M$ and for the case when both the rank and the condition number of $M$ are bounded, it was shown in (Candès and Recht, 2009; Candès and Tao, 2010; Keshavan et al., 2010; Recht, 2011; Jain et al., 2012; Hardt, 2014) that $M$ can be recovered exactly or approximately (depending on some trade-off between accuracy and computational complexity) using $O(n \text{poly}(\log n))$ samples in super-linear time $O(n^a \text{poly}(\log n))$ for some constant $a ≥1$. In this paper, we propose a new matrix completion algorithm using a novel sampling scheme based on a union of independent sparse random regular bipartite graphs. We show that under the same conditions w.h.p. our algorithm recovers an $ε$-approximation of $M$ in terms of the Frobenius norm using $O(n \log^2(1/ε))$ samples and in linear time $O(n \log^2(1/ε))$. This provides the best known bounds both on the sample complexity and computational cost for reconstructing (approximately) an unknown low-rank matrix. The novelty of our algorithm is two new steps of thresholding singular values and rescaling singular vectors in the application of the “vanilla” alternating minimization algorithm. The structure of sparse random regular graphs is used heavily for controlling the impact of these regularization steps.

We formalize the class of “sequential local algorithms" and show that these algorithms fail to find satisfying assignments on random instances of the “Not-All-Equal-$K$-SAT” (NAE-$K$-SAT) problem if the number of message passing iterations is bounded by a function moderately growing in the number of variables and if the clause-to-variable ratio is above $(1+o_K(1)){2^{K-1}\over K}\ln^2 K$ for sufficiently large $K$. Sequential local algorithms are those that iteratively set variables based on some local information and/or local randomness and then recurse on the reduced instance. Our model captures some weak abstractions of natural algorithms such as Survey Propagation (SP)-guided as well as Belief Propagation (BP)-guided decimation algorithms---two widely studied message-passing--based algorithms---when the number of message-passing rounds in these algorithms is restricted to be growing only moderately with the number of variables. The approach underlying our paper is based on an intricate geometry of the solution space of a random NAE-$K$-SAT problem. We show that above the $(1+o_K(1)){2^{K-1}\over K}\ln^2 K$ threshold, the overlap structure of $m$-tuples of nearly (in an appropriate sense) satisfying assignments exhibit a certain behavior expressed in the form of some constraints on pairwise distances between the $m$ assignments for appropriately chosen positive integer $m$. We further show that if a sequential local algorithm succeeds in finding a satisfying assignment with probability bounded away from zero, then one can construct an $m$-tuple of solutions violating these constraints, thus leading to a contradiction. Along with [D. Gamarnik and M. Sudan, Ann. Probab., to appear], where a similar approach was used in a (somewhat simpler) setting of nonsequential local algorithms, this result is the first work that directly links the overlap property of random constraint satisfaction problems to the computational hardness of finding satisfying assignments.

We consider the following distributed service model: jobs with unit mean, exponentially distributed, and independent processing times arrive as a Poisson process of rate λ N, with 0<λ<1, and are immediately dispatched to one of several queues associated with N identical servers with unit processing rate. 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 to drive the expected steady-state queueing delay of a typical job to zero, as N increases. We propose a certain policy and establish (using a fluid limit approach) that it drives the delay to zero when either (i) the message rate grows superlinearly with N, or (ii) the memory grows superlogarithmically with N. Moreover, we show that any policy that has a certain symmetry property, and for which neither condition (i) or (ii) holds, results in an expected queueing delay which is bounded away from zero.

We consider the problem of reconstructing a low-rank matrix from a subset of its entries and analyze two variants of the so-called alternating minimization algorithm, which has been proposed in the past. We establish that when the underlying matrix has rank one, has positive bounded entries, and the graph underlying the revealed entries has diameter which is logarithmic in the size of the matrix, both algorithms succeed in reconstructing the matrix approximately in polynomial time starting from an arbitrary initialization. We further provide simulation results which suggest that the second variant which is based on the message passing type updates performs significantly better.

We consider the problem of efficient operation of a barter exchange platform for indivisible goods. We introduce a dynamic model of barter exchange where in each period one agent arrives with a single item she wants to exchange for a different item. We study a homogeneous and stochastic environment: an agent is interested in the item possessed by another agent with probability p, independently for all pairs of agents. We consider two settings with respect to the types of allowed exchanges: a) Only two-way cycles, in which two agents swap their items, b) Two or three-way cycles. The goal of the platform is to minimize the average waiting time of an agent. Somewhat surprisingly, we find that in each of these settings, a policy that conducts exchanges in a greedy fashion is near optimal, among a large class of policies that includes batching policies. Further, we find that for small p, allowing three-cycles can greatly improve the waiting time over the two-cycles only setting. Specifically, we find that a greedy policy achieves an average waiting time of Θ(1/p2) in setting a), and Θ(1/p3/2) in setting b). Thus, a platform can achieve the smallest waiting times by using a greedy policy, and by facilitating three cycles, if possible. Our findings are consistent with empirical and computational observations which compare batching policies in the context of kidney exchange programs.

Local algorithms on graphs are algorithms that run in parallel on the nodes of a graph to compute some global structural feature of the graph. Such algorithms use only local information available at nodes to determine local aspects of the global structure, while also potentially using some randomness. Research over the years has shown that such algorithms can be surprisingly powerful in terms of computing structures like large independent sets in graphs locally. These algorithms have also been implicitly considered in the work on graph limits, where a conjecture due to Hatami, Lovász and Szegedy [17] implied that local algorithms may be able to compute near-maximum independent sets in (sparse) random d-regular graphs. In this paper we refute this conjecture and show that every independent set produced by local algorithms is smaller that the largest one by a multiplicative factor of at least 1/2+1/(2√2) ≈ .853, asymptotically as d → ∞.

We consider the #P-complete problem of counting the number of independent sets in a given graph. Our interest is in understanding the effectiveness of the popular belief propagation (BP) heuristic. BP is a simple iterative algorithm that is known to have at least one fixed point, where each fixed point corresponds to a stationary point of the Bethe free energy (introduced by Yedidia, Freeman, and Weiss [IEEE Trans. Inform. Theory, 51 (2004), pp. 2282–2312] in recognition of Bethe’s earlier work in 1935). The evaluation of the Bethe free energy at such a stationary point (or BP fixed point) leads to the Bethe approximation for the number of independent sets of the given graph. BP is not known to converge in general, nor is an efficient, convergent procedure for finding stationary points of the Bethe free energy known. Furthermore, the effectiveness of the Bethe approximation is not well understood. As the first result of this paper we propose a BP-like algorithm that always converges to a stationary point of the Bethe free energy for any graph for the independent set problem. This procedure finds an [Formula: see text]-approximate stationary point in [Formula: see text] iterations for a graph of [Formula: see text] nodes with max-degree [Formula: see text]. We study the quality of the resulting Bethe approximation using the recently developed “loop series” framework of Chertkov and Chernyak [J. Stat. Mech. Theory Exp., 6 (2006), P06009]. As this characterization is applicable only for exact stationary points of the Bethe free energy, we provide a slightly modified characterization that holds for [Formula: see text]-approximate stationary points. We establish that for any graph on [Formula: see text] nodes with max-degree [Formula: see text] and girth larger than [Formula: see text], the multiplicative error between the number of independent sets and the Bethe approximation decays as [Formula: see text] for some [Formula: see text]. This provides a deterministic counting algorithm that leads to strictly different results compared to a recent result of Weitz [in Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing, ACM Press, New York, 2006, pp. 140–149]. Finally, as a consequence of our analysis we prove that the Bethe approximation is exceedingly good for a random 3-regular graph conditioned on the shortest cycle cover conjecture of Alon and Tarsi [SIAM J. Algebr. Discrete Methods, 6 (1985), pp. 345–350] being true.

Finding the largest independent set in a graph is a notoriously difficult NP-complete combinatorial optimization problem. Moreover, even for graphs with largest degree 3, no polynomial time approximation algorithm exists with a 1.0071-factor approximation guarantee, unless P = NP [BK98]. We consider the related problem of finding the maximum weight independent set in a bounded degree graph, when the node weights are generated i.i.d. from a common distribution. Surprisingly, we discover that the problem becomes tractable for certain distributions. Specifically, we construct a randomized PTAS (Polynomial-Time Approximation Scheme) for the case of exponentially distributed weights and arbitrary graphs with degree at most 3. We extend our result to graphs with larger constant degrees but for distributions which are mixtures of exponential distributions. At the same time, we prove that no PTAS exists for computing the expected size of the maximum weight independent set in the case of exponentially distributed weights for graphs with sufficiently large constant degree, unless P=NP. Our algorithm, cavity expansion, is new and is based on the combination of several powerful ideas, including recent deterministic approximation algorithms for counting on graphs and local weak convergence/correlation decay methods.

We formulate a Belief Propagation (BP) algorithm in the context of the capacitated minimum-cost network flow problem (ℳ ℱ). Unlike most of the instances of BP studied in the past, the messages of BP in the context of this problem are piecewise-linear functions. We prove that BP converges to the optimal solution in pseudo-polynomial time, provided that the optimal solution is unique and the problem input is integral. Moreover, we present a simple modification of the BP algorithm which gives a fully polynomial-time randomized approximation scheme (FPRAS) for ℳ ℱ. This is the first instance where BP is proved to have fully-polynomial running time.

We establish the existence of free energy limits for several sparse random hypergraph models corresponding to certain combinatorial models on Erdos-Renyi (ER) graph G(N,c/N) and random r-regular graph G(N,r).

One of the key computational problems in combinatorics/statistical physics is the problem of computing limits of the log-partition functions for various statistical mechanics models on lattices. In combinatorics this limit corresponds to the exponent of various arrangements on lattices, for example the exponents of the number of independent sets, proper colorings or matchings on a lattice. In statistical physics this limit is called free energy. We propose a new method, sequential cavity, which beats the best known existing methods, such as transfer matrix method, in obtaining sharper bounds on the limits of the log-partition function for two models: independent sets (hard-core) and matchings (monomer-dimer). Our method is based on a surprisingly simple representation of the log-partition function limit in terms of a certain marginal probability of a suitably modified lattice, and using recent deterministic approximation counting algorithms for these two models. Our method also has a provably better theoretical performance compared with the transfer matrix method.

We construct a deterministic fully polynomial time approximationscheme (FPTAS) for computing the total number of matchings in abounded degree graph. Additionally, for an arbitrary graph, weconstruct a deterministic algorithm for computing approximately thenumber of matchings within running time exp(O(√n log2n)),where n is the number of vertices.

We investigate the stability of packet routing policies in adversarial queueing networks. We provide a simple classification of networks which are stable under any greedy scheduling policy. We show that a network is stable if and only if the underlying undirected connected graph contains at most two edges. We also propose a simple and distributed policy which is stable in an arbitrary adversarial queueing network even for the critical value of the arrival rate r=1. Finally, a simple and checkable network flow-type load condition is formulated for adaptive adversarial queueing networks, and a policy is proposed which achieves stability under this new load condition. This load condition is a relaxation of the integral network flow-type condition considered previously in the literature.

We consider a model of learning in which the successive observations follow a certain Markov chain. The observations are labeled according to a membership to some unknown target set. For a Markov chain with finitely many states we show that, if the target set belongs to a family of sets with a finite Vapnik-Chervonenkis (1995) dimension, then probably approximately correct (PAC) learning of this set is possible with polynomially large samples. Specifically for observations following a random walk with a state space /spl Xscr/ and uniform stationary distribution, the sample size required is no more than /spl Omega/(t/sub 0//1-/spl lambda//sub 2/log(t/sub 0/|/spl chi/|1//spl delta/)), where /spl delta/ is the confidence level, /spl lambda//sub 2/ is the second largest eigenvalue of the transition matrix, and t/sub 0/ is the sample size sufficient for learning from independent and identically distributed (i.i.d.) observations. We then obtain similar results for Markov chains with countably many states using Lyapunov function technique and results on mixing properties of infinite state Markov chains.

We consider a model of learning in which the successive observations follow a certain Markov chain. The observations are labeled according to a membership to some unknown target set. For a Markov chain with finitely many states we show that, if the target set belongs to a family of sets with a finite VC dimension, then probably approximately correct learning of this set is possible with polynomially large samples. Specifically for observations following a random walk with a state space and uniform stationary distribution, the sample size required is no more than # 1-#2 log(t 0 where # is the confidence level, # 2 is the second largest eigenvalue of the transition matrix and t 0 is the sample size su#cient for learning from i.i.d. observations. We then obtain similar results for Markov chains with countably many states using Lyapunov function technique and recent results on mixing properties of infinite state Markov chains.

We investigate stability of packet routing policies in adversarial queueing networks. We provide a simple classification of networks which are stable under any greedy scheduling policy - network is stable if and only if the underlying undirected connected graph contains at most two edges. We also propose a simple and distributed policy which is stable in an arbitrary adversarial queueing network even for the critical value of the arrival rate r = 1. Finally, a simple and checkable network flow type load condition is formulated for adaptive adversarial queueing networks and a policy is proposed which achieves stability under this new load condition. This load condition is a relaxation of the integral network flow type condition considered previously in the literature.

We consider a non-parametric regression model, in which the regression function to be estimated is coordinate-wise monotone.Such functions can model, for example, the dependence of an option price on a strike price, duration and a price of an underlying asset.We propose a simple algorithm based on quadratic optimization, which estimates the regression function in polynomial time.Numerical results are provided, which show that the algorithm is quite robust to possible discontinuities of the regression function.Our main theoretical result shows that the expected VC-entropy of the space of coordinate-wise monotone functions grows subexponentially.As a result, the estimating function, constructed by our algorithm, converges to the true regression function, as the number of observations goes to infinity, and the estimating procedure is consistent.

The subject of this paper is stability properties of adversarial queueing networks. Such queueing systems are used to model packet switch communication networks, in which packets are generated and routed dynamically, and have become a subject of research focus recently. Adversarial queueing networks are defined to be stable, if the number of packets stays bounded over time. A central question is determining which adversarial queueing networks are stable, when an arbitrary greedy packet routing policy is implemented. In this paper we show how stability of a queueing network can be determined by considering an associated fluid models. Our main result is that the stability of the fluid model implies the stability of an underlying adversarial queueing network. This opens an opportunity for analyzing stability of adversarial networks, using established stability methods from continuous time processes, for example, the method of Lyapunov function or trajectory decomposition. We demonstrate the use of these methods on several examples.

Article Estimation of time-varying parameters in statistical models: an optimization approach Share on Authors: Dimitris Bertsimas Sloan School of Management and Operations Research Center, MIT Cambridge, MA Sloan School of Management and Operations Research Center, MIT Cambridge, MAView Profile , David Gamarnik Operations Research Center, MIT Cambridge, MA Operations Research Center, MIT Cambridge, MAView Profile , John N. Tsitsiklis Laboratory for Information and Decision Sciences and Operations Research Center, MIT Cambridge, MA Laboratory for Information and Decision Sciences and Operations Research Center, MIT Cambridge, MAView Profile Authors Info & Claims COLT '97: Proceedings of the tenth annual conference on Computational learning theoryJuly 1997 Pages 314–324https://doi.org/10.1145/267460.267519Online:01 July 1997Publication History 1citation173DownloadsMetricsTotal Citations1Total Downloads173Last 12 Months1Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access