A Unifying Tutorial on Approximate Message Passing

DOI10.1561/2200000092zbMATH Open1491.68152arXiv2105.02180OpenAlexW4292482091MaRDI QIDQ5863992FDOQ5863992

Cynthia Rush, Ramji Venkataramanan, Richard Samworth, Oliver Y. Feng

Publication date: 3 June 2022

Published in: Foundations and Trends® in Machine Learning (Search for Journal in Brave)

Abstract: Over the last decade or so, Approximate Message Passing (AMP) algorithms have become extremely popular in various structured high-dimensional statistical problems. The fact that the origins of these techniques can be traced back to notions of belief propagation in the statistical physics literature lends a certain mystique to the area for many statisticians. Our goal in this work is to present the main ideas of AMP from a statistical perspective, to illustrate the power and flexibility of the AMP framework. Along the way, we strengthen and unify many of the results in the existing literature.

Full work available at URL: https://arxiv.org/abs/2105.02180

Recommendations

• Approximate Message Passing With Consistent Parameter Estimation and Applications to Sparse Learning
• On the Convergence of Approximate Message Passing With Arbitrary Matrices
• Approximate Message Passing Algorithm With Universal Denoising and Gaussian Mixture Learning
• Universality of approximate message passing algorithms
• Vector Approximate Message Passing
• Approximate message passing with spectral initialization for generalized linear models*
• Hybrid Approximate Message Passing
• Expectation-Maximization Gaussian-Mixture Approximate Message Passing
• Bilinear Generalized Approximate Message Passing—Part I: Derivation

zbMATH Keywords

regressionrandomized algorithmsinformation theorydesign and analysis of algorithmsstatistical machine learningstatistical signal processing: estimation

Mathematics Subject Classification ID

Statistical aspects of information-theoretic topics (62B10) Learning and adaptive systems in artificial intelligence (68T05) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Research exposition (monographs, survey articles) pertaining to information and communication theory (94-02) Research exposition (monographs, survey articles) pertaining to statistics (62-02)

Cites Work

