Coordinate Descent

Coordinate descent optimizes one variable at a time, holding the rest fixed, and cycles or samples through the coordinates until convergence.

The idea

Instead of updating every variable at once with a full gradient, coordinate descent picks one coordinate, minimizes the objective along just that direction, and moves on. Each subproblem is one-dimensional and often has a closed-form solution, so individual steps are extremely cheap. The method sweeps through coordinates cyclically, randomly, or by a greedy rule that picks the coordinate with the largest expected gain.

When it works well

Coordinate descent shines when the single-variable minimizations are easy and when the objective is separable enough that changing one coordinate does not require recomputing everything. For least squares and generalized linear models with L1 or L2 penalties, each coordinate update is a scalar soft-thresholding or ratio, and the method is one of the fastest known. The widely used glmnet package for penalized regression is built on cyclic coordinate descent.

import numpy as np

def lasso_cd(A, b, lam, iters=100):
    n = A.shape[1]
    x = np.zeros(n)
    col_sq = (A**2).sum(axis=0)
    for _ in range(iters):
        for j in range(n):
            r = b - A @ x + A[:, j]*x[j]   # residual excluding j
            rho = A[:, j] @ r
            x[j] = np.sign(rho)*max(abs(rho)-lam, 0)/col_sq[j]
    return x

Convergence

For smooth convex objectives coordinate descent converges, and for the composite smooth-plus-separable-nonsmooth case it converges provided the nonsmooth part is separable across coordinates, exactly the structure L1 penalties provide. Randomized coordinate selection has clean expected-rate guarantees and avoids the worst-case behavior of a fixed cyclic order. If the nonsmooth part couples coordinates, plain coordinate descent can stall at a non-minimizer, which is why separability is the key precondition.

Trade-offs

Coordinate descent avoids storing or inverting large matrices and exploits sparsity in the data naturally, since only the active coordinate's column is touched. Its weakness is strongly coupled variables, where each one-dimensional step makes little progress; there block coordinate descent, which updates several correlated variables together, restores efficiency.