PATHWISE COORDINATE OPTIMIZATION

By Jerome H. Friedman, Trevor J. Hastie, Holger Hofling, Robert Tibshirani. 2007

2,107 citations recorded by the source corpus.

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. 1. Introduction. In this paper we consider statistical models that lead to convex optimization problems with inequality constraints. Typically, the optimization for these problems is carried out using a standard quadratic programming algorithm. The purpose of this paper is to explore “one-at-a-time” coordinate-wise descent algorithms for these problems. The equivalent of a coordinate descent algorithm has been proposed for the L1-penalized regression (lasso) in the literature, but it is not commonly used. Moreover, coordinate-wise algorithms seem too simple, and they are not often used in convex optimization, perhaps because they only work in specialized problems. We ourselves never appreciated the value of coordinate descent methods for convex statistical problems before working on this paper. In this paper we show that coordinate descent is very competitive with the wellknown LARS (or homotopy) procedure in large lasso problems, can deliver a path of solutions efficiently, and can be applied to many other convex statistical problems such as the garotte and elastic net. We then go on to explore a nonseparable problem in which coordinate-wise descent does not work—the “fused lasso.” We derive a generalized algorithm that yields the solution in much less time that a standard convex optimizer. Finally, we generalize the procedure to

Subfields: Computational Mechanics, Computer Vision and Pattern Recognition, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computer Vision and Pattern Recognition

In Statistics and Probability

Citations in the corpus

Extended Comparisons of Best Subset Selection, Forward Stepwise Selection, and the Lasso (2017, positive): “In our simulations, we use coordinate descent with warm starts over a sequence of tuning parameter values λ1 > · · · > λm > 0, as implemented in the glmnet R package (Friedman et al., 2007, 2010).”
Best Subset Selection via a Modern Optimization Lens (2015, background): “Problem (1.2) is a convex quadratic optimization problem and there are several efficient solvers for it; see, for example, Efron et al. (2004), Friedman et al. (2007), Nesterov (2013).”
Spectral Regularization Algorithms for Learning Large Incomplete Matrices (2010, background): “See [ FHHT07 ] for more elaborate discussions on how the soft-thresholding operator arises in univariate penalized least-squares problems with the l1 penalization.”
Regularization Paths for Generalized Linear Models via Coordinate Descent (2010, methodology): “Recent rediscoveries include Friedman et al. (2007) and Wu and Lange (2008).”
SIMULTANEOUS ANALYSIS OF LASSO AND DANTZIG SELECTOR (2008, neutral): “From (A.6) – (A.8) we find 1√ n |X∆|2 ≥ 1√ n |X∆J01 |2 − c0 √ φmax(m) √ s m |∆J01 |2 ≥ (√ φmin(s + m) − c0 √ φmax(m) √ s m ) |∆J01 |2 (A.9) which proves part (ii) of the lemma.”
Petuum: A New Platform for Distributed Machine Learning on Big Data (2013, methodology): “…space of modern ML such as stochastic gradient descent and coordinate descent for determining optimality or ﬁxed-point in optimization programs [3, 12], MCMC and variational methods for graphical models [13, 15], proximal optimization and ADMM for structured sparsity problems [6, 4], among others.”
Stability selection (2008, methodology): “In contrast, stability selection with the randomized lasso does not pick wrong variables if λ is chosen too large.”
Online Learning for Matrix Factorization and Sparse Coding (2009, positive): “The second one is proven in Friedman et al. (2007) by considering subgradient optimality conditions.”
Learning Multi-Level Task Groups in Multi-Task Learning (2015, background): “It is worth mentioning that Ω(W) differs from the fused lasso regularizer (FLR) (Tibshirani et al. 2005) and its variant, generalized fused lasso regularizer (GFLR) (Friedman et al. 2007).”
On Model Parallelization and Scheduling Strategies for Distributed Machine Learning (2014, positive): “We solve Lasso using coordinate descent (CD) update rule [9]: β j ← S(xj y − ∑ j 6=k x T j xkβ (t−1) k , λ), where S(g, λ) := sign(β) (|g| − λ)+.”
Polygenic scores via penalized regression on summary statistics (2016, methodology): “Other similar methods that can also be solved using the fast coordinate descent method of Friedman et al. (2007) include the non-negative garotte, LAD-LASSO, and Grouped LASSO.”
Partial Correlation Estimation by Joint Sparse Regression Models (2008, methodology): “(2007) and Friedman et al. (2007a). Active-shooting exploits the sparse nature of sparse penalization problems in a more efficient way, and is therefore computationally much faster.”
Genome-wide association analysis by lasso penalized logistic regression (2009, background): “Friedman et al. (2008) compared coordinate descent with several competing algorithms and concluded that it performs the best.”
Regularized Multivariate Regression for Identifying Master Predictors with Application to Integrative Genomics Study of Breast Cancer (2008, methodology): “In particular, we adopt the active-shooting idea pro-10 posed by Peng et al. (2008) and Friedman et al. (2008), which is a modiﬁcation of the shooting algorithm proposed by Fu (1998) and also Friedman et al. (2007) among others.”
Bond Risk Premia with Machine Learning∗ (2018, neutral): “A similar expression can be obtained for the case β̂j 0 and β̂j = 0 (c.f. Friedman et al., 2007).”
How Correlations Influence Lasso Prediction (2012, background): “Additionally, in the ﬁrst example, corresponding to highly correlated added variables ( η = 0 .”
Non-local sparse models for image restoration (2009, background): “In the 1,2-case, this optimization problem is convex and can be solved efficiently [12].”
The graphical lasso: New insights and alternatives (2011, methodology): “The algorithms described above are variants of non-linear Gauss Seidel, or conventional variants of block coordinate methods [Friedman et al., 2007a, Tseng, 2001], where the block coordinate optimizations are performed completely. Mazumder and Agarwal [2011] propose an algorithmic framework on the p”