A nonasymptotic distributional theory of approximate message passing for sparse and robust regression

Abstract

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 o(logn/loglogn) (with n the sample size). Our AMP theory is further leveraged to derive a refined rate for the Lasso estimator, built upon a nonasymptotic convergence of AMP to Lasso. To the best of our knowledge, this is the first result of its kind, breaking the rate barrier resulting from the widely adopted Gaussian min-max theorem. Our results establish approximate accuracy of Gaussian approximation of the AMP iterates, which improves upon prior results and implies enhanced distributional characterizations for both optimally tuned Lasso and robust M-estimator.