Coordinate Descent

Imagine you're standing in a mountain range and need to find the lowest valley. A full gradient step tells you the steepest downhill direction in all dimensions at once — useful, but expensive when the landscape has millions of dimensions. Coordinate descent takes a simpler route: at every step it picks one coordinate axis, finds the minimum along that line, moves there, then moves to the next axis and repeats.

The path zigzags, sometimes frustratingly so. But each individual step is cheap — often just a closed-form formula — and after enough cycles the zigzag converges on the valley floor.

This approach is not a hack. For many functions the mathematics guarantees convergence to the global minimum, and for some important problems — like the Lasso regression in statistics — cycling through coordinates one by one gives the exact solution faster than any joint method. The simplicity that looks like a limitation is the source of its power.

Below is a 2D quadratic bowl — a function f(x, y) = a·$x^{2}$ + b·$y^{2}$ with a minimum at the origin. Drag the starting point or press Step to advance one coordinate at a time. Each horizontal segment minimizes over x (with y frozen), each vertical segment minimizes over y (with x frozen). Press Run to animate the full descent.

<div class="controls">
  <label>{{lbl_shape}}
    <select id="shape">
      <option value="1,1">{{opt_circular}}</option>
      <option value="0.5,4" selected>{{opt_elongated}}</option>
      <option value="0.2,5">{{opt_very_elongated}}</option>
    </select>
  </label>
  <label>{{lbl_speed}}
    <select id="speed">
      <option value="600">{{opt_slow}}</option>
      <option value="300" selected>{{opt_normal}}</option>
      <option value="120">{{opt_fast}}</option>
    </select>
  </label>
</div>
<canvas id="canvas" width="380" height="320"></canvas>
<div class="info" id="info">{{info_initial}}</div>
<div class="btns">
  <button id="stepBtn" type="button">{{btn_step}}</button>
  <button id="runBtn" type="button">{{btn_run}}</button>
  <button id="resetBtn" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.controls { display: flex; gap: 1rem; flex-wrap: wrap; margin-bottom: .6rem; font-size: .88rem; }
label { display: flex; align-items: center; gap: .4rem; }
select { font-size: .88rem; border: 1px solid #b0b8c1; border-radius: 6px; padding: .25rem .5rem; }
canvas { display: block; border: 1px solid #d0d6dd; border-radius: 10px;
         background: #f8fafc; cursor: crosshair; max-width: 100%; touch-action: none; }
.info { font-size: .9rem; color: #444; min-height: 1.5em; margin: .5rem 0; }
.info.done { color: #0a7d33; font-weight: 600; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Notice the characteristic zigzag: after fixing y and minimizing x, the point lands exactly on the x-axis minimum for that row — then fixing x and minimizing y drives it down. When the bowl is circular (a = b) the algorithm converges in just two steps; when it is elongated (a ≪ b) the zigzag becomes tighter and more steps are needed. This is the hallmark of coordinate descent — progress is guaranteed each step, but the path may be indirect.

Coordinate descent looks trivial. The convergence theory is anything but.

• Convex + separable: if the objective f($x_{1}$, …, $x_{n}$) is convex and the constraints decompose by coordinate, each 1-D minimization is exact and the sequence converges to the global minimum. This is the textbook guarantee (Tseng, 2001).
• Convex + non-separable (Lasso): the Lasso penalty ‖x‖₁ is not smooth, but coordinate-wise the subproblem has a closed-form solution called soft thresholding. Cycling through coordinates (the Lassoed-LARS / coordinate-wise strategy, Friedman et al. 2007) solves the full Lasso to machine precision.
• Lipschitz-smooth: if each partial gradient is Lipschitz-continuous with constant $L_{i}$, randomized coordinate descent (Richtárik & Takáč, 2014) converges with rate $O(1/k)$ in expectation — the same rate as full gradient descent, but each step costs n times less.
• Non-convex problems: convergence to a local minimum is not guaranteed. The algorithm can stall at a saddle point where every coordinate direction is a local minimum yet the point is not a global one — a subtle failure mode absent from gradient descent.
• Status: coordinate descent is a solved method for convex problems. Its convergence rates are tight, it parallelizes naturally (each coordinate can run on its own core), and for structured sparsity problems it is often provably optimal among first-order methods.

The gap between convex and non-convex is the crux. Understanding it connects coordinate descent to the deeper question of what non-convex optimization can promise.

The "one variable at a time" strategy is everywhere in applied optimization:

• Lasso and elastic net regression: the canonical use case. The coordinate-wise soft-threshold update (Friedman et al., 2007) fits sparse linear models on millions of features in seconds. It is the default solver in scikit-learn's Lasso class.
• Support vector machines: the SMO (Sequential Minimal Optimization) algorithm for SVMs minimizes over two variables at a time — a block-coordinate variant — to avoid ever solving a large linear system.
• Deep learning: Adam and other adaptive optimizers perform per-parameter (coordinate-wise) updates using running estimates of gradient moments. The "one parameter at a time" intuition is preserved even inside complex adaptive rules.
• Probabilistic graphical models: Gibbs sampling updates one random variable at a time conditioned on all others — a stochastic coordinate-descent on the log-probability.
• Large-scale recommendation: matrix factorization for collaborative filtering alternates between fixing user embeddings and fixing item embeddings — a block-coordinate strategy that splits a giant joint problem into two small ones.

Whenever the joint problem is hard but the 1-D subproblem is easy, coordinate descent is the natural tool. Learn it and you've understood the skeleton of linear programming simplex pivots, SVM training, and sparse statistical inference at once.

Coordinate descent turns a hard multi-dimensional minimization into a sequence of trivial 1-D ones. The price is a zigzag path; the reward is that each step is cheap, often closed-form, and perfectly parallelizable across cores.

For convex problems the theory closes the loop cleanly: the zigzag converges, the rate matches full gradient descent per unit of work, and for structured problems like Lasso it is provably optimal. For non-convex landscapes the guarantees weaken — saddle points can trap the algorithm — connecting coordinate descent to the open frontier of non-convex optimization.

The lesson is broader than any single algorithm: sometimes the right way to attack a problem in many dimensions is to pretend, one step at a time, that only one dimension exists.