Friedman-Hastie-Tibshirani (2010) Regularization Paths for Generalized Linear Models via Coordinate Descent

Summary

The paper behind the glmnet software: fast algorithms for fitting generalized linear models with convex ($\ell_1$/$\ell_2$/elastic-net) penalties by cyclical coordinate descent, computed along an entire regularization path of penalty values. The methods cover linear regression, two-class logistic and multinomial regression, handle very large and sparse problems, and in the authors' timings run substantially faster than competing path algorithms (e.g. LARS, or specialized interior-point solvers). The core primitive is the coordinate-wise soft-thresholding update for the $\ell_1$ term, wrapped in an outer loop over a decreasing grid of $\lambda$ with warm starts.

Key Claims

• Coordinate descent is the right engine for penalized GLMs. Cyclically minimizing the penalized objective one coefficient at a time — a simple soft-threshold update for the $\ell_1$ part — converges fast and scales to large $p$.
• Whole-path computation with warm starts. Solving over a grid of $\lambda$ from large (all-zero) to small, using each solution to initialize the next, is far cheaper than solving each $\lambda$ from scratch and traces the full coefficient path.
• One framework, many models and penalties. Linear, logistic, and multinomial likelihoods and the lasso ($\ell_1$), ridge ($\ell_2$), and elastic-net (mixing parameter $\alpha$) penalties are all handled by the same coordinate-descent scheme (via iteratively reweighted least squares for the non-Gaussian likelihoods).
• Sparsity and active sets. Exploiting sparse features and maintaining an "active set" of currently nonzero coefficients (with occasional full sweeps) makes each pass cheap.
• Practical speed. Comparative timings show the coordinate-descent path solver is considerably faster than LARS and other competitors on realistic large-scale problems.

Concepts Introduced or Extended

• Coordinate Descent
• Lasso

Entities Mentioned

• Jerome Friedman
• Trevor Hastie
• Robert Tibshirani

Quotes

"We develop fast algorithms for estimation of generalized linear models with convex penalties. ... The algorithms use cyclical coordinate descent, computed along a regularization path. ... In comparative timings we find that the new algorithms are considerably faster than competing methods."

My Take

Less a new statistical idea than a computational one that decided how penalized regression is actually done in practice. LARS gave the exact piecewise-linear lasso path, but coordinate descent — with warm starts down a $\lambda$ grid and soft-thresholding as the inner update — proved simpler, faster, and trivially extensible to logistic/multinomial likelihoods and the elastic net. The resulting glmnet package became the default tool for high-dimensional regression across statistics, genomics, and machine learning, and it is the workhorse behind lasso-based shrinkage in empirical economics and finance. It pairs naturally with the lasso (the estimator and its geometry) and variable selection; the contribution here is the algorithm, coordinate descent, that makes the whole penalty family cheap to compute.