Optimization

Coordinate Descent

Optimize one variable at a time while holding the rest fixed, effective when single-coordinate updates are cheap and closed-form.

One coordinate at a time

Coordinate descent minimizes a function by cycling through the variables, updating one while keeping the others fixed. Each subproblem is one-dimensional and often has a closed-form solution, so a full sweep can be very fast. The method needs no gradient of the full objective, only the ability to optimize along each axis.

Update orders

Kronos motion — when

Cyclic: sweep through coordinates in fixed order.
Randomized: pick the next coordinate at random, which has clean convergence theory.
Greedy (Gauss-Southwell): update the coordinate with the largest gradient component, fewer iterations but more overhead per step.

When it works well

Coordinate descent converges to the global optimum for smooth convex functions and for separable-plus-smooth objectives such as the lasso, where the nonsmooth L1 term is separable across coordinates. It can fail to reach the optimum for general nonsmooth objectives whose nonsmooth part is not separable, because it may get stuck at a non-stationary point.

Why it is fast in practice

For sparse problems each coordinate update touches only a few data entries, and the closed-form soft-thresholding update for lasso is extremely cheap. Coordinate descent is the default solver in widely used packages for sparse linear models, often outperforming full-gradient methods on such problems.

Block coordinate descent

Updating groups of variables together (block coordinate descent) generalizes the idea and is used when variables have natural blocks, as in matrix factorization where one alternately fixes one factor and solves for the other. Alternating least squares is a block coordinate descent method.

python

for _ in range(sweeps):
    for j in range(n):
        x[j] = argmin_over_xj(x, j)   # 1-D minimization, often closed form

Coordinate descent efficiently fits the sparse regression and matrix-factorization models used in large-scale data analysis.