Statistical Sparse Online Regression: A Diffusion Approximation Perspective
Jianqing Fan, Wenyan Gong, Chris Junchi Li, Qiang Sun
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.
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.}
}