A Unifying Tutorial on Approximate Message Passing

DOI10.1561/2200000092MaRDI QIDQ5863992zbMATH OpenOpenAlexFDO

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

Publication date 3 June 2022

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

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

zbMATH Keywords

design and analysis of algorithmsinformation theoryrandomized algorithmsregressionstatistical machine learningstatistical signal processing: estimation

Mathematics Subject Classification ID

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

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.

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

Cites work

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

Cited in

(36)

• Universality of approximate message passing algorithms
• A precise high-dimensional asymptotic theory for boosting and minimum-\(\ell_1\)-norm interpolated classifiers
• The overlap gap property and approximate message passing algorithms for \(p\)-spin models
• Approximate Message Passing With Consistent Parameter Estimation and Applications to Sparse Learning
• Bilinear Generalized Approximate Message Passing—Part I: Derivation
• Hybrid Approximate Message Passing
• State evolution for approximate message passing with non-separable functions
• Approximate message passing with spectral initialization for generalized linear models*
• Mean field asymptotics in high-dimensional statistics: from exact results to efficient algorithms
• State evolution for general approximate message passing algorithms, with applications to spatial coupling
• Analysis of Approximate Message Passing With Non-Separable Denoisers and Markov Random Field Priors
• High-temperature expansions and message passing algorithms
• Generalized approximate survey propagation for high-dimensional estimation ^*
• 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 Friendly Tutorial on Mean-Field Spin Glass Techniques for Non-Physicists
• Algorithmic obstructions in the random number partitioning problem
• Universality of approximate message passing with semirandom matrices
• Local convexity of the TAP free energy and AMP convergence for \(\mathbb{Z}_2\)-synchronization
• A tradeoff between false discovery and true positive proportions for sparse high-dimensional logistic regression
• Universality of approximate message passing algorithms and tensor networks
• Approximate message passing with rigorous guarantees for pooled data and quantitative group testing
• Equilibria of large random Lotka-Volterra systems with vanishing species: a mathematical approach
• Optimality of approximate message passing for spiked matrix models with rotationally invariant noise
• Linear operator approximate message passing (OpAMP)
• Approximate message passing for general non-symmetric random matrices
• Fundamental limits of community detection from multi-view data: multi-layer, dynamic and partially labeled block models
• Elliptic approximate message passing and an application to theoretical ecology
• Spectral estimators for structured generalized linear models via approximate message passing
• A leave-one-out approach to approximate message passing
• A new central limit theorem for the augmented IPW estimator: variance inflation, cross-fit covariance and beyond
• Deflated HeteroPCA: overcoming the curse of ill-conditioning in heteroskedastic PCA
• Spectrum-aware debiasing: a modern inference framework with applications to principal components regression
• Optimal thresholds and algorithms for a model of multi-modal learning in high dimensions
• Universality of estimators for high-dimensional linear models with block dependency
• Diaconis-Ylvisaker prior penalized likelihood for p/n(0, 1) logistic regression

Describes a project that uses

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)