Semidefinite programs simulate approximate message passing robustly
This offers robust polynomial-time algorithms for average-case optimization problems like max-cut-gain, addressing a gap where previous SDP relaxations had strong lower bounds.
The paper shows that a broad class of approximate message passing (AMP) algorithms can be simulated in polynomial time by semidefinite programs (SDPs) with local statistics hierarchy, even when up to 1/polylog(dimension) of the data is adversarially corrupted, providing the first robust guarantees for many average-case optimization problems.
Approximate message passing (AMP) is a family of iterative algorithms that generalize matrix power iteration. AMP algorithms are known to optimally solve many average-case optimization problems. In this paper, we show that a large class of AMP algorithms can be simulated in polynomial time by \emph{local statistics hierarchy} semidefinite programs (SDPs), even when an unknown principal minor of measure $1/\mathrm{polylog}(\mathrm{dimension})$ is adversarially corrupted. Ours are the first robust guarantees for many of these problems. Further, our results offer an interesting counterpoint to strong lower bounds against less constrained SDP relaxations for average-case max-cut-gain (a.k.a. "optimizing the Sherrington-Kirkpatrick Hamiltonian") and other problems.