mlsanityData to 7 Oct 2026

Graph-based Approximate Message Passing Iterations

arXiv 2109.11905 ↗First posted 24 Sep 2021cs.IT math.IT math.PRcited by 35

Not on the map. Why?

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.

Key facts. Cited by 35 papers in the map (data through 7 Oct 2026). Builds on 12 of its 42 references that are in the map. First posted on arXiv 24 Sep 2021.

Builds on

12 of 42 references.

References · 12

  1. 2013Expectation Propagation for approximate Bayesian inferencecited by 172
  2. 2015Statistical physics of inference: Thresholds and algorithmscited by 128
  3. 2018The committee machine: Computational to statistical gaps in learning a two-layers neural networkcited by 58
  4. 2020Generalization error in high-dimensional perceptrons: Approaching Bayes error with convex optimizationcited by 51
  5. 2020Approximate Message Passing algorithms for rotationally invariant matricescited by 31
  6. 2016Finite Sample Analysis of Approximate Message Passing Algorithmscited by 20
  7. 2019The spiked matrix model with generative priorscited by 20
  8. 2020Universality of Approximate Message Passing Algorithmscited by 16
  9. 2015Phase Transitions in Sparse PCAcited by 15
  10. 2017Multi-Layer Generalized Linear Estimationcited by 12
  11. 2017Inference in Deep Networks in High Dimensionscited by 12
  12. 2020Inference in Multi-Layer Networks with Matrix-Valued Unknownscited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 4; 2023: 8; 2024: 10; 2025: 7; 2026: 6.

35 papers.

Sort:

By area:

  1. 2024Bayes-optimal learning of an extensive-width neural network from quadratically many samplescited by 23
  2. 2022Fluctuations, Bias, Variance & Ensemble of Learners: Exact Asymptotics for Convex Losses in High-Dimensioncited by 19
  3. 2022Theoretical characterization of uncertainty in high-dimensional linear classificationcited by 18
  4. 2025Scaling Laws and Spectra of Shallow Neural Networks in the Feature Learning Regimecited by 18
  5. 2022Learning curves for the multi-class teacher-student perceptroncited by 17
  6. 2024Fundamental computational limits of weak learnability in high-dimensional multi-index modelscited by 17
  7. 2022On double-descent in uncertainty quantification in overparametrized modelscited by 15
  8. 2023Classification of Heavy-tailed Features in High Dimensions: a Superstatistical Approachcited by 11
  9. 2025Asymptotics of Non-Convex Generalized Linear Models in High-Dimensions: A proof of the replica formulacited by 11
  10. 2025The Nuclear Route: Sharp Asymptotics of ERM in Overparameterized Quadratic Networkscited by 11
  11. 2023Optimal Algorithms for the Inhomogeneous Spiked Wigner Modelcited by 8
  12. 2024Fundamental limits of community detection from multi-view data: multi-layer, dynamic and partially labeled block modelscited by 7
23 more
  1. 2023Approximate Message Passing for the Matrix Tensor Product Modelcited by 6
  2. 2026Optimal scaling laws in learning hierarchical multi-index modelscited by 6
  3. 2023Spectral Estimators for Structured Generalized Linear Models via Approximate Message Passingcited by 5
  4. 2024A High Dimensional Statistical Model for Adversarial Training: Geometry and Trade-Offscited by 5
  5. 2024Matrix Denoising with Doubly Heteroscedastic Noise: Fundamental Limits and Optimal Spectral Methodscited by 5
  6. 2025Single-Head Attention in High Dimensions: A Theory of Generalization, Weights Spectra, and Scaling Lawscited by 5
  7. 2023Neural-prior stochastic block modelcited by 4
  8. 2024Analysis of Bootstrap and Subsampling in High-dimensional Regularized Regressioncited by 4
  9. 2023Mixed Regression via Approximate Message Passingcited by 3
  10. 2023Multinomial Logistic Regression: Asymptotic Normality on Null Covariates in High-Dimensionscited by 3
  11. 2024Bilinear Sequence Regression: A Model for Learning from Long Sequences of High-dimensional Tokenscited by 3
  12. 2025Bayes optimal learning of attention-indexed modelscited by 3
  13. 2023Bayes optimal learning in high-dimensional linear regression with network side informationcited by 2
  14. 2024Fundamental limits of Non-Linear Low-Rank Matrix Estimationcited by 2
  15. 2025Dimension-Free Bounds for Generalized First-Order Methods via Gaussian Couplingcited by 2
  16. 2024A Convergence Analysis of Approximate Message Passing with Non-Separable Functions and Applications to Multi-Class Classificationcited by 1
  17. 2025Orthogonal Approximate Message Passing with Optimal Spectral Initializations for Rectangular Spiked Matrix Modelscited by 1
  18. 2026A Noise Sensitivity Exponent Controls Large Statistical-to-Computational Gaps in Single- and Multi-Index Modelscited by 1
  19. 2026Lasso Universality Under Linearly Dependent Covariates in the Sparse Regimecited by 1
  20. 2024Inferring Change Points in High-Dimensional Regression via Approximate Message Passingcited by 0
  21. 2026Decoupled Descent: Exact Test Error Tracking Via Approximate Message Passingcited by 0
  22. 2026How Width and Data Shape Generalization Scaling Laws in Quadratic Neural Networkscited by 0
  23. 2026DAIF: A Data-Driven Intermediate Fusion Framework for Multimodal Supervised Learning via Approximate Message Passingcited by 0