We investigate the sample complexity of recovering tensors with low symmetric rank from sym- metric rank-one measurements, a setting particularly motivated by the study of higher-order inter- actions in statistics and the analysis of two-layer polynomial neural networks. Using a covering number argument, we analyze the performance of the symmetric rank minimization program and establish near-optimal sample complexity bounds when the underlying distribution is log-concave. Our measurement model involves random symmetric rank-one tensors, leading to involved proba- bility calculations. To address these challenges, we employ the Carbery-Wright inequality, a power- ful tool for studying anti-concentration properties of random polynomials, and leverage orthogonal polynomial expansions. Additionally, we provide a sample complexity lower bound via Fano’s inequality, and discuss broader implications of our results for two-layer polynomial networks.

The Ising p-spin glass and random k-SAT are two canonical examples of disordered systems that play a central role in understanding the link between geometric features of optimization landscapes and computational tractability. Both models exhibit hard regimes where all known polynomial-time algorithms fail and possess the multi Overlap Gap Property (m-OGP), an intricate geometrical property that rigorously rules out a broad class of algorithms exhibiting input stability. We establish that, in both models, the symmetric m-OGP undergoes a sharp phase transition, and we pinpoint its exact threshold. For the Ising p-spin glass, our results hold for all sufficiently large p; for the random k-SAT, they apply to all k growing mildly with the number of Boolean variables. Notably, our findings yield qualitative insights into the power of OGP-based arguments. A particular consequence for the Ising p-spin glass is that the strength of the m-OGP in establishing algorithmic hardness grows without bound as m increases. These are the first sharp threshold results for the m-OGP. Our analysis hinges on a judicious application of the second moment method, enhanced by concentration. While a direct second moment calculation fails, we overcome this via a refined approach that leverages an argument of Frieze [Frieze, 1990] and exploiting concentration properties of carefully constructed random variables.

We introduce a random constraint satisfaction problem (CSP) with non-uniform constraints that is closely related to the average-case discrepancy minimization problem in the non-proportional regime. Our proposal is particularly motivated by randomized controlled trials (RCTs) in statistics, involving different constraints. For the random CSP that we propose, we establish a sharp phase transition result regarding the existence of its solutions. We then precisely pinpoint the distance between the solution spaces corresponding to independent problem instances. In the context of RCTs, this quantifies the amount of reassignments needed if a similar RCT is to be repeated with an independent population and/or a potentially different set of constraints. We lastly study the solution space geometry, and show that, for certain values of constraints, the solutions are isolated singletons separated by linear Hamming distance.

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 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 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, β*〉|.