Semidefinite programs simulate approximate message passing robustly
Misha Ivkov Tselil Schramm
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.