Pathwise coordinate optimization

2007/08/31 by Jerome H. Friedman, Jerome Friedman, Trevor Hastie +2 · 11 citations
Computer Science · Engineering · Mathematics · #Algorithm #Artificial intelligence #Computer science #Convex optimization #Coordinate descent #Coordinate system #Elastic net regularization #Feature selection #Lasso (programming language) #Mathematical optimization #Mathematics #Medical Image Segmentation Techniques #Optimization problem #Regular polygon #Smoothing #Sparse and Compressive Sensing Techniques #Statistical Methods and Inference #Statistics #math.OC #stat.CO

paper · pdf · doi:10.1214/07-aoas131

published as Annals of Applied Statistics 2007, Vol. 1, No. 2, 302-332 · Published in at http://dx.doi.org/10.1214/07-AOAS131 the Annals of Applied Statistics (http://www.imstat.org/aoas/) by the Institute of Mathematical Statistics (http://www.imstat.org)

openalex publication_date 2007/12/01 · arxiv created 2007/12/14 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05

Abstract

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.

Citations

• Convergence of a Block Coordinate Descent Method for Nondifferentiable Minimization
• Atomic Decomposition by Basis Pursuit
• Least angle regression
• Penalized Regressions: The Bridge versus the Lasso
• Nonlinear total variation based noise removal algorithms
• A Maximum Likelihood Approach to Least Absolute Deviation Regression
• Better Subset Regression Using the Nonnegative Garrote

Cited by

• Efficient algorithm to select tuning parameters in sparse regression modeling with regularization
• Variable selection and regression analysis for graph-structured covariates with an application to genomics
• Screening Rules for Lasso with Non-Convex Sparse Regularizers
• Solution path clustering with adaptive concave penalty
• Safe Feature Elimination in Sparse Supervised Learning
• Convex and non-convex regularization methods for spatial point processes intensity estimation
• Covariate Selection in High-Dimensional Generalized Linear Models With Measurement Error
• ℓ₁ Adaptive Trend Filter via Fast Coordinate Descent
• Post-selection inference with HSIC-Lasso
• Symmetric Bilinear Regression for Signal Subgraph Estimation
• Iteratively reweighted adaptive lasso for conditional heteroscedastic time series with applications to AR–ARCH type processes

Related

• Coordinate Descent Algorithms
• Fast Distributed Coordinate Descent for Non-Strongly Convex Losses
• Improved Pathwise Coordinate Descent for Power Penalties
• A coordinate-wise optimization algorithm for the Fused Lasso
• Dykstra's Algorithm, ADMM, and Coordinate Descent: Connections, Insights, and Extensions