When Coordinate Descent Converges — and When It Doesn't

Introduction

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.

Watch the Zigzag

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>Bowl shape:
    <select id="shape">
      <option value="1,1">Circular (a=1, b=1)</option>
      <option value="0.5,4" selected>Elongated (a=0.5, b=4)</option>
      <option value="0.2,5">Very elongated (a=0.2, b=5)</option>
    </select>
  </label>
  <label>Speed:
    <select id="speed">
      <option value="600">Slow</option>
      <option value="300" selected>Normal</option>
      <option value="120">Fast</option>
    </select>
  </label>
</div>
<canvas id="canvas" width="380" height="320"></canvas>
<div class="info" id="info">Click the canvas to set start point, then step.</div>
<div class="btns">
  <button id="stepBtn" type="button">Step</button>
  <button id="runBtn" type="button">Run</button>
  <button id="resetBtn" type="button" class="ghost">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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Coordinate descent on f(x,y) = a*x^2 + b*y^2.
// Minimum is at (0,0). Each step fixes one coordinate and minimizes the 1-D slice:
//   fix y -> optimal x = 0  (df/dx = 2a*x = 0)
//   fix x -> optimal y = 0  (df/dy = 2b*y = 0)
// For a general quadratic A*x^2 + B*y^2 the exact coordinate update is:
//   x_new = -gradient_x / (2a) = 0,  y_new = -gradient_y / (2b) = 0
// which for this bowl means both coordinates go directly to 0 in one step each.
// To make the zigzag visible we perturb with a coupling term:
//   f(x,y) = a*x^2 + b*y^2 + c*x*y
// Optimal x with y fixed: df/dx = 2a*x + c*y = 0 -> x = -c*y/(2a)
// Optimal y with x fixed: df/dy = 2b*y + c*x = 0 -> y = -c*x/(2b)

const C = 1.8; // coupling strength — makes the zigzag vivid

const canvas = document.getElementById('canvas');
const ctx = canvas.getContext('2d');
const W = canvas.width, H = canvas.height;
const CX = W/2, CY = H/2;
const SCALE = 60; // pixels per unit

let a = 0.5, b = 4;
let path = [];       // [{x,y}] in math coords
let step = 0;        // which coordinate to update next (0=x, 1=y)
let animId = null;

function f(x, y) { return a*x*x + b*y*y + C*x*y; }

// Math coords -> canvas coords
function toCanvas(x, y) { return [CX + x*SCALE, CY - y*SCALE]; }
function toMath(px, py)  { return [(px-CX)/SCALE, (CY-py)/SCALE]; }

// Coordinate descent step
function cdStep(pt) {
  const {x, y} = pt;
  if (step % 2 === 0) {
    // Minimize over x: d/dx(a*x^2 + C*x*y) = 2a*x + C*y = 0  => x = -C*y/(2a)
    const nx = -C*y / (2*a);
    step++;
    return {x: nx, y: y};
  } else {
    // Minimize over y: d/dy(b*y^2 + C*x*y) = 2b*y + C*x = 0  => y = -C*x/(2b)
    const ny = -C*x / (2*b);
    step++;
    return {x: x, y: ny};
  }
}

// Draw contours of f
function drawContours() {
  const levels = [0.5, 1.5, 3, 5.5, 9, 14, 20];
  for (const lv of levels) {
    ctx.beginPath();
    let first = true;
    // Approximate ellipse: 2a*x^2 + 2b*y^2 + 2C*x*y = 2*lv (quadratic form)
    // Parametric: sweep angle t, find r(t) on the level curve
    for (let t = 0; t <= 2*Math.PI+0.01; t += 0.04) {
      const dx = Math.cos(t), dy = Math.sin(t);
      const A = a*dx*dx + b*dy*dy + C*dx*dy;
      if (A <= 1e-9) continue;
      const r = Math.sqrt(lv/A);
      const [px, py] = toCanvas(r*dx, r*dy);
      first ? ctx.moveTo(px,py) : ctx.lineTo(px,py);
      first = false;
    }
    ctx.closePath();
    ctx.strokeStyle = 'rgba(100,140,200,0.35)';
    ctx.lineWidth = 1;
    ctx.stroke();
  }
  // Minimum marker
  const [mx, my] = toCanvas(0, 0);
  ctx.beginPath(); ctx.arc(mx, my, 5, 0, 2*Math.PI);
  ctx.fillStyle = '#0a7d33'; ctx.fill();
}

