# The Statistics of Streaming Sparse Regression

arXiv: https://arxiv.org/abs/1412.4182 · HTML: https://mlsanity.com/paper/1412.4182/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Dec 2014.

## Built on by (most cited first, 3 of 3)

- [On Private Online Convex Optimization: Optimal Algorithms in ℓp-Geometry and High Dimensional Contextual Bandits](https://mlsanity.com/paper/2206.08111/) (2022)
- [A Generalized Adaptive Joint Learning Framework for High-Dimensional Time-Varying Models](https://mlsanity.com/paper/2601.04499/) (2026)
- [Online Generalized Sparse Regression: How Does Overparametrization Help?](https://mlsanity.com/paper/2608.17466/) (2026)

## Abstract (arXiv)

We present a sparse analogue to stochastic gradient descent that is guaranteed to perform well under similar conditions to the lasso. In the linear regression setup with irrepresentable noise features, our algorithm recovers the support set of the optimal parameter vector with high probability, and achieves a statistically quasi-optimal rate of convergence of Op(k log(d)/T), where k is the sparsity of the solution, d is the number of features, and T is the number of training examples. Meanwhile, our algorithm does not require any more computational resources than stochastic gradient descent. In our experiments, we find that our method substantially out-performs existing streaming algorithms on both real and simulated data.