Pathwise coordinate optimization
Jerome H. Friedman, Trevor J. Hastie, Holger Höfling et al. · The Annals of Applied Statistics · 2007
We consider “one-at-a-time” coordinate-wise descent algorithms for a class of convex optimization problems. An algorithm of this kind has been proposed for the L1-penalized regression (lasso) in the literature, but it seems to have been largely ignored. Indeed, it seems that coordinate-wise algorithms are not often used in convex optimization. We show that this algorithm is very competitive with the well-known LARS (or homotopy) procedure in large lasso problems, and that it can be applied to related methods such as the garotte and elastic net. It turns out that coordinate-wise descent does not work in the “fused lasso,” however, so we derive a generalized algorithm that yields the solution in much less time that a standard convex optimizer. Finally, we generalize the procedure to the two-dimensional fused lasso, and demonstrate its performance on some image smoothing problems.
Cited by 1,895 works. doi:10.1214/07-aoas131 Open-access PDF
Authors
References
- Regression Shrinkage and Selection Via the Lasso
- Nonlinear Programming
- Nonlinear total variation based noise removal algorithms
- Atomic Decomposition by Basis Pursuit
- Least angle regression
- Regularization and Variable Selection Via the Elastic Net
- Adapting to Unknown Smoothness via Wavelet Shrinkage
- An iterative thresholding algorithm for linear inverse problems with a sparsity constraint
- Model Selection and Estimation in Regression with Grouped Variables
- Better Subset Regression Using the Nonnegative Garrote