6
$\begingroup$

I have a huge dataset (millions of rows, thousands of columns) and glmnet Lasso regularised regression is too slow.

I am wondering what other libraries there are that try to implement regularised linear model estimation extremely efficiently? I don't necessarily need a distributed solution (it can estimate on one CPU), and it is fine for me to load all data to RAM (so an R solution may be fine, if one exists that's faster somehow than glmnet). It also does not necessarily need to be Lasso or Elastic Net.

I can use java, python or R.

My data is pretty messy, some columns are sparse, some have heavy autocorrelation, etc.

$\endgroup$

1 Answer 1

2
$\begingroup$

Some form gradient descent algorithm will be fastest on your problem. There are a number of variants of gradient descent algorithms and and a number of different algorithms. The most basic variant is Stochastic Gradient Descent (SGD). Most of the major machine learning libraries/systems will have a version of this. For massive datasets that do not fit into memory Vovpal Wabbit is probably the go, but for your data sets most of the major implementations should be fine. Enhancements to SGD include Pegasos, PassiveAggressive algorithms, Confidence Wighted Learning, Adagrad, AROW, and Natural Gradient Descent.

If you use Python then the scikit library has SGD and Passive Agrresive Preceptrons. I have used them very succesfully for datasets like you describe. Training should take only seconds or possibly minutes depending on the particulars of your data and the settings you use.

If your inputs are sparse, make sure the algorithm your algorithm is using sparse data structures to represent them. This could be what made glmnet slow.

$\endgroup$
6
  • $\begingroup$ Do you have thoughts on liblinear for this kind of problem? $\endgroup$ May 22, 2014 at 6:33
  • $\begingroup$ I think liblinear would also be a good choice. It has been a while since I used it & I have not benchmarked it against other libraries, but it served me well when I did use it. If I remeber correctly there were considerable differences in speed between the algorithm it provides so you want to play around a bit. I suspect the "-s 2" option to work in the primal space may help in your case. $\endgroup$ May 22, 2014 at 6:48
  • $\begingroup$ I think with liblinear you will probably get best results on your data with L1-loss L2-penalty and solving the primal problem as I mentioned in the previous comment. $\endgroup$ May 23, 2014 at 1:49
  • $\begingroup$ I can confirm good/fast results with primal & L2 linear SVR. Few minutes to solve. Haven't tested the quality of the model yet but it estimates quickly. $\endgroup$ May 23, 2014 at 3:27
  • $\begingroup$ Is Stochastic Gradient Descent is just optimisation algorithm that can be applied to different formulations of optimization function, can you elaborate on this? $\endgroup$
    – mrgloom
    Oct 13, 2015 at 16:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.