# Fast, robust approximate message passing

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 25 references that are in the map.
- First posted on arXiv 5 Nov 2024.

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

- [Sever: A Robust Meta-Algorithm for Stochastic Optimization](https://mlsanity.com/paper/1803.02815/) (2018)
- [A unifying tutorial on Approximate Message Passing](https://mlsanity.com/paper/2105.02180/) (2021)
- [Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors](https://mlsanity.com/paper/1512.02337/) (2015)
- [Optimization of the Sherrington-Kirkpatrick Hamiltonian](https://mlsanity.com/paper/1812.10897/) (2018)
- [Robust recovery for stochastic block models](https://mlsanity.com/paper/2111.08568/) (2021)
- [Universality of Approximate Message Passing Algorithms](https://mlsanity.com/paper/2003.10431/) (2020)
- [Robust Regression Revisited: Acceleration and Improved Estimation Rates](https://mlsanity.com/paper/2106.11938/) (2021)
- [Reaching Kesten-Stigum Threshold in the Stochastic Block Model under Node Corruptions](https://mlsanity.com/paper/2305.10227/) (2023)
- [Semidefinite programs simulate approximate message passing robustly](https://mlsanity.com/paper/2311.09017/) (2023)
- [Robust recovery for stochastic block models, simplified and generalized](https://mlsanity.com/paper/2402.13921/) (2024)

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

- [Computation-Utility-Privacy Tradeoffs in Bayesian Estimation](https://mlsanity.com/paper/2603.18254/) (2026)
- [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)

We give a fast, spectral procedure for implementing approximate-message passing (AMP) algorithms robustly. For any quadratic optimization problem over symmetric matrices X with independent subgaussian entries, and any separable AMP algorithm mathcal A, our algorithm performs a spectral pre-processing step and then mildly modifies the iterates of mathcal A. If given the perturbed input X + E ∈ mathbb Rn × n for any E supported on a varepsilon n × varepsilon n principal minor, our algorithm outputs a solution hat v which is guaranteed to be close to the output of mathcal A on the uncorrupted X, with |mathcal A(X) - hat v|2 ≤ f(varepsilon) |mathcal A(X)|2 where f(varepsilon) → 0 as varepsilon → 0 depending only on varepsilon.