Coordinate Descent

Gradient descent moves every variable simultaneously along the full multi-dimensional slope, which requires computing the gradient with respect to all variables at once — sometimes expensive, and sometimes the problem doesn't even offer a clean joint gradient. A far simpler idea: freeze every variable except one, solve the trivial one-variable problem that remains exactly, move to the next variable, and repeat. It sounds almost too simple to work well, yet for a wide and important class of problems it's both easy to implement and fast in practice.

An analogy: tuning one knob at a time

A sound engineer adjusting a mixing board with a dozen knobs (bass, treble, individual channel volumes) doesn't try to compute the perfect joint setting of all twelve simultaneously — that's an intractable, tangled problem. Instead she adjusts one knob, listens, finds its best setting given where all the other knobs currently sit, locks it in, moves to the next knob, and cycles through all twelve repeatedly. Each individual adjustment is trivial. Do enough cycles, and the whole board converges to a very good — often optimal — overall setting.

The method, one symbol at a time

For a function $f(x_1, x_2, \dots, x_n)$, coordinate descent cycles through coordinates $j = 1, \dots, n$, and at each step updates only $x_j$ while every other coordinate stays fixed:

$$x_j \leftarrow \arg\min_{x_j} \; f(x_1, \dots, x_{j-1}, \, x_j, \, x_{j+1}, \dots, x_n) .$$

In plain English: pretend every variable except $x_j$ is a known constant, and solve the resulting one-dimensional problem exactly (or approximately, if an exact solve isn't available) — then move on to the next coordinate using this newly updated value. A full pass over all $n$ coordinates is called one cycle or epoch; the algorithm typically runs several cycles until the values stop changing appreciably. For problems where each one-variable sub-problem has a simple closed-form solution (as in ordinary least squares, ridge, or lasso regression), each individual update is nearly free to compute, which is coordinate descent's biggest appeal.

Worked example 1: minimizing a two-variable quadratic by hand

Minimize $f(x,y) = (x-3)^2 + (y-5)^2 + 0.5(x-y)^2$, starting at $(x_0,y_0)=(0,0)$. Holding $y=0$ fixed, minimize over $x$: $\frac{d}{dx}\left[(x-3)^2 + 0.5(x-0)^2\right] = 2(x-3) + x = 0 \Rightarrow 3x = 6 \Rightarrow x_1 = 2$. Now holding $x=2$ fixed, minimize over $y$: $\frac{d}{dy}\left[(y-5)^2 + 0.5(2-y)^2\right] = 2(y-5) - (2-y) = 0 \Rightarrow 3y = 12 \Rightarrow y_1 = 4$. One cycle already moved the point from $(0,0)$ to $(2,4)$, close to the joint optimum. A second cycle (holding $y=4$: minimize $x$; then holding new $x$: minimize $y$) tightens further, converging toward the true joint minimum near $(2.33, 4.33)$.

Worked example 2: lasso regression, one coordinate

For $\min_\beta \tfrac12\|y-X\beta\|^2 + \lambda\sum_j|\beta_j|$, updating a single coefficient $\beta_j$ while holding all others fixed reduces to a simple soft-thresholding formula (the same operator used in proximal gradient methods). Suppose column $j$ has a "partial residual correlation" of $\rho_j = 0.35$ after accounting for all other current coefficients, feature norm $\|X_j\|^2 = 1$, and $\lambda = 0.2$. The coordinate-descent update is $\beta_j \leftarrow \mathrm{sign}(\rho_j)\max(|\rho_j| - \lambda, 0) = \mathrm{sign}(0.35)\max(0.35-0.2, 0) = 0.15$. Cycling through every coefficient this way, recomputing each partial correlation against the others' current values, is exactly the algorithm behind glmnet, one of the most widely used lasso solvers — it's often faster in practice than proximal gradient methods on the same problem because each coordinate update is a single closed-form line, no step-size tuning required.

What this means in practice

Coordinate descent is the default engine behind fast lasso and elastic-net solvers, and shows up wherever a problem's variables have easy one-at-a-time updates but a hard joint solve — factor-model calibration with per-factor constraints, or large sparse regression with millions of coefficients. Its simplicity (no gradients of the full objective, no step-size tuning for many problem types) makes it easy to implement correctly, which matters when correctness is as important as speed.