The Statistics of Streaming Sparse Regression
arXiv:1412.4182
Abstract
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.
References in corpus (17)
- Discussion of "Least angle regression" by Efron et al
- Rejoinder to "Least angle regression" by Efron et al
- Discussion of "Least angle regression" by Efron et al
- Discussion of "Least angle regression" by Efron et al
- Least Angle Regression
- Discussion of "Least angle regression" by Efron et al
- Discussion of "Least angle regression" by Efron et al
- Discussion of "Least angle regression" by Efron et al
- Discussion of "Least angle regression" by Efron et al
- Discussion of "Least angle regression" by Efron et al
- Simultaneous analysis of Lasso and Dantzig selector
- The Sixth Data Release of the Sloan Digital Sky Survey
- On the conditions used to prove oracle results for the Lasso
- Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging Schemes
- Safe Feature Elimination in Sparse Supervised Learning
- Fast Randomized Kernel Methods With Statistical Guarantees
- Stream Processing for Solar Physics: Applications and Implications for Big Solar Data