Online Linearized LASSO

Shuoguang Yang, Yuhao Yan, Xiuneng Zhu, Qiang Sun
Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, PMLR 206:7594-7610, 2023.

Abstract

Sparse regression has been a popular approach to perform variable selection and enhance the prediction accuracy and interpretability of the resulting statistical model. Existing approaches focus on offline regularized regression, while the online scenario has rarely been studied. In this paper, we propose a novel online sparse linear regression framework for analyzing streaming data when data points arrive sequentially. Our proposed method is memory efficient and requires less stringent restricted strong convexity assumptions. Theoretically, we show that with a properly chosen regularization parameter, the $\ell_2$-error of our estimator decays to zero at the optimal order of $\tilde \mathcal{O}(\frac{s}{\sqrt{t}})$, where $s$ is the sparsity level, $t$ is the streaming sample size, and $\tilde \mathcal{O}(\cdot)$ hides logarithmic terms. Numerical experiments demonstrate the practical efficiency of our algorithm.

Cite this Paper


BibTeX
@InProceedings{pmlr-v206-yang23g, title = {Online Linearized LASSO}, author = {Yang, Shuoguang and Yan, Yuhao and Zhu, Xiuneng and Sun, Qiang}, booktitle = {Proceedings of The 26th International Conference on Artificial Intelligence and Statistics}, pages = {7594--7610}, year = {2023}, editor = {Ruiz, Francisco and Dy, Jennifer and van de Meent, Jan-Willem}, volume = {206}, series = {Proceedings of Machine Learning Research}, month = {25--27 Apr}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v206/yang23g/yang23g.pdf}, url = {https://proceedings.mlr.press/v206/yang23g.html}, abstract = {Sparse regression has been a popular approach to perform variable selection and enhance the prediction accuracy and interpretability of the resulting statistical model. Existing approaches focus on offline regularized regression, while the online scenario has rarely been studied. In this paper, we propose a novel online sparse linear regression framework for analyzing streaming data when data points arrive sequentially. Our proposed method is memory efficient and requires less stringent restricted strong convexity assumptions. Theoretically, we show that with a properly chosen regularization parameter, the $\ell_2$-error of our estimator decays to zero at the optimal order of $\tilde \mathcal{O}(\frac{s}{\sqrt{t}})$, where $s$ is the sparsity level, $t$ is the streaming sample size, and $\tilde \mathcal{O}(\cdot)$ hides logarithmic terms. Numerical experiments demonstrate the practical efficiency of our algorithm.} }
Endnote
%0 Conference Paper %T Online Linearized LASSO %A Shuoguang Yang %A Yuhao Yan %A Xiuneng Zhu %A Qiang Sun %B Proceedings of The 26th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2023 %E Francisco Ruiz %E Jennifer Dy %E Jan-Willem van de Meent %F pmlr-v206-yang23g %I PMLR %P 7594--7610 %U https://proceedings.mlr.press/v206/yang23g.html %V 206 %X Sparse regression has been a popular approach to perform variable selection and enhance the prediction accuracy and interpretability of the resulting statistical model. Existing approaches focus on offline regularized regression, while the online scenario has rarely been studied. In this paper, we propose a novel online sparse linear regression framework for analyzing streaming data when data points arrive sequentially. Our proposed method is memory efficient and requires less stringent restricted strong convexity assumptions. Theoretically, we show that with a properly chosen regularization parameter, the $\ell_2$-error of our estimator decays to zero at the optimal order of $\tilde \mathcal{O}(\frac{s}{\sqrt{t}})$, where $s$ is the sparsity level, $t$ is the streaming sample size, and $\tilde \mathcal{O}(\cdot)$ hides logarithmic terms. Numerical experiments demonstrate the practical efficiency of our algorithm.
APA
Yang, S., Yan, Y., Zhu, X. & Sun, Q.. (2023). Online Linearized LASSO. Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 206:7594-7610 Available from https://proceedings.mlr.press/v206/yang23g.html.

Related Material