The Statistics of Streaming Sparse Regression

By Jacob Steinhardt, Stefan Wager, Percy Liang. 2014

11 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Mechanics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

Citations in the corpus

Memory, Communication, and Statistical Queries (2016, background): “…side on reducing the memory needs (e.g., Langford et al., 2009; Xiao, 2010; Agarwal et al., 2012; Mitliagkas et al., 2013; Arora et al., 2013; Steinhardt et al., 2014) and/or communication needs (e.g., Niu et al., 2011) for various specific learning tasks, though this literature is beyond…”
Minimax rates for memory-bounded sparse linear regression (2015, background): “Further weakenings of this assumption in online settings appear possible but challenging (Agarwal et al., 2012; Steinhardt et al., 2014).”