An Asymptotic Rate for the LASSO Loss

Cynthia Rush
Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, PMLR 108:3664-3673, 2020.

Abstract

The LASSO is a well-studied method for use in high-dimensional linear regression where one wishes to recover a sparse vector b from noisy observations y measured through a n-by-p matrix X with the model y = Xb + w where w is a vector of independent, mean-zero 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].

Cite this Paper

BibTeX
@InProceedings{pmlr-v108-rush20a, title = {An Asymptotic Rate for the LASSO Loss}, author = {Rush, Cynthia}, booktitle = {Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics}, pages = {3664--3673}, year = {2020}, editor = {Chiappa, Silvia and Calandra, Roberto}, volume = {108}, series = {Proceedings of Machine Learning Research}, month = {26--28 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v108/rush20a/rush20a.pdf}, url = {https://proceedings.mlr.press/v108/rush20a.html}, abstract = {The LASSO is a well-studied method for use in high-dimensional linear regression where one wishes to recover a sparse vector b from noisy observations y measured through a n-by-p matrix X with the model y = Xb + w where w is a vector of independent, mean-zero 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].} }
Endnote
%0 Conference Paper %T An Asymptotic Rate for the LASSO Loss %A Cynthia Rush %B Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2020 %E Silvia Chiappa %E Roberto Calandra %F pmlr-v108-rush20a %I PMLR %P 3664--3673 %U https://proceedings.mlr.press/v108/rush20a.html %V 108 %X The LASSO is a well-studied method for use in high-dimensional linear regression where one wishes to recover a sparse vector b from noisy observations y measured through a n-by-p matrix X with the model y = Xb + w where w is a vector of independent, mean-zero 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].
APA
Rush, C.. (2020). An Asymptotic Rate for the LASSO Loss. Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 108:3664-3673 Available from https://proceedings.mlr.press/v108/rush20a.html.

Related Material