  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$-norm statistical error of our estimator diminishes to zero in the
optimal order of $\tilde{O}({\sqrt{s/t}})$, where $s$ is the sparsity level,
$t$ is the streaming sample size, and $\tilde{O}(\cdot)$ hides logarithmic
terms. Numerical experiments demonstrate the practical efficiency of our
algorithm.
