A Unifying Tutorial on Approximate Message Passing

DOI10.1561/2200000092zbMath1491.68152arXiv2105.02180OpenAlexW4292482091MaRDI QIDQ5863992

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

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

information theoryregressionrandomized algorithmsdesign and analysis of algorithmsstatistical machine learningstatistical signal processing: estimation

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Research exposition (monographs, survey articles) pertaining to statistics (62-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 computer science (68-02) Statistical aspects of information-theoretic topics (62B10)

Related Items (7)

A precise high-dimensional asymptotic theory for boosting and minimum-\(\ell_1\)-norm interpolated classifiers ⋮ 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 ⋮ 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

Uses Software

• TheCommitteeMachine

Cites Work

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

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