An Asymptotic Rate for the LASSO Loss
[edit]
Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, PMLR 108:36643673, 2020.
Abstract
The LASSO is a wellstudied method for use in highdimensional linear regression where one wishes to recover a sparse vector b from noisy observations y measured through a nbyp matrix X with the model y = Xb + w where w is a vector of independent, meanzero noise. We study the linear asymptotic regime where the under sampling ratio, n/p, approaches a constant greater than 0 in the limit.Using a carefully constructed approximate message passing (AMP) algorithm that converges to the LASSO estimator and recent finite sample theoretical performance guarantees for AMP, we provide large deviations bounds between various measures of LASSO loss and their concentrating values predicted by the AMP state evolution that shows exponentially fast convergence (in n) when the measurement matrix X is i.i.d. Gaussian. This work refines previous asymptotic analysis of LASSO loss in [Bayati and Montanari, 2012].
Related Material


