Coordinate descent algorithms for lasso penalized regression

By Tong Tong Wu, Kenneth L. Lange. 2008

844 citations recorded by the source corpus.

Imposition of a lasso penalty shrinks parameter estimates toward zero and performs continuous model selection. Lasso penalized regression is capable of handling linear regression problems where the number of predictors far exceeds the number of cases. This paper tests two exceptionally fast algorithms for estimating regression coefficients with a lasso penalty. The previously known l 2 algorithm is based on cyclic coordinate descent. Our new l 1 algorithm is based on greedy coordinate descent and Edgeworth's algorithm for ordinary l 1 regression. Each algorithm relies on a tuning constant that can be chosen by cross-validation. In some regression problems it is natural to group parameters and penalize parameters group by group rather than separately. If the group penalty is proportional to the Euclidean norm of the parameters of the group, then it is possible to majorize the norm and reduce parameter estimation to l 2 regression with a lasso penalty. Thus. the existing algorithm can be extended to novel settings. Each of the algorithms discussed is tested via either simulated or real data or both. The Appendix proves that a greedy form of the l 2 algorithm converges to the minimum value of the objective function.

Subfields: Artificial Intelligence, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/afc473ea8e7e923246b27bd2790d71d93dffbadb

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 Statistics and Probability

Citations in the corpus

Sparse inverse covariance matrix estimation using quadratic approximation (2011, methodology): “In [7, 18] the authors show that coordinate descent methods are very efficient for solving lasso type problems.”
Coordinate Descent Converges Faster with the Gauss-Southwell Rule Than Random Selection (2015, methodology): “In Section 6, we discuss selection rules that incorporate the L i to achieve faster rates whenever the L i are distinct, but ﬁrst we consider the eﬀect of exact coordinate optimization on the choice of the L i k .”
A variational Bayes algorithm for fast and accurate multiple locus genome-wide association analysis (2010, methodology): “Algorithmic details for fitting the LASSO model for the linear-Gaussian case are provided by [35,36].”
Dykstra's Algorithm, ADMM, and Coordinate Descent: Connections, Insights, and Extensions (2017, background): “The use of coordinate descent for the lasso was popularized by Friedman et al. (2007, 2010), but was studied earlier or concurrently by several others, e.g., Fu (1998); Sardy et al. (2000); Wu and Lange (2008).”
Online Learning for Matrix Factorization and Sparse Coding (2009, neutral): “on coordinate descent with soft thresholding (Fu, 1998; Friedman et al., 2007; Wu and Lange, 2008).”
On the complexity analysis of randomized block-coordinate descent methods (2013, methodology): “Block-coordinate descent (BCD) methods and their variants have been successfully applied to solve various large-scale optimization problems (see, for example, [22, 4, 18, 19, 20, 21, 9, 23]).”
Stochastic methods for l1 regularized loss minimization (2009, methodology): “In a series of experiments, they observed that cyclical coordinate descent outperforms many alternative popular methods such as LARS (Efron et al., 2004), an interior point method called l1lognet (Koh et al., 2007), and the Lasso Penalized Logistic (LPL) program (Wu & Lange, 2008).”
Bond Risk Premia with Machine Learning∗ (2018, positive): “The parameter λ for ridge and lasso, and the pair λ,µ for elastic-net are estimated adaptively on the validation sample by using a cyclical coordinate descent method as proposed by Wu et al. (2008) and extended by Friedman et al. (2010).”
Blockwise coordinate descent procedures for the multi-task lasso, with applications to neural semantic basis discovery (2009, methodology): “… Basis Discovery Han Liu hanliu@cs.cmu.edu Machine Learning Department, School of Computer Science, Carnegie Mellon University, PA 15213 USA Mark Palatucci mpalatuc@cs.cmu.edu School of Computer Science, Carnegie Mellon University, 5000 Forbes Ave., Pittsburgh, PA 15213 USA Jian Zhang…”
Regularization Paths for Cox’s Proportional Hazards Model via Coordinate Descent (2011, methodology): “This method has been applied to penalized regression and in particular, elastic net penalties; recently by Friedman et al. (2010), van der Kooij (2007) and Wu and Lange (2008).”
Group descent algorithms for nonconvex penalized linear and logistic regression models with grouped predictors (2012, methodology): “The idea behind the algorithm is the same as that of coordinate descent algorithms (Friedman et al. 2007; Wu and Lange 2008), with the modification that the optimization of (2.5) takes place repeatedly with respect to a group βj rather than an individual coordinate βj .”