function drawPath() {
  if (path.length < 1) return;
  ctx.lineWidth = 2;
  // Horizontal steps (x changes) in blue, vertical (y changes) in orange
  for (let i = 1; i < path.length; i++) {
    const [x0, y0] = toCanvas(path[i-1].x, path[i-1].y);
    const [x1, y1] = toCanvas(path[i].x, path[i].y);
    // Determine direction: if x changed it was a horizontal step, else vertical
    const horizontal = Math.abs(path[i].x - path[i-1].x) > Math.abs(path[i].y - path[i-1].y);
    ctx.beginPath();
    ctx.moveTo(x0, y0); ctx.lineTo(x1, y1);
    ctx.strokeStyle = horizontal ? '#1d6fa5' : '#e07020';
    ctx.lineWidth = 2.5;
    ctx.stroke();
    // Arrow tip
    const angle = Math.atan2(y1-y0, x1-x0);
    ctx.save();
    ctx.translate(x1, y1);
    ctx.rotate(angle);
    ctx.beginPath();
    ctx.moveTo(0,0); ctx.lineTo(-10, -5); ctx.lineTo(-10, 5); ctx.closePath();
    ctx.fillStyle = horizontal ? '#1d6fa5' : '#e07020';
    ctx.fill();
    ctx.restore();
  }
  // Start marker
  const [sx, sy] = toCanvas(path[0].x, path[0].y);
  ctx.beginPath(); ctx.arc(sx, sy, 6, 0, 2*Math.PI);
  ctx.fillStyle = '#c92f3c'; ctx.fill();
  // Current position
  const last = path[path.length-1];
  const [lx, ly] = toCanvas(last.x, last.y);
  ctx.beginPath(); ctx.arc(lx, ly, 6, 0, 2*Math.PI);
  ctx.fillStyle = '#e07020'; ctx.fill();
}

function drawAxes() {
  ctx.strokeStyle = '#bbb'; ctx.lineWidth = 1;
  ctx.beginPath(); ctx.moveTo(0,CY); ctx.lineTo(W,CY); ctx.stroke();
  ctx.beginPath(); ctx.moveTo(CX,0); ctx.lineTo(CX,H); ctx.stroke();
  ctx.fillStyle = '#999'; ctx.font = '11px system-ui';
  ctx.fillText('x', W-12, CY-6);
  ctx.fillText('y', CX+6, 12);
}

function render() {
  ctx.clearRect(0, 0, W, H);
  drawAxes();
  drawContours();
  drawPath();
}

function dist2(p) { return p.x*p.x + p.y*p.y; }

function updateInfo() {
  const last = path[path.length-1];
  const fval = last ? f(last.x, last.y).toFixed(4) : '—';
  const d = last ? Math.sqrt(dist2(last)).toFixed(4) : '—';
  const done = last && dist2(last) < 0.0001;
  const el = document.getElementById('info');
  el.className = done ? 'info done' : 'info';
  el.textContent = done
    ? fmt('Converged! f = %fval% (distance to min = %d%)', { fval: fval, d: d })
    : last
      ? fmt('Step %v% | f(x,y) = %fval% | dist = %d% | next: %v2%', { v: path.length-1, fval: fval, d: d, v2: step%2===0?'minimize x':'minimize y' })
      : 'Click on the canvas to set a starting point.';
}

function doStep() {
  if (path.length === 0) { updateInfo(); return; }
  const last = path[path.length-1];
  if (dist2(last) < 0.0001) { updateInfo(); return; }
  path.push(cdStep(last));
  render();
  updateInfo();
}

function parseShape() {
  const [av, bv] = document.getElementById('shape').value.split(',').map(Number);
  a = av; b = bv;
}

document.getElementById('shape').addEventListener('change', () => {
  parseShape(); path = []; step = 0; render(); updateInfo();
});

document.getElementById('stepBtn').addEventListener('click', () => {
  stopAnim(); doStep();
});

document.getElementById('runBtn').addEventListener('click', () => {
  if (animId) { stopAnim(); return; }
  if (path.length === 0) { updateInfo(); return; }
  runAnim();
});

document.getElementById('resetBtn').addEventListener('click', () => {
  stopAnim(); path = []; step = 0; render(); updateInfo();
});

function stopAnim() {
  if (animId) { clearInterval(animId); animId = null; }
  document.getElementById('runBtn').textContent = 'Run';
}

function runAnim() {
  document.getElementById('runBtn').textContent = 'Pause';
  const delay = parseInt(document.getElementById('speed').value, 10);
  animId = setInterval(() => {
    const last = path[path.length-1];
    if (!last || dist2(last) < 0.0001) { stopAnim(); return; }
    doStep();
  }, delay);
}

