# A non-asymptotic distributional theory of approximate message passing for sparse and robust regression

arXiv: https://arxiv.org/abs/2401.03923 · HTML: https://mlsanity.com/paper/2401.03923/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 103 references that are in the map.
- First posted on arXiv 8 Jan 2024.

## Builds on (most cited first, 14 of 14)

- [The Lasso with general Gaussian designs with applications to hypothesis testing](https://mlsanity.com/paper/2007.13716/) (2020)
- [Inference for Heteroskedastic PCA with Missing Data](https://mlsanity.com/paper/2107.12365/) (2021)
- [A Non-Asymptotic Framework for Approximate Message Passing in Spiked Models](https://mlsanity.com/paper/2208.03313/) (2022)
- [Approximate Message Passing for orthogonally invariant ensembles: Multivariate non-linearities and spectral initialization](https://mlsanity.com/paper/2110.02318/) (2021)
- [Estimation in Rotationally Invariant Generalized Linear Models via Approximate Message Passing](https://mlsanity.com/paper/2112.04330/) (2021)
- [High-dimensional robust regression under heavy-tailed data: Asymptotics and Universality](https://mlsanity.com/paper/2309.16476/) (2023)
- [PCA Initialization for Approximate Message Passing in Rotationally Invariant Models](https://mlsanity.com/paper/2106.02356/) (2021)
- [Uncertainty quantification for nonconvex tensor completion: Confidence intervals, heteroscedasticity and optimality](https://mlsanity.com/paper/2006.08580/) (2020)
- [De-Biasing The Lasso With Degrees-of-Freedom Adjustment](https://mlsanity.com/paper/1902.08885/) (2019)
- [Minimum ℓ1-norm interpolators: Precise asymptotics and multiple descent](https://mlsanity.com/paper/2110.09502/) (2021)
- [CAD: Debiasing the Lasso with inaccurate covariate model](https://mlsanity.com/paper/2107.14172/) (2021)
- [Spectral Estimators for Structured Generalized Linear Models via Approximate Message Passing](https://mlsanity.com/paper/2308.14507/) (2023)
- [Mean-field variational inference with the TAP free energy: Geometric and statistical properties in linear models](https://mlsanity.com/paper/2311.08442/) (2023)
- [Sharp Analysis of Power Iteration for Tensor PCA](https://mlsanity.com/paper/2401.01047/) (2024)

## Built on by (most cited first, 4 of 4)

- [Watch and Listen: Understanding Audio-Visual-Speech Moments with Multimodal LLM](https://mlsanity.com/paper/2505.18110/) (2025)
- [Stability of a Generalized Debiased Lasso with Applications to Resampling-Based Variable Selection](https://mlsanity.com/paper/2405.03063/) (2024)
- [Estimating Generalization Performance Along the Trajectory of Proximal SGD in Robust Regression](https://mlsanity.com/paper/2410.02629/) (2024)
- [Approximate Message Passing with Random Initialization for Phase Retrieval](https://mlsanity.com/paper/2608.01654/) (2026)

## Abstract (arXiv)

Characterizing the distribution of high-dimensional statistical estimators is a challenging task, due to the breakdown of classical asymptotic theory in high dimension. This paper makes progress towards this by developing non-asymptotic distributional characterizations for approximate message passing (AMP) -- a family of iterative algorithms that prove effective as both fast estimators and powerful theoretical machinery -- for both sparse and robust regression. Prior AMP theory, which focused on high-dimensional asymptotics for the most part, failed to describe the behavior of AMP when the number of iterations exceeds obig(log n/log log nbig) (with n the sample size). We establish the first finite-sample non-asymptotic distributional theory of AMP for both sparse and robust regression that accommodates a polynomial number of iterations. Our results derive approximate accuracy of Gaussian approximation of the AMP iterates, which improves upon all prior results and implies enhanced distributional characterizations for both optimally tuned Lasso and robust M-estimator.