Sharp link established between message passing and polynomial estimation

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

Data Structures and Algorithms

Summary

This paper studies a math problem where you try to find a hidden pattern in noisy data using polynomial functions. The authors show that a certain kind of method called approximate message passing (AMP) matches the best possible error achievable by such polynomial methods, even as the polynomial degree grows slowly with data size. They extend previous results by carefully analyzing dependencies in the variables involved, using a new technique based on conditional joint cumulants. This work clarifies exactly how well polynomial algorithms can estimate the hidden signal compared to AMP methods.

What this means in practice

  • For machine learning engineers: Evaluate the theoretical limits of polynomial-based algorithms for signal detection tasks with noise modeled by Gaussian distributions.
  • For statistical signal processors: Design signal recovery methods knowing the precise error floor for polynomial degree growth relative to approximate message passing performance.

A theory result. No direct application yet.

Authors

Zhangsong Li

Abstract

We prove a sharp lower bound for growing-degree polynomial estimation in the Gaussian planted submatrix model. The observation is $$ \boldsymbol{Y}= \fracλ{\sqrt{n}} \boldsymbolθ \boldsymbolθ^{\top}+\boldsymbol{W}, $$ where the coordinates of $\boldsymbolθ$ are independent $\mathsf{Ber}(ρ)$ variables and $\boldsymbol{W}$ is symmetric with independent standard Gaussian upper-triangular entries. For every fixed $λ>0$ and $ρ\in(0,1)$, 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 $ρ-q_{\mathsf{amp}}/λ$, the limiting error of Bayes approximate message passing (AMP). This extends the constant-degree result of Montanari and Wein~\cite{montanari2025equivalence} for the Bernoulli prior. 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 therefore resolves the Bernoulli rank-one case of the growing-degree AMP-equivalence question discussed in~\cite{wein2025computational, maleki2026high}. The proof constructs a low-degree certificate using \emph{conditional} joint cumulants of the signal coordinates and their products. Specifically, we condition on 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. Most of the arguments in this paper were generated using GPT-6 Astra.