Optimality of AMP Among Low-Degree Polynomials

The approximate message passing (AMP) framework has been widely successful at producing algorithms with provable guarantees for a variety of high-dimensional statistical inference tasks. In some settings, AMP is conjectured to be optimal in the sense that no computationally efficient estimator can achieve a better mean squared error (MSE) than AMP. In a simple "signal plus noise" model (spiked Wigner), we prove a variant of this conjecture by showing that AMP has the best possible MSE within the larger class of constant-degree polynomials. This result is sharper than existing low-degree lower bounds, matching AMP's exact asymptotic MSE. The proof sheds some light on what makes AMP optimal for some problems but not others. This is joint work with Andrea Montanari that began at the Simons Institute.