# Graph-based Approximate Message Passing Iterations arXiv: https://arxiv.org/abs/2109.11905 ยท HTML: https://mlsanity.com/paper/2109.11905/ ## Key facts - Cited by 35 papers in the map (data through 14 Oct 2026). - Builds on 12 of its 42 references that are in the map. - First posted on arXiv 24 Sep 2021. ## Builds on (most cited first, 12 of 12) - [Expectation Propagation for approximate Bayesian inference](https://mlsanity.com/paper/1301.2294/) (2013) - [Statistical physics of inference: Thresholds and algorithms](https://mlsanity.com/paper/1511.02476/) (2015) - [The committee machine: Computational to statistical gaps in learning a two-layers neural network](https://mlsanity.com/paper/1806.05451/) (2018) - [Generalization error in high-dimensional perceptrons: Approaching Bayes error with convex optimization](https://mlsanity.com/paper/2006.06560/) (2020) - [Approximate Message Passing algorithms for rotationally invariant matrices](https://mlsanity.com/paper/2008.11892/) (2020) - [Finite Sample Analysis of Approximate Message Passing Algorithms](https://mlsanity.com/paper/1606.01800/) (2016) - [The spiked matrix model with generative priors](https://mlsanity.com/paper/1905.12385/) (2019) - [Universality of Approximate Message Passing Algorithms](https://mlsanity.com/paper/2003.10431/) (2020) - [Phase Transitions in Sparse PCA](https://mlsanity.com/paper/1503.00338/) (2015) - [Inference in Deep Networks in High Dimensions](https://mlsanity.com/paper/1706.06549/) (2017) - [Multi-Layer Generalized Linear Estimation](https://mlsanity.com/paper/1701.06981/) (2017) - [Inference in Multi-Layer Networks with Matrix-Valued Unknowns](https://mlsanity.com/paper/2001.09396/) (2020) ## Built on by (most cited first, 30 of 35) - [Bayes-optimal learning of an extensive-width neural network from quadratically many samples](https://mlsanity.com/paper/2408.03733/) (2024) - [Scaling Laws and Spectra of Shallow Neural Networks in the Feature Learning Regime](https://mlsanity.com/paper/2509.24882/) (2025) - [Fluctuations, Bias, Variance & Ensemble of Learners: Exact Asymptotics for Convex Losses in High-Dimension](https://mlsanity.com/paper/2201.13383/) (2022) - [Fundamental computational limits of weak learnability in high-dimensional multi-index models](https://mlsanity.com/paper/2405.15480/) (2024) - [Theoretical characterization of uncertainty in high-dimensional linear classification](https://mlsanity.com/paper/2202.03295/) (2022) - [Learning curves for the multi-class teacher-student perceptron](https://mlsanity.com/paper/2203.12094/) (2022) - [On double-descent in uncertainty quantification in overparametrized models](https://mlsanity.com/paper/2210.12760/) (2022) - [Asymptotics of Non-Convex Generalized Linear Models in High-Dimensions: A proof of the replica formula](https://mlsanity.com/paper/2502.20003/) (2025) - [Classification of Heavy-tailed Features in High Dimensions: a Superstatistical Approach](https://mlsanity.com/paper/2304.02912/) (2023) - [The Nuclear Route: Sharp Asymptotics of ERM in Overparameterized Quadratic Networks](https://mlsanity.com/paper/2505.17958/) (2025) - [Optimal scaling laws in learning hierarchical multi-index models](https://mlsanity.com/paper/2602.05846/) (2026) - [Optimal Algorithms for the Inhomogeneous Spiked Wigner Model](https://mlsanity.com/paper/2302.06665/) (2023) - [Fundamental limits of community detection from multi-view data: multi-layer, dynamic and partially labeled block models](https://mlsanity.com/paper/2401.08167/) (2024) - [A High Dimensional Statistical Model for Adversarial Training: Geometry and Trade-Offs](https://mlsanity.com/paper/2402.05674/) (2024) - [Approximate Message Passing for the Matrix Tensor Product Model](https://mlsanity.com/paper/2306.15580/) (2023) - [Single-Head Attention in High Dimensions: A Theory of Generalization, Weights Spectra, and Scaling Laws](https://mlsanity.com/paper/2509.24914/) (2025) - [Spectral Estimators for Structured Generalized Linear Models via Approximate Message Passing](https://mlsanity.com/paper/2308.14507/) (2023) - [Matrix Denoising with Doubly Heteroscedastic Noise: Fundamental Limits and Optimal Spectral Methods](https://mlsanity.com/paper/2405.13912/) (2024) - [Neural-prior stochastic block model](https://mlsanity.com/paper/2303.09995/) (2023) - [Analysis of Bootstrap and Subsampling in High-dimensional Regularized Regression](https://mlsanity.com/paper/2402.13622/) (2024) - [Mixed Regression via Approximate Message Passing](https://mlsanity.com/paper/2304.02229/) (2023) - [Multinomial Logistic Regression: Asymptotic Normality on Null Covariates in High-Dimensions](https://mlsanity.com/paper/2305.17825/) (2023) - [Bilinear Sequence Regression: A Model for Learning from Long Sequences of High-dimensional Tokens](https://mlsanity.com/paper/2410.18858/) (2024) - [Bayes optimal learning of attention-indexed models](https://mlsanity.com/paper/2506.01582/) (2025) - [Bayes optimal learning in high-dimensional linear regression with network side information](https://mlsanity.com/paper/2306.05679/) (2023) - [Fundamental limits of Non-Linear Low-Rank Matrix Estimation](https://mlsanity.com/paper/2403.04234/) (2024) - [Dimension-Free Bounds for Generalized First-Order Methods via Gaussian Coupling](https://mlsanity.com/paper/2508.10782/) (2025) - [A Noise Sensitivity Exponent Controls Large Statistical-to-Computational Gaps in Single- and Multi-Index Models](https://mlsanity.com/paper/2603.17896/) (2026) - [Lasso Universality Under Linearly Dependent Covariates in the Sparse Regime](https://mlsanity.com/paper/2608.08390/) (2026) - [A Convergence Analysis of Approximate Message Passing with Non-Separable Functions and Applications to Multi-Class Classification](https://mlsanity.com/paper/2402.08676/) (2024) ## Abstract (arXiv) Approximate-message passing (AMP) algorithms have become an important element of high-dimensional statistical inference, mostly due to their adaptability and concentration properties, the state evolution (SE) equations. This is demonstrated by the growing number of new iterations proposed for increasingly complex problems, ranging from multi-layer inference to low-rank matrix estimation with elaborate priors. In this paper, we address the following questions: is there a structure underlying all AMP iterations that unifies them in a common framework? Can we use such a structure to give a modular proof of state evolution equations, adaptable to new AMP iterations without reproducing each time the full argument ? We propose an answer to both questions, showing that AMP instances can be generically indexed by an oriented graph. This enables to give a unified interpretation of these iterations, independent from the problem they solve, and a way of composing them arbitrarily. We then show that all AMP iterations indexed by such a graph admit rigorous SE equations, extending the reach of previous proofs, and proving a number of recent heuristic derivations of those equations. Our proof naturally includes non-separable functions and we show how existing refinements, such as spatial coupling or matrix-valued variables, can be combined with our framework.