function handleClick(e) {
  stopAnim();
  const rect = canvas.getBoundingClientRect();
  const scaleX = W / rect.width;
  const scaleY = H / rect.height;
  const px = (e.clientX - rect.left) * scaleX;
  const py = (e.clientY - rect.top) * scaleY;
  const [mx, my] = toMath(px, py);
  path = [{x: mx, y: my}];
  step = 0;
  render();
  updateInfo();
}

canvas.addEventListener('click', handleClick);

// Initial render
parseShape();
render();
updateInfo();

// Verification log (used by test harness)
(function verifyCD() {
  // Verify: for f(x,y)=a*x^2+b*y^2+C*x*y, starting from (3,3)
  // After step 1 (min over x): x = -C*y/(2a) = -1.8*3/(2*0.5) = -5.4
  // After step 2 (min over y): y = -C*x/(2b) = -1.8*(-5.4)/(2*4) = 1.215
  // Check these by running the cdStep logic
  const startX = 3, startY = 3;
  let px = startX, py = startY;
  let s = 0;
  function step1(x, y, st) {
    if (st % 2 === 0) return {x: -C*y/(2*a), y: y};
    return {x: x, y: -C*x/(2*b)};
  }
  const r1 = step1(px, py, s); s++;
  const expectedX1 = -C*startY/(2*a); // = -1.8*3/1 = -5.4
  const r2 = step1(r1.x, r1.y, s); s++;
  const expectedY2 = -C*r1.x/(2*b); // = -1.8*(-5.4)/8 = 1.215
  console.assert(Math.abs(r1.x - expectedX1) < 1e-9, 'Step 1 x update failed');
  console.assert(Math.abs(r2.y - expectedY2) < 1e-9, 'Step 2 y update failed');
  console.log('CD verification: step1 x =', r1.x.toFixed(4), '(expected', expectedX1.toFixed(4)+')');
  console.log('CD verification: step2 y =', r2.y.toFixed(4), '(expected', expectedY2.toFixed(4)+')');
  console.log('Coordinate descent demo verified OK');
})();

<div class="controls">
  <label>Bowl shape:
    <select id="shape">
      <option value="1,1">Circular (a=1, b=1)</option>
      <option value="0.5,4" selected>Elongated (a=0.5, b=4)</option>
      <option value="0.2,5">Very elongated (a=0.2, b=5)</option>
    </select>
  </label>
  <label>Speed:
    <select id="speed">
      <option value="600">Slow</option>
      <option value="300" selected>Normal</option>
      <option value="120">Fast</option>
    </select>
  </label>
</div>
<canvas id="canvas" width="380" height="320"></canvas>
<div class="info" id="info">Click the canvas to set start point, then step.</div>
<div class="btns">
  <button id="stepBtn" type="button">Step</button>
  <button id="runBtn" type="button">Run</button>
  <button id="resetBtn" type="button" class="ghost">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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Coordinate descent on f(x,y) = a*x^2 + b*y^2.
// Minimum is at (0,0). Each step fixes one coordinate and minimizes the 1-D slice:
//   fix y -> optimal x = 0  (df/dx = 2a*x = 0)
//   fix x -> optimal y = 0  (df/dy = 2b*y = 0)
// For a general quadratic A*x^2 + B*y^2 the exact coordinate update is:
//   x_new = -gradient_x / (2a) = 0,  y_new = -gradient_y / (2b) = 0
// which for this bowl means both coordinates go directly to 0 in one step each.
// To make the zigzag visible we perturb with a coupling term:
//   f(x,y) = a*x^2 + b*y^2 + c*x*y
// Optimal x with y fixed: df/dx = 2a*x + c*y = 0 -> x = -c*y/(2a)
// Optimal y with x fixed: df/dy = 2b*y + c*x = 0 -> y = -c*x/(2b)

const C = 1.8; // coupling strength — makes the zigzag vivid

const canvas = document.getElementById('canvas');
const ctx = canvas.getContext('2d');
const W = canvas.width, H = canvas.height;
const CX = W/2, CY = H/2;
const SCALE = 60; // pixels per unit

let a = 0.5, b = 4;
let path = [];       // [{x,y}] in math coords
let step = 0;        // which coordinate to update next (0=x, 1=y)
let animId = null;

function f(x, y) { return a*x*x + b*y*y + C*x*y; }

// Math coords -> canvas coords
function toCanvas(x, y) { return [CX + x*SCALE, CY - y*SCALE]; }
function toMath(px, py)  { return [(px-CX)/SCALE, (CY-py)/SCALE]; }

