14
$\begingroup$

What are the pros and cons of using LARS [1] versus using coordinate descent for fitting L1-regularized linear regression?

I am mainly interested in performance aspects (my problems tend to have N in the hundreds of thousands and p < 20.) However, any other insights would also be appreciated.

edit: Since I've posted the question, chl has kindly pointed out a paper [2] by Friedman et al where coordinate descent is shown to be considerably faster than other methods. If that's the case, should I as a practitioner simply forget about LARS in favour of coordinate descent?

[1] Efron, Bradley; Hastie, Trevor; Johnstone, Iain and Tibshirani, Robert (2004). "Least Angle Regression". Annals of Statistics 32 (2): pp. 407–499.
[2] Jerome H. Friedman, Trevor Hastie, Rob Tibshirani, "Regularization Paths for Generalized Linear Models via Coordinate Descent", Journal of Statistical Software, Vol. 33, Issue 1, Feb 2010.
$\endgroup$
13
$\begingroup$

In scikit-learn the implementation of Lasso with coordinate descent tends to be faster than our implementation of LARS although for small p (such as in your case) they are roughly equivalent (LARS might even be a bit faster with the latest optimizations available in the master repo). Furthermore coordinate descent allows for efficient implementation of elastic net regularized problems. This is not the case for LARS (that solves only Lasso, aka L1 penalized problems).

Elastic Net penalization tends to yield a better generalization than Lasso (closer to the solution of ridge regression) while keeping the nice sparsity inducing features of Lasso (supervised feature selection).

For large N (and large p, sparse or not) you might also give a stochastic gradient descent (with L1 or elastic net penalty) a try (also implemented in scikit-learn).

Edit: here are some benchmarks comparing LassoLARS and the coordinate descent implementation in scikit-learn

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ (+1) @ogrisel Thanks a lot! Since I'll probably end up having to code this up myself (need it in Java, and haven't seen any open-source Java implementations yet), which algorithm would you say is easier to implement? $\endgroup$ – NPE Nov 26 '10 at 13:24
  • 1
    $\begingroup$ both coordinate descent and SGD are easy to implement (check Leon Bottou's webpage for a nice intro to SGD). LARS is probably trickier to get right. $\endgroup$ – ogrisel Nov 26 '10 at 13:25
  • $\begingroup$ Superb, thanks! I'll check out Léon Bottou's site. $\endgroup$ – NPE Nov 26 '10 at 13:28
  • $\begingroup$ @ogrisel (+1) Nice to see you there. $\endgroup$ – chl Nov 26 '10 at 13:31
  • 2
    $\begingroup$ @aix I have edited my answer to add some benchmarks on the current implementations in scikit-learn. Also checkout the java version of liblinear before implementing your own coordinate descent as it might be good enough for you (though you cannot have both L1 and L2 reg at the same time). $\endgroup$ – ogrisel Nov 26 '10 at 17:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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