CS Paper Radar

Almost Sharp Equivalence between Approximate Message Passing and Low-Degree Polynomials

Zhangsong Li

cs.DS math.STmath.PR ·submitted 2026-09-07 03:29 UTC · v2
theory

Abstract

We prove a sharp lower bound for growing-degree polynomial estimation in the symmetric rank-one matrix estimation problem. The observation is \[ \boldsymbol{Y}=\frac{1}{\sqrt{n}} \boldsymbolθ \boldsymbolθ^{\top}+\boldsymbol{W}, \] where the coordinates of $\boldsymbolθ$ are independent with a common, fixed sub-Gaussian distribution $π_Θ$ satisfying $\mathbb E[Θ]\neq0$, and $\boldsymbol{W}$ is symmetric with independent standard Gaussian upper-triangular entries. For every such prior, we give an explicit finite-dimensional bound implying that every sequence of polynomial estimators of degree $D(n)=o(n^{1/60})$ has normalized mean-square error with limit inferior at least $\mathbb E[Θ^2]-q_{\mathsf{amp}}$, the limiting error of Bayes approximate message passing (AMP). This extends the constant-degree equivalence of Montanari and Wein~\cite{montanari2025equivalence} to growing degree under the same prior assumptions. Combined with their polynomial approximation of fixed-iteration AMP, the bound identifies the exact limiting low-degree MMSE whenever $D(n)\to\infty$ within this range. It thereby answers the growing-degree AMP-equivalence question discussed in~\cite{wein2025computational, maleki2026high} for nonzero-mean sub-Gaussian priors in the stated degree range. We also obtain a moment-dependent finite-dimensional lower bound for any nonzero-mean prior with all moments finite. The proof bounds low-degree MMSE using \emph{conditional} joint cumulants and a refined application of Jensen's inequality. The conditional cumulants are defined using an auxiliary Gaussian channel $\boldsymbol{R}$ calibrated to the AMP fixed point. This retains signal dependence that is lost in unconditional cumulant bounds and produces the cancellations needed for quantitative control as the degree grows.

Comment
29 pages, 2 figures; extended the results and added a detailed description of AI usage

Closest papers

Nearest neighbours by meaning across the whole index.

On Complexity of Gaussian Sampling

cs.CC stat.CO ·2026-10-14 ·Huanjian Zhou, Taiji Suzuki
theory similarity 0.64
Abstract · 36 pages

We study the number of exact matrix-vector queries needed to sample a centered $d$-dimensional Gaussian with condition number at most $κ$ to total variation error $\varepsilon$. The best known algorithm uses $O(\min\{d,\sqrtκ\log(\frac{d}{\varepsilon})\})$ queries, while the known lower bounds do not grow as $\varepsilon\to0$ and match this bound only for $κ\le d^{1/5-δ}$ at constant accuracy. We introduce a construction based on a hidden determinant sign and prove a lower bound of $Ω\!\left(\min\left\{d,\sqrtκ\log\left(1+\frac{d}{\sqrtκ\,\varepsilon}\right)\right\}\right)$ uniformly for all $d\ge1$, $κ\ge4$, and $0<\varepsilon\le\tfrac{1}{16}$. This bound matches the known upper bound up to constant factors whenever $κ\le d^{2-δ}$ for fixed $δ\in(0,2)$, or $\varepsilon\le d^{-c}$ for fixed $c>0$. We also extend a recent fixed-spectrum construction with a hidden eigenbasis from $κ=2$ to $2\leκ\le d^{1-δ}$, for any fixed $δ\in(0,1)$. This gives an $Ω_δ(\sqrtκ\log d)$ lower bound at constant accuracy that holds even when the spectrum of the precision matrix is known to the algorithm.

0.13

A Walk From Free Probability to Matrix Discrepancy I: Matrix Spencer

cs.DS ·2026-09-16 ·Tarun Kathuria
theory similarity 0.64
Abstract · The authors explicitly reserve all rights in this work. No permission is granted for the reproduction, storage, or use of this document for …

