Statistical Sparse Online Regression: A Diffusion Approximation Perspective

Jianqing Fan, Wenyan Gong, Chris Junchi Li, Qiang Sun
Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics, PMLR 84:1017-1026, 2018.

Abstract

In this paper, we propose to adopt the diffusion approximation techniques to study online regression. The diffusion approximation techniques allow us to characterize the exact dynamics of the online regression process. As a consequence, we obtain the optimal statistical rate of convergence up to a logarithmic factor of the streaming sample size. Using the idea of trajectory averaging, we further improve the rate of convergence by eliminating the logarithmic factor. Lastly, we propose a two-step algorithm for sparse online regression: a burn-in step using offline learning and a refinement step using a variant of truncated stochastic gradient descent. Under appropriate assumptions, we show the proposed algorithm produces near optimal sparse estimators. Numerical experiments lend further support to our obtained theory.

Cite this Paper

BibTeX
@InProceedings{pmlr-v84-fan18a, title = {Statistical Sparse Online Regression: A Diffusion Approximation Perspective}, author = {Fan, Jianqing and Gong, Wenyan and Li, Chris Junchi and Sun, Qiang}, booktitle = {Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics}, pages = {1017--1026}, year = {2018}, editor = {Storkey, Amos and Perez-Cruz, Fernando}, volume = {84}, series = {Proceedings of Machine Learning Research}, month = {09--11 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v84/fan18a/fan18a.pdf}, url = {https://proceedings.mlr.press/v84/fan18a.html}, abstract = {In this paper, we propose to adopt the diffusion approximation techniques to study online regression. The diffusion approximation techniques allow us to characterize the exact dynamics of the online regression process. As a consequence, we obtain the optimal statistical rate of convergence up to a logarithmic factor of the streaming sample size. Using the idea of trajectory averaging, we further improve the rate of convergence by eliminating the logarithmic factor. Lastly, we propose a two-step algorithm for sparse online regression: a burn-in step using offline learning and a refinement step using a variant of truncated stochastic gradient descent. Under appropriate assumptions, we show the proposed algorithm produces near optimal sparse estimators. Numerical experiments lend further support to our obtained theory.} }
Endnote
%0 Conference Paper %T Statistical Sparse Online Regression: A Diffusion Approximation Perspective %A Jianqing Fan %A Wenyan Gong %A Chris Junchi Li %A Qiang Sun %B Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2018 %E Amos Storkey %E Fernando Perez-Cruz %F pmlr-v84-fan18a %I PMLR %P 1017--1026 %U https://proceedings.mlr.press/v84/fan18a.html %V 84 %X In this paper, we propose to adopt the diffusion approximation techniques to study online regression. The diffusion approximation techniques allow us to characterize the exact dynamics of the online regression process. As a consequence, we obtain the optimal statistical rate of convergence up to a logarithmic factor of the streaming sample size. Using the idea of trajectory averaging, we further improve the rate of convergence by eliminating the logarithmic factor. Lastly, we propose a two-step algorithm for sparse online regression: a burn-in step using offline learning and a refinement step using a variant of truncated stochastic gradient descent. Under appropriate assumptions, we show the proposed algorithm produces near optimal sparse estimators. Numerical experiments lend further support to our obtained theory.
APA
Fan, J., Gong, W., Li, C.J. & Sun, Q.. (2018). Statistical Sparse Online Regression: A Diffusion Approximation Perspective. Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 84:1017-1026 Available from https://proceedings.mlr.press/v84/fan18a.html.

Related Material