mlsanityData to 7 Oct 2026

Semidefinite programs simulate approximate message passing robustly

arXiv 2311.09017 ↗First posted 15 Nov 2023cs.DS cs.LG math.STcited by 6

Not on the map. Why?

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.

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

Builds on

19 of 41 references.

References · 19

  1. 2017Mixture Models, Robustness, and Sum of Squares Proofscited by 81
  2. 2014A statistical model for tensor PCAcited by 72
  3. 2017The power of sum-of-squares for detecting hidden structurescited by 54
  4. 2020Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalentcited by 51
  5. 2021A unifying tutorial on Approximate Message Passingcited by 49
  6. 2017Estimation of Low-Rank Matrices via Approximate Message Passingcited by 41
  7. 2015Tensor principal component analysis via sum-of-squares proofscited by 35
  8. 2020The estimation error of general first order methodscited by 33
  9. 2019Computational Hardness of Certifying Bounds on Constrained PCA Problemscited by 30
  10. 2018High-dimensional estimation via sum-of-squares proofscited by 25
  11. 2018Optimization of the Sherrington-Kirkpatrick Hamiltoniancited by 20
  12. 2021Robust recovery for stochastic block modelscited by 18
7 more
  1. 2022A Non-Asymptotic Framework for Approximate Message Passing in Spiked Modelscited by 18
  2. 2019The Kikuchi Hierarchy and Tensor PCAcited by 15
  3. 2019Local Statistics, Semidefinite Programming, and Community Detectioncited by 14
  4. 2020Spectral Planting and the Hardness of Refuting Cuts, Colorability, and Communities in Random Graphscited by 13
  5. 2022Minimax Rates for Robust Community Detectioncited by 12
  6. 2019Lifting Sum-of-Squares Lower Bounds: Degree-2 to Degree-4cited by 9
  7. 2019A Tight Degree 4 Sum-of-Squares Lower Bound for the Sherrington-Kirkpatrick Hamiltoniancited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 4; 2025: 0; 2026: 2.

6 papers.

  1. 2024Fast, robust approximate message passingcited by 3
  2. 2024Unrolled denoising networks provably learn optimal Bayesian inferencecited by 1
  3. 2026Computation-Utility-Privacy Tradeoffs in Bayesian Estimationcited by 1
  4. 2024Adversarially-Robust Inference on Trees via Belief Propagationcited by 0
  5. 2024Robust Random Graph Matching in Dense Graphs via an Approximate Message Passing Type Algorithmcited by 0
  6. 2026Easy, robust approximate message passing for planted spike modelscited by 0