// Coordinate descent step
function cdStep(pt) {
  const {x, y} = pt;
  if (step % 2 === 0) {
    // Minimize over x: d/dx(a*x^2 + C*x*y) = 2a*x + C*y = 0  => x = -C*y/(2a)
    const nx = -C*y / (2*a);
    step++;
    return {x: nx, y: y};
  } else {
    // Minimize over y: d/dy(b*y^2 + C*x*y) = 2b*y + C*x = 0  => y = -C*x/(2b)
    const ny = -C*x / (2*b);
    step++;
    return {x: x, y: ny};
  }
}

// Draw contours of f
function drawContours() {
  const levels = [0.5, 1.5, 3, 5.5, 9, 14, 20];
  for (const lv of levels) {
    ctx.beginPath();
    let first = true;
    // Approximate ellipse: 2a*x^2 + 2b*y^2 + 2C*x*y = 2*lv (quadratic form)
    // Parametric: sweep angle t, find r(t) on the level curve
    for (let t = 0; t <= 2*Math.PI+0.01; t += 0.04) {
      const dx = Math.cos(t), dy = Math.sin(t);
      const A = a*dx*dx + b*dy*dy + C*dx*dy;
      if (A <= 1e-9) continue;
      const r = Math.sqrt(lv/A);
      const [px, py] = toCanvas(r*dx, r*dy);
      first ? ctx.moveTo(px,py) : ctx.lineTo(px,py);
      first = false;
    }
    ctx.closePath();
    ctx.strokeStyle = 'rgba(100,140,200,0.35)';
    ctx.lineWidth = 1;
    ctx.stroke();
  }
  // Minimum marker
  const [mx, my] = toCanvas(0, 0);
  ctx.beginPath(); ctx.arc(mx, my, 5, 0, 2*Math.PI);
  ctx.fillStyle = '#0a7d33'; ctx.fill();
}

function drawPath() {
  if (path.length < 1) return;
  ctx.lineWidth = 2;
  // Horizontal steps (x changes) in blue, vertical (y changes) in orange
  for (let i = 1; i < path.length; i++) {
    const [x0, y0] = toCanvas(path[i-1].x, path[i-1].y);
    const [x1, y1] = toCanvas(path[i].x, path[i].y);
    // Determine direction: if x changed it was a horizontal step, else vertical
    const horizontal = Math.abs(path[i].x - path[i-1].x) > Math.abs(path[i].y - path[i-1].y);
    ctx.beginPath();
    ctx.moveTo(x0, y0); ctx.lineTo(x1, y1);
    ctx.strokeStyle = horizontal ? '#1d6fa5' : '#e07020';
    ctx.lineWidth = 2.5;
    ctx.stroke();
    // Arrow tip
    const angle = Math.atan2(y1-y0, x1-x0);
    ctx.save();
    ctx.translate(x1, y1);
    ctx.rotate(angle);
    ctx.beginPath();
    ctx.moveTo(0,0); ctx.lineTo(-10, -5); ctx.lineTo(-10, 5); ctx.closePath();
    ctx.fillStyle = horizontal ? '#1d6fa5' : '#e07020';
    ctx.fill();
    ctx.restore();
  }
  // Start marker
  const [sx, sy] = toCanvas(path[0].x, path[0].y);
  ctx.beginPath(); ctx.arc(sx, sy, 6, 0, 2*Math.PI);
  ctx.fillStyle = '#c92f3c'; ctx.fill();
  // Current position
  const last = path[path.length-1];
  const [lx, ly] = toCanvas(last.x, last.y);
  ctx.beginPath(); ctx.arc(lx, ly, 6, 0, 2*Math.PI);
  ctx.fillStyle = '#e07020'; ctx.fill();
}

function drawAxes() {
  ctx.strokeStyle = '#bbb'; ctx.lineWidth = 1;
  ctx.beginPath(); ctx.moveTo(0,CY); ctx.lineTo(W,CY); ctx.stroke();
  ctx.beginPath(); ctx.moveTo(CX,0); ctx.lineTo(CX,H); ctx.stroke();
  ctx.fillStyle = '#999'; ctx.font = '11px system-ui';
  ctx.fillText('x', W-12, CY-6);
  ctx.fillText('y', CX+6, 12);
}

function render() {
  ctx.clearRect(0, 0, W, H);
  drawAxes();
  drawContours();
  drawPath();
}

function dist2(p) { return p.x*p.x + p.y*p.y; }

