Almost Sharp Equivalence between Approximate Message Passing and Low-Degree Polynomials
Abstract
We prove a sharp lower bound for growing-degree polynomial estimation in the symmetric rank-one matrix estimation problem. The observation is Y=1/√n θ θ⊤+W, where the coordinates of θ are independent with a common, fixed sub-Gaussian distribution πΘ satisfying 𝔼[Θ]≠0, and 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(n1/60) has normalized mean-square error with limit inferior at least 𝔼[Θ2]−qamp, 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)→∞ 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 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.
Related
- Deriving Approximate Message Passing from the Convex Gaussian Min-Max Theorem
- Quantitative Universality of Approximate Message Passing for Rank-One Quadratic Sensing
- Universality of approximate message passing under a fourth-moment tail condition
- On the State Evolution of Approximate Message Passing with Discontinuous Denoisers
- DAIF: A Data-Driven Intermediate Fusion Framework for Multimodal Supervised Learning via Approximate Message Passing
BibTeX
@misc{li2026almost,
title = {{Almost Sharp Equivalence between Approximate Message Passing and Low-Degree Polynomials}},
author = {Zhangsong Li},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.06988},
eprint = {2609.06988},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.06988},
}
RIS
TY - UNPB
TI - Almost Sharp Equivalence between Approximate Message Passing and Low-Degree Polynomials
AU - Zhangsong Li
PY - 2026
DA - 2026/10/16
PB - arXiv
DO - 10.48550/arxiv.2609.06988
UR - https://arxiv.org/abs/2609.06988
AB - We prove a sharp lower bound for growing-degree polynomial estimation in the symmetric rank-one matrix estimation problem. The observation is Y=1/√n θ θ^⊤+W, where the coordinates of θ are independent with a common, fixed sub-Gaussian distribution π_Θ satisfying 𝔼[Θ]≠0, and 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 𝔼[Θ^2]−q_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)→∞ 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 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.
ER -