The Matrix Spencer conjecture asks whether any $n$ real symmetric matrices A_1,...,A_n \in \mathbb{R}^{m \times m} of operator norm at most one admit a signing $x\in\{-1,1\}^n$ such that the operator norm of the signed sum is at most O(\sqrt{n \log(2m/n)}) We give a randomized algorithm establishing this bound with polynomial runtime in the real-arithmetic model. We first prove the $O(\sqrt n)$ bound for $m\le n$, resolving the square case, and then obtain the rectangular bound by changing the regularizer. As in earlier algorithmic discrepancy methods \cite{lovettmeka2012,bansalLaddhaVempala2022,pesentivladu2026}, we run a covariance-controlled random walk from the origin of the hypercube, rounding coordinates near its faces and keeping them fixed. Our potential measures a soft spectral edge of the evolving discrepancy matrix perturbed by an operator-valued free semicircular element. Inspired by the free interpolation approach of \cite{bbvh2023}, we combine Lehner's variational formula for the free edge \cite{lehner1999} with spectral Tsallis regularization \cite{allenZhuLiaoOrecchia2015,pesentivladu2026}. This puts the discrepancy and remaining covariance in a single smooth optimization problem. The potential has a finite-dimensional semidefinite formulation. Stability of its optimizer, governed by equations related to the matrix Dyson equation \cite{erdos2019}, lets us find a large subspace in which to move while controlling discrepancy. The square case uses the Tsallis--$1/2$ regularizer; the rectangular case uses a suitable generalized Tsallis power regularizer. Our companion paper \cite{kathuria2026ks} applies these ideas to give an algorithmic proof of Weaver's discrepancy theorem, whose existence proof by [MSS15] resolved the Kadison--Singer conjecture \cite{mss2015}.Lean formalizations of our main discrepancy theorems have been completed and will be released shortly.

0.49

Dimension-Free Private Mean Estimation is Impossible Without the Covariance

cs.LG cs.DS ·2026-11-04 ·Renaud Gaucher, Ephraim Linder, Adam Smith, Jonathan Ullman, Lydia Zakynthinou
similarity 0.63
Abstract

We study the limits of differentially private Gaussian mean estimation when the covariance matrix is unknown. Prior work shows that when the covariance $Σ$ is known, the optimal sample complexity can depend only on its spectrum, rather than on the ambient dimension $d$. We establish new lower bounds for Gaussian mean estimation with Euclidean error which show that private estimators cannot achieve similar guarantees when the covariance is unknown. First, when the sample size $n$ is smaller than the effective dimension $\mathrm{trace}(Σ)/\|Σ\|_{\text{op}}$, the optimal error when the covariance is unknown can be larger than the optimal error when it is known by a factor of $\sqrt{d/n}$. Second, when the sample size is larger than the effective dimension, even for diagonal covariance matrices with effective dimension bounded by $\log d$, the optimal error when the covariance is unknown can be larger than the optimal error when it is known by a factor of $\sqrt{d}/n^{3/2}$. Together, these results show that in the unknown covariance setting, exploiting anisotropic structure under differential privacy can require a dimension-dependent error or sample complexity.

0.21

Nuclear Norm-Regularized Bayesian Matrix Completion

cs.LG stat.ML ·2026-09-24 ·Calvin Tolbert
similarity 0.62
Abstract · 40 pages, 7 figures

Nuclear-norm-regularized least squares is a standard approach to matrix completion, but it yields only a point estimate. Its Bayesian counterpart, a prior combining the nuclear norm with a Frobenius-norm term, gives a strongly log-concave though nonsmooth posterior when the noise precision is known. In practice the precision is unknown, and placing a truncated Jeffreys prior on it makes the joint posterior neither log-concave nor smooth. To our knowledge, we give the first sampler for this model with an explicit non-asymptotic guarantee: its output is within a prescribed total-variation or Wasserstein distance of the posterior on the matrix after a number of steps polynomial in the matrix dimensions and the reciprocal of the target accuracy. The sampler never targets a continuous distribution that is not strongly log-concave. It discretizes the precision onto a grid, estimates its posterior by thermodynamic integration along the tilted conditional posteriors of the matrix, and bounds the error this propagates to the posterior on the matrix. The approach applies whenever non-log-concavity is confined to a bounded scalar hyperparameter and the conditional distributions are strongly log-concave with smooth-plus-Lipschitz potentials. Our result establishes feasibility; the polynomial complexity is not intended as a practical algorithm at current problem scales.