function updateInfo() {
  const last = path[path.length-1];
  const fval = last ? f(last.x, last.y).toFixed(4) : '—';
  const d = last ? Math.sqrt(dist2(last)).toFixed(4) : '—';
  const done = last && dist2(last) < 0.0001;
  const el = document.getElementById('info');
  el.className = done ? 'info done' : 'info';
  el.textContent = done
    ? fmt('Converged! f = %fval% (distance to min = %d%)', { fval: fval, d: d })
    : last
      ? fmt('Step %v% | f(x,y) = %fval% | dist = %d% | next: %v2%', { v: path.length-1, fval: fval, d: d, v2: step%2===0?'minimize x':'minimize y' })
      : 'Click on the canvas to set a starting point.';
}

function doStep() {
  if (path.length === 0) { updateInfo(); return; }
  const last = path[path.length-1];
  if (dist2(last) < 0.0001) { updateInfo(); return; }
  path.push(cdStep(last));
  render();
  updateInfo();
}

function parseShape() {
  const [av, bv] = document.getElementById('shape').value.split(',').map(Number);
  a = av; b = bv;
}

document.getElementById('shape').addEventListener('change', () => {
  parseShape(); path = []; step = 0; render(); updateInfo();
});

document.getElementById('stepBtn').addEventListener('click', () => {
  stopAnim(); doStep();
});

document.getElementById('runBtn').addEventListener('click', () => {
  if (animId) { stopAnim(); return; }
  if (path.length === 0) { updateInfo(); return; }
  runAnim();
});

document.getElementById('resetBtn').addEventListener('click', () => {
  stopAnim(); path = []; step = 0; render(); updateInfo();
});

function stopAnim() {
  if (animId) { clearInterval(animId); animId = null; }
  document.getElementById('runBtn').textContent = 'Run';
}

function runAnim() {
  document.getElementById('runBtn').textContent = 'Pause';
  const delay = parseInt(document.getElementById('speed').value, 10);
  animId = setInterval(() => {
    const last = path[path.length-1];
    if (!last || dist2(last) < 0.0001) { stopAnim(); return; }
    doStep();
  }, delay);
}

function handleClick(e) {
  stopAnim();
  const rect = canvas.getBoundingClientRect();
  const scaleX = W / rect.width;
  const scaleY = H / rect.height;
  const px = (e.clientX - rect.left) * scaleX;
  const py = (e.clientY - rect.top) * scaleY;
  const [mx, my] = toMath(px, py);
  path = [{x: mx, y: my}];
  step = 0;
  render();
  updateInfo();
}

canvas.addEventListener('click', handleClick);

// Initial render
parseShape();
render();
updateInfo();

// Verification log (used by test harness)
(function verifyCD() {
  // Verify: for f(x,y)=a*x^2+b*y^2+C*x*y, starting from (3,3)
  // After step 1 (min over x): x = -C*y/(2a) = -1.8*3/(2*0.5) = -5.4
  // After step 2 (min over y): y = -C*x/(2b) = -1.8*(-5.4)/(2*4) = 1.215
  // Check these by running the cdStep logic
  const startX = 3, startY = 3;
  let px = startX, py = startY;
  let s = 0;
  function step1(x, y, st) {
    if (st % 2 === 0) return {x: -C*y/(2*a), y: y};
    return {x: x, y: -C*x/(2*b)};
  }
  const r1 = step1(px, py, s); s++;
  const expectedX1 = -C*startY/(2*a); // = -1.8*3/1 = -5.4
  const r2 = step1(r1.x, r1.y, s); s++;
  const expectedY2 = -C*r1.x/(2*b); // = -1.8*(-5.4)/8 = 1.215
  console.assert(Math.abs(r1.x - expectedX1) < 1e-9, 'Step 1 x update failed');
  console.assert(Math.abs(r2.y - expectedY2) < 1e-9, 'Step 2 y update failed');
  console.log('CD verification: step1 x =', r1.x.toFixed(4), '(expected', expectedX1.toFixed(4)+')');
  console.log('CD verification: step2 y =', r2.y.toFixed(4), '(expected', expectedY2.toFixed(4)+')');
  console.log('Coordinate descent demo verified OK');
})();

Result

Console

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.

The Real Complexity

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.

Where It Matters

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.

Conclusion

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.

Comments

Loading comments...

https://www.kipuhub.com/en/article/coordinate-descent/Content licensed under CC BY-NC 4.0.

Cookies & privacy

Coordinate Descent

The optimizer that cheats by forgetting all but one direction