title: How to speed up up Stochastic Gradient Descent?
body: <p>I'm trying to fit a regression model with an L1 penalty, but I'm having trouble finding an implementation in python that fits in a reasonable amount of time. The data I've got is on the order of 100k by 500 (sidenote; several of the variables are pretty correlated), but running the sklearn Lasso implementation on this takes upwards of 12 hours to fit a single model (I'm not actually sure of the exact time, I've left it running overnight several times and it never finished).</p>
  
  <p>I've been looking into <a href="http://scikit-learn.org/stable/modules/sgd.html" rel="nofollow">Stochastic Gradient Descent</a> as a way to get the job done faster. However, the <a href="http://scikit-learn.org/stable/modules/generated/sklearn.linear_model.SGDRegressor.html#sklearn.linear_model.SGDRegressor" rel="nofollow">SGDRegressor</a> implementation in sklearn takes on the order of 8 hours to fit when I'm using 1e5 iterations. This seems like a relatively small amount (and the docs even suggest that the model often takes around 1e6 iters to converge).</p>
  
  <p>I'm wondering if there's something that I'm being stupid about which is causing the fits to take a really long time. I've been told that SGD is often used for its efficiency (something around O(n_iter * n_samp * n_feat), though so far I haven't seen much improvement over Lasso.</p>
  
  <p>To speed things up, I have tried:</p>
  
  <ol>
  <li>Decreasing n_iter, but this often leads to a pretty bad solution because it hasn't converged yet.</li>
  <li>Increasing the step size (and decreasing n_iter), but this often makes the loss function explode</li>
  <li>Changing the learning rate types (from inverse scaling to an amount based off of the number of iterations), and this also didn't seem to make a huge difference.</li>
  </ol>
  
  <p>Any suggestions for speeding this process up? It seems like partial_fit might be part of the answer, though the docs on this are somewhat sparse. I'd love to be able to fit these models without waiting for three days apiece.</p>