Semidefinite programs simulate approximate message passing robustly

Approximate message passing (AMP) is a family of iterative algorithms that are known to optimally solve many high-dimensional statistics optimization problems. In this talk, I will explain how to simulate a broad class of AMP algorithms in polynomial time using "local statistics hierarchy" semidefinite programs (SDPs), with the added benefit of robustness: the SDPs work even in the strong contamination model, when an unknown (but bounded) subset of the input data 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 problems where AMP is known to succeed.

This is based on joint work with Misha Ivkov.