0.26

Information-Theoretic Limits for Rectangular Spiked Matrix Models with Rotationally Invariant Noise

cs.IT cond-mat.dis-nnmath.ST ·2026-10-12 ·Qun Chen, Rudy Skerk, Jean Barbier, Francesco Camilli, Junjie Ma +1 more
similarity 0.61
Abstract

We study the information-theoretic limits of inference in rectangular rank-one spiked matrix models with additive rotationally invariant noise, thereby going beyond the standard assumption of independent noise entries. Using the replica method from statistical physics, we derive a variational formula for the mutual information between the signal and the data, together with a system of saddle point equations predicting the minimum mean squared error in estimating the rank-one spike. We further show that, in the Bayes-optimal setting, these saddle point equations coincide with the fixed point equations of the state evolution of a recently proposed orthogonal approximate message passing algorithm with Bayes-optimal denoisers. This equivalence provides an algorithmic interpretation of the replica prediction and supports the Bayes-optimality of orthogonal approximate message passing whenever the relevant fixed point is unique. Numerical evaluations of the saddle point equations for several rotationally invariant noise ensembles and signal priors, together with finite-size simulations of the algorithm, confirm the asymptotic predictions. They illustrate both regimes with a unique informative fixed point, where orthogonal approximate message passing is predicted to attain the minimum mean squared error, and regimes with multiple fixed points, where a statistical-to-computational gap exists.

0.39

Polynomial-Time MIMO Detection at the Maximum-Likelihood Threshold

cs.IT ·2026-09-16 ·Dimitris Papailiopoulos
theory similarity 0.61
Abstract · 51 pages

We prove that exact block recovery in the square Gaussian binary MIMO model can be achieved in polynomial time at the same first-order SNR threshold as exhaustive maximum-likelihood detection. Specifically, for $y=\sqrt{ρ/N}Hx^\star+w, \; x^\star\in\{\pm1\}^N,$ and independent standard Gaussian $H\in\mathbb R^{N\times N}$ and $w$, rounded linear MMSE followed by steepest single-bit descent recovers $x^\star$ with failure probability tending to zero, uniformly over every transmitted word and every $ρ\ge2\log N$, using $O(N^3)$ unit-cost exact-real arithmetic operations. The model is a special case of Gaussian random linear estimation, for which AMP state evolution and replica/MMSE formulas rigorously characterize fixed-parameter normalized performance. Those results predict the same $2\log N$ scale, but do not by themselves yield an all-coordinate guarantee in the dimension-dependent regime considered here. To the best of our knowledge, no prior work gives polynomial-time exact block recovery at the ML boundary for this setting; the closest prior square-system theorem, for the box relaxation, has first-order threshold $4\log N$. The proof places the rounded LMMSE estimate at sublinear Hamming distance from the truth, and then establishes, uniformly over every error set the local search can visit, that some wrong bit offers a quantified cost decrease while an objective barrier confines the search path. Conversely, if $0<ρ\le2\log N-\log\log N-s_N$ with $s_N\to\infty$ and $s_N=o(\log N)$, then a one-bit neighbor beats the transmitted word with probability tending to one, so even ML detection fails. Therefore, the statistical and polynomial-time exact-recovery thresholds coincide to first order in the stated arithmetic model.

0.20

Matrix Spencer: Eight Standard Deviations Suffice and an Almost-Linear Time Algorithm for Dense Input

cs.DS math.FAmath.OCmath.PR ·2026-09-14 ·Zhao Song, Lichen Zhang
theory similarity 0.61
Abstract

