# Semidefinite programs simulate approximate message passing robustly

arXiv: https://arxiv.org/abs/2311.09017 · HTML: https://mlsanity.com/paper/2311.09017/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 41 references that are in the map.
- First posted on arXiv 15 Nov 2023.

## Builds on (most cited first, 19 of 19)

- [Mixture Models, Robustness, and Sum of Squares Proofs](https://mlsanity.com/paper/1711.07454/) (2017)
- [A statistical model for tensor PCA](https://mlsanity.com/paper/1411.1076/) (2014)
- [The power of sum-of-squares for detecting hidden structures](https://mlsanity.com/paper/1710.05017/) (2017)
- [Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalent](https://mlsanity.com/paper/2009.06107/) (2020)
- [A unifying tutorial on Approximate Message Passing](https://mlsanity.com/paper/2105.02180/) (2021)
- [Estimation of Low-Rank Matrices via Approximate Message Passing](https://mlsanity.com/paper/1711.01682/) (2017)
- [Tensor principal component analysis via sum-of-squares proofs](https://mlsanity.com/paper/1507.03269/) (2015)
- [The estimation error of general first order methods](https://mlsanity.com/paper/2002.12903/) (2020)
- [Computational Hardness of Certifying Bounds on Constrained PCA Problems](https://mlsanity.com/paper/1902.07324/) (2019)
- [High-dimensional estimation via sum-of-squares proofs](https://mlsanity.com/paper/1807.11419/) (2018)
- [Optimization of the Sherrington-Kirkpatrick Hamiltonian](https://mlsanity.com/paper/1812.10897/) (2018)
- [A Non-Asymptotic Framework for Approximate Message Passing in Spiked Models](https://mlsanity.com/paper/2208.03313/) (2022)
- [Robust recovery for stochastic block models](https://mlsanity.com/paper/2111.08568/) (2021)
- [The Kikuchi Hierarchy and Tensor PCA](https://mlsanity.com/paper/1904.03858/) (2019)
- [Local Statistics, Semidefinite Programming, and Community Detection](https://mlsanity.com/paper/1911.01960/) (2019)
- [Spectral Planting and the Hardness of Refuting Cuts, Colorability, and Communities in Random Graphs](https://mlsanity.com/paper/2008.12237/) (2020)
- [Minimax Rates for Robust Community Detection](https://mlsanity.com/paper/2207.11903/) (2022)
- [Lifting Sum-of-Squares Lower Bounds: Degree-2 to Degree-4](https://mlsanity.com/paper/1911.01411/) (2019)
- [A Tight Degree 4 Sum-of-Squares Lower Bound for the Sherrington-Kirkpatrick Hamiltonian](https://mlsanity.com/paper/1907.11686/) (2019)

## Built on by (most cited first, 6 of 6)

- [Fast, robust approximate message passing](https://mlsanity.com/paper/2411.02764/) (2024)
- [Unrolled denoising networks provably learn optimal Bayesian inference](https://mlsanity.com/paper/2409.12947/) (2024)
- [Computation-Utility-Privacy Tradeoffs in Bayesian Estimation](https://mlsanity.com/paper/2603.18254/) (2026)
- [Adversarially-Robust Inference on Trees via Belief Propagation](https://mlsanity.com/paper/2404.00768/) (2024)
- [Robust Random Graph Matching in Dense Graphs via an Approximate Message Passing Type Algorithm](https://mlsanity.com/paper/2412.16457/) (2024)
- [Easy, robust approximate message passing for planted spike models](https://mlsanity.com/paper/2606.00500/) (2026)

## Abstract (arXiv)

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 local statistics hierarchy semidefinite programs (SDPs), even when an unknown principal minor of measure 1/polylog(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.