Coordinate Descent

Definition

Coordinate descent is an iterative optimization method that minimizes a multivariate objective by cyclically minimizing over one coordinate at a time, holding the others fixed, and repeating until convergence. For separable-plus-smooth objectives — a differentiable loss plus a separable penalty such as the $\ell_1$ norm — the one-dimensional subproblems have closed-form solutions, making the method simple and extremely fast. It is the computational engine behind glmnet for fitting the lasso, ridge, and elastic-net regularization paths.

Key Ideas

• One coordinate at a time. Each update fixes all but one coefficient and solves the resulting scalar problem exactly; a full "cycle" sweeps through all coordinates, and cycles repeat to convergence.
• Soft-thresholding for the $\ell_1$ penalty. For a lasso/elastic-net objective the coordinate-wise update is a soft-threshold of the partial residual's inner product with the predictor: $\beta_j \leftarrow \dfrac{S(\sum_i x_{ij} r_i^{(j)},\ \lambda\alpha)}{\sum_i x_{ij}^2 + \lambda(1-\alpha)}$, where $S(z,\gamma)=\mathrm{sign}(z)(|z|-\gamma)_+$ and $r^{(j)}$ is the partial residual excluding predictor $j$. The elastic-net mixing $\alpha$ splits the penalty between $\ell_1$ (numerator threshold) and $\ell_2$ (denominator shrinkage).
• Convergence needs separability. Coordinate descent converges for a smooth convex loss plus a separable convex penalty (e.g. $\ell_1$); with non-separable penalties (e.g. the fused lasso) naïve coordinate descent can get stuck at non-stationary points.
• Regularization path with warm starts. Solving over a decreasing grid of penalty values $\lambda$, initializing each fit from the previous solution ("warm start"), traces the whole coefficient path far more cheaply than solving each $\lambda$ independently.
• Active-set / sparsity tricks. Maintaining the set of currently nonzero coefficients and mostly cycling over it (with occasional full sweeps to check the KKT conditions), plus exploiting sparse feature matrices, makes each pass cheap in large-$p$ problems.

How It Works

1. Start at large $\lambda$ where all coefficients are zero.
2. Decrease $\lambda$ along a grid; for each $\lambda$, cycle coordinate-wise soft-threshold updates over the active set until the coefficients stop changing.
3. For non-Gaussian GLMs (logistic, multinomial), wrap the coordinate descent inside an iteratively reweighted least squares (IRLS) outer loop: form a quadratic (weighted-least-squares) approximation to the log-likelihood at the current estimate, then run coordinate descent on that weighted lasso problem.
4. Use the previous $\lambda$'s solution as the warm start for the next; check KKT/optimality on the full variable set before moving on.

Why It Matters

• The default solver for penalized regression. Coordinate descent (via glmnet) is how the lasso and elastic net are actually computed at scale, across statistics, genomics, econometrics, and machine learning.
• Simplicity and speed. The inner update is a one-line soft-threshold; there is no matrix inversion, so it handles very large, sparse designs and is often faster than exact path methods like LARS.
• Extensible. The same scheme covers different likelihoods (Gaussian/logistic/multinomial/Cox) and penalties (lasso/ridge/elastic net) by changing only the loss's quadratic approximation and the coordinate update.

Open Questions

• Non-separable penalties. Coordinate descent is not guaranteed to reach the optimum for penalties that couple coordinates (fused lasso, generalized lasso); modified or proximal algorithms are needed.
• Update order and correlated predictors. Cyclic vs. random vs. greedy coordinate selection affects convergence speed, especially with strongly correlated features.
• Non-convex penalties. SCAD/MCP objectives require care (local linear approximation) for coordinate descent to behave well.

Related

• Lasso
• Variable Selection
• Friedman-Hastie-Tibshirani (2010) Regularization Paths for Generalized Linear Models via Coordinate Descent
• Jerome Friedman
• Trevor Hastie
• Robert Tibshirani
• Machine Learning in Asset Pricing