The Matrix Spencer conjecture asserts that for all symmetric matrices $A_1,\ldots,A_n\in\mathbb{R}^{n\times n}$ with $\|A_i\|\le1$ there are signs $\varepsilon_1,\ldots,\varepsilon_n\in\{-1,1\}$ with $\|\sum_{i=1}^n\varepsilon_iA_i\|=O(\sqrt n)$. We prove it: a signing of discrepancy below $8\sqrt n$ always exists. We also give a randomized algorithm that finds a signing of discrepancy below $12\sqrt n$ with failure probability at most $p$. The algorithm uses $n^{3+o(1)}\operatorname{polylog}(1/p)$ arithmetic operations in the real-arithmetic model. This matches the size $n^3$ of the dense input up to subpolynomial factors. In the other direction, we prove that for every $n$ there are collections of symmetric matrices such that every signing has discrepancy at least $(2-o(1))\sqrt{n}$. We present three different proofs of the matrix Spencer conjecture. The key to every proof is a hereditary small-ball estimate. This is a lower bound on the Gaussian measure of the spectral body $\{x\in \mathbb{R}^n:\|\sum_ix_iA_i\|\le R\}$ that holds for every subfamily of the matrices. The other ingredient turns that Gaussian measure into a partial signing. We give three approaches to obtain such a signing. The first one covers the cube by partially signed faces through Gaussian concentration with a constant $7\cdot10^9$. The second proof replaces the covering by a projection lemma with explicit parameters for a constant $156000$. The third proof turns Gaussian measure into signs by a lossless coding, with no union bound. It proves the estimate at the right radius with smooth spectral barriers and certified coefficients. It gives a constant below $7.88$. For algorithms, the main idea is to project Gaussian points onto a smoothed spectral body. The $n^{3+o(1)}$ time algorithm tracks the Gibbs matrix of that body across coordinate-descent steps with sketched increments and random refreshes.

0.47

Hardness of Approximation for Polynomial Optimization over Sphere for Linear Programming Relaxation Hierarchy

cs.CC ·2026-11-06 ·Mrinalkanti Ghosh
theory similarity 0.61
Abstract

Semidefinite programming (SDP), particularly the sum-of-squares (SoS) hierarchy, provides $n^{O(q)}$-time approximation and certification algorithms for optimizing degree-$d$ homogeneous polynomials on the unit sphere. For arbitrary inputs, degree-$q$ SoS gives a powered-objective approximation factor $O_d((n/q)^{d/2-1})$ [BGGLT17]. For random order-$d$ tensors, degree-$d$ SoS has an integrality-gap lower bound of $2^{-O(d)}(n/d)^{d/4-1/2}$ relative to the true spherical maximum; lower bounds also extend to growing SoS degree in tensor PCA [BGL17,HKP17]. We establish lower bounds for weaker linear-programming relaxation hierarchies. Our degree-$q$ moment LPs impose the sphere identities and any prescribed, instance-independent family $\mathcal{G}$ of valid polynomial inequalities of degree at most $q$. They include Sherali--Adams-type product hierarchies. For every even $d\ge2$, constant $C>0$, and $q$ satisfying $2d | q$ and $2d\le q\le n$, every such relaxation with at most $n^{Cq}$ tests has instances $P$ satisfying \[ \frac{\mathrm{PowLP}_{q,\mathcal{G}}(P)}{\|P\|_\infty}\ge \frac{c_{d,C}}{\sqrt{q\log n}}\left(\frac nq\right)^{d/2-1/2}.\] Here $\|P\|_\infty$ is the maximum absolute value of the polynomial over the sphere and $\mathrm{PowLP}_{q,\mathcal{G}}(P)$ is the relaxed objective. The exponent $d/2-1/2$ improves the leading dependence on $d$ relative to the $d/4$-type exponents in prior random-tensor SoS lower bounds. Our LP hierarchies impose weaker positivity conditions than semidefinite moment relaxations. It leaves open whether analogous degree dependence can be achieved in lower bounds for SDP hierarchies.

0.25