• Optimal errors and phase transitions in high-dimensional generalized linear models
• Optimization-Based AMP for Phase Retrieval: The Impact of Initialization and $\ell_{2}$ Regularization
• Capacity-Achieving Sparse Superposition Codes via Approximate Message Passing Decoding
• Approximate Message-Passing Decoder and Capacity Achieving Sparse Superposition Codes
• Surprises in high-dimensional ridgeless least squares interpolation
• Two Models of Double Descent for Weak Features
• Fundamental barriers to high-dimensional regression with convex penalties
• A precise high-dimensional asymptotic theory for boosting and minimum-\(\ell_1\)-norm interpolated classifiers
• The Generalization Error of Random Features Regression: Precise Asymptotics and the Double Descent Curve
• Algorithmic Analysis and Statistical Estimation of SLOPE via Approximate Message Passing
• Vector Approximate Message Passing
• A Simple Derivation of AMP and its State Evolution via First-Order Cancellation
• Approximate message passing algorithms for rotationally invariant matrices
• Fixed Points of Generalized Approximate Message Passing With Arbitrary Matrices
• On the Convergence of Approximate Message Passing With Arbitrary Matrices
• Consistent parameter estimation for Lasso and approximate message passing
• Rigorous Dynamics of Expectation-Propagation-Based Signal Recovery from Unitarily Invariant Measurements
• Decoding From Pooled Data: Phase Transitions of Message Passing
• The Replica-Symmetric Prediction for Random Linear Estimation With Gaussian Matrices Is Exact
• Analysis of Approximate Message Passing With Non-Separable Denoisers and Markov Random Field Priors
• A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
• Approximation Theorems of Mathematical Statistics
• Title not available (Why is that?)
• Title not available (Why is that?)
• Statistics for high-dimensional data. Methods, theory and applications.
• The committee machine: computational to statistical gaps in learning a two-layers neural network
• Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers
• Robust regression: Asymptotics, conjectures and Monte Carlo
• On the existence of maximum likelihood estimates in logistic regression models
• Title not available (Why is that?)
• Approximation by log-concave distributions, with applications to regression
• Robust Estimation of a Location Parameter
• Spectral analysis of large dimensional random matrices
• Eigenvalues of large sample covariance matrices of spiked population models
• Foundations of Modern Probability
• Real Analysis and Probability
• Title not available (Why is that?)
• An Invitation to Statistics in Wasserstein Space
• On Consistency and Sparsity for Principal Components Analysis in High Dimensions
• Asymptotics of sample eigenstructure for a large dimensional spiked covariance model
• Optimal Transport
• Robust Statistics
• Exact matrix completion via convex optimization
• Probabilistic graphical models.
• Minimax risk over \(l_ p\)-balls for \(l_ q\)-error
• False discoveries occur early on the Lasso path
• 10.1162/jmlr.2003.3.4-5.993
• Asymptotic behavior of M-estimators of p regression parameters when \(p^ 2/n\) is large. I. Consistency
• Title not available (Why is that?)
• Finding hidden cliques of size \(\sqrt{N/e}\) in nearly linear time
• SLOPE-adaptive variable selection via convex optimization
• Geometric measure theory.
• Tweedie’s Formula and Selection Bias
• An introduction to random matrices
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Complete Convergence and the Law of Large Numbers
• Asymptotic behavior of likelihood methods for exponential families when the number of parameters tends to infinity
• Minimax estimation via wavelet shrinkage
• Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices
• Title not available (Why is that?)
• A Stochastic Approach to the Gamma Function
• Title not available (Why is that?)
• Measurable selections of extrema
• Title not available (Why is that?)
• Title not available (Why is that?)
• Mean Field Models for Spin Glasses
• The largest eigenvalues of finite rank deformation of large Wigner matrices: Convergence and nonuniversality of the fluctuations
• The largest eigenvalue of rank one deformation of large Wigner matrices
• The isotropic semicircle law and deformation of Wigner matrices
• SLOPE is adaptive to unknown sparsity and asymptotically minimax
• High dimensional robust M-estimation: asymptotic variance via approximate message passing
• The LASSO Risk for Gaussian Matrices
• The eigenvalues and eigenvectors of finite, low rank perturbations of large random matrices
• Asymptotic behavior of M estimators of p regression parameters when \(p^ 2/n\) is large. II: Normal approximation
• Information, Physics, and Computation
• Minimax sparse principal subspace estimation in high dimensions
• Universality in polytope phase transitions and message passing algorithms
• Title not available (Why is that?)
• The Dynamics of Message Passing on Dense Graphs, with Applications to Compressed Sensing
• Statistical and computational trade-offs in estimation of sparse principal components
• An iterative construction of solutions of the TAP equations for the Sherrington-Kirkpatrick model
• State evolution for general approximate message passing algorithms, with applications to spatial coupling
• Title not available (Why is that?)
• Compressive Phase Retrieval via Generalized Approximate Message Passing
• Estimation of low-rank matrices via approximate message passing
• Constrained low-rank matrix estimation: phase transitions, approximate message passing and applications
• Randomly Spread CDMA: Asymptotics Via Statistical Physics
• A statistical-mechanics approach to large-system analysis of CDMA multiuser detectors
• Computational barriers in minimax submatrix detection
• Fundamental limits of symmetric low-rank matrix estimation
• The Spiked Matrix Model With Generative Priors
• Precise Error Analysis of Regularized <inline-formula> <tex-math notation="LaTeX">$M$ </tex-math> </inline-formula>-Estimators in High Dimensions
• Optimality and sub-optimality of PCA. I: Spiked random matrix models
• Slope meets Lasso: improved oracle bounds and optimality
• Sparse Principal Component Analysis via Axis-Aligned Random Projections
• Just interpolate: kernel ``ridgeless regression can generalize
• Deep double descent: where bigger models and more data hurt*
• Reconciling modern machine-learning practice and the classical bias–variance trade-off
• Title not available (Why is that?)
• High-dimensional dynamics of generalization error in neural networks
• Asymptotic mutual information for the balanced binary stochastic block model
• Non-Negative Principal Component Analysis: Message Passing Algorithms and Sharp Asymptotics
• Bayes-Optimal Convolutional AMP
• Bilinear Generalized Approximate Message Passing—Part I: Derivation
• Bilinear Generalized Approximate Message Passing—Part II: Applications
• Shrinkage estimation
• Benign overfitting in linear regression
• Phase Transitions and Sample Complexity in Bayes-Optimal Matrix Factorization
• The likelihood ratio test in high-dimensional logistic regression is asymptotically a rescaled Chi-square
• Finite Sample Analysis of Approximate Message Passing Algorithms
• A theory of solving TAP equations for Ising models with general invariant random matrices
• A modern maximum-likelihood theory for high-dimensional logistic regression
• Bounding distributional errors via density ratios
• Universality of approximate message passing algorithms
• The phase transition for the existence of the maximum likelihood estimate in high-dimensional logistic regression
• Information-Theoretically Optimal Compressed Sensing via Spatial Coupling and Approximate Message Passing
• The distribution of the Lasso: uniform control over sparse balls and adaptive parameter tuning
• State evolution for approximate message passing with non-separable functions

Cited In (14)

• Algorithmic obstructions in the random number partitioning problem
• Hybrid Approximate Message Passing
• Bilinear Generalized Approximate Message Passing—Part I: Derivation
• Approximate Message Passing With Consistent Parameter Estimation and Applications to Sparse Learning
• Universality of approximate message passing algorithms and tensor networks
• Local convexity of the TAP free energy and AMP convergence for \(\mathbb{Z}_2\)-synchronization
• Approximate message passing with rigorous guarantees for pooled data and quantitative group testing
• A tradeoff between false discovery and true positive proportions for sparse high-dimensional logistic regression
• Equilibria of large random Lotka-Volterra systems with vanishing species: a mathematical approach
• Analysis of Approximate Message Passing With Non-Separable Denoisers and Markov Random Field Priors
• Approximate message passing for sparse matrices with application to the equilibria of large ecological Lotka-Volterra systems
• Optimization algorithms for multi-species spherical spin glasses
• A precise high-dimensional asymptotic theory for boosting and minimum-\(\ell_1\)-norm interpolated classifiers
• A Friendly Tutorial on Mean-Field Spin Glass Techniques for Non-Physicists

Uses Software

• TheCommitteeMachine

This page was built for publication: A Unifying Tutorial on Approximate Message Passing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5863992)