Introduction

Every optimizer eventually faces the same question: which direction should the next step go, and how far?

Ordinary gradient descent has a clean answer: subtract a multiple of the gradient and land somewhere in Euclidean space. For unconstrained problems on flat landscapes, that is perfectly fine. But many real problems live on constraint sets with their own natural geometry — and forcing a Euclidean ruler onto a curved space is like measuring angles with a straight stick.

The probability simplex is the canonical example. A point on the simplex is a probability distribution over nn outcomes: each coordinate xi≥0x_{i} \geq 0 and they sum to one. A naive gradient step can push coordinates negative and immediately leave the feasible set. Projecting back works, but ignores the fact that the simplex is not flat — distances near the boundary behave very differently from distances near the center.

Mirror descent, introduced by Nemirovski and Yudin in 1983, fixes this by choosing a mirror map Φ\Phi whose geometry matches the constraint set. Instead of stepping in primal space and projecting, you:

  1. Map the current point xx to the dual space via ∇Φ(x)\nabla\Phi(x).
  2. Take the gradient step there.
  3. Map back to primal space via (∇Φ)−1(\nabla\Phi)^{-1}.

On the simplex the natural mirror map is the negative entropy Φ(x)=∑ixiln⁡xi\Phi(x) = \sum_{i} x_{i} \ln x_{i}. The resulting update is the multiplicative weights rule: each coordinate is multiplied by e−ηgie^{-\eta g_{i}} and renormalized, where gig_{i} is the ii-th component of the gradient and η\eta is the step size. Coordinates stay positive automatically — no projection needed.

The payoff is a convergence rate that depends on the entropy diameter of the simplex, ln⁡n\ln n, instead of the Euclidean diameter n\sqrt{n}. That logarithmic versus square-root gap is the whole story of why mirror descent matters.

Try It: Descend on the Simplex

Below is a 3-coordinate simplex (an equilateral triangle). A linear objective f(x)=c⋅xf(x) = c \cdot x is minimized over the simplex — the optimum is always at a vertex. Both algorithms start at the center (13,13,13)(\tfrac{1}{3}, \tfrac{1}{3}, \tfrac{1}{3}) and take steps toward the same minimum.

<!-- Two-panel demo: simplex trajectory + objective value plot -->
<div class="controls">
  <label>Step size η: <input id="eta" type="range" min="0.05" max="1.0" step="0.05" value="0.3"> <span id="eta-val">0.3</span></label>
  <label>Gradient direction:
    <select id="dir">
      <option value="0">Push toward vertex x₀</option>
      <option value="1">Push toward vertex x₁</option>
      <option value="2">Push toward vertex x₂</option>
    </select>
  </label>
</div>
<div class="panels">
  <canvas id="simplex" width="200" height="180" title="Simplex trajectory"></canvas>
  <canvas id="objplot" width="200" height="180" title="Objective value over steps"></canvas>
</div>
<div class="legend">
  <span class="dot eucl"></span>Euclidean projected GD
  <span class="dot mirr"></span>Mirror descent (entropy)
</div>
<div id="status" class="status"></div>
<div class="btns">
  <button id="btn-step">Step</button>
  <button id="btn-run">Run</button>
  <button id="btn-reset" class="ghost">Reset</button>
</div>

/* Styles for the mirror descent demo panels */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; color: #222; }
.controls { display: flex; flex-wrap: wrap; gap: .5rem 1rem; margin-bottom: .4rem; font-size: .85rem; }
.controls label { display: flex; align-items: center; gap: .4rem; }
input[type=range] { width: 90px; }
.panels { display: flex; gap: 8px; flex-wrap: wrap; }
canvas { border: 1px solid #cdd9e3; border-radius: 8px; background: #f7fafc; }
.legend { display: flex; align-items: center; gap: 1rem; font-size: .82rem; margin: .35rem 0; }
.dot { display: inline-block; width: 11px; height: 11px; border-radius: 50%; margin-right: 3px; }
.dot.eucl { background: #e63946; }
.dot.mirr { background: #1d6fa5; }
.status { font-size: .88rem; font-weight: 600; min-height: 1.4em; margin: .25rem 0; }
.status.ok { color: #0a7d33; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 13px system-ui; padding: .4rem .8rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Mirror descent vs Euclidean projected gradient descent on the 3-simplex.
// Feasible set: probability simplex {x: x_i >= 0, sum(x) = 1}.
// Euclidean GD step: x_{t+1} = proj(x_t - eta * g)
// Mirror descent (entropy map) step: x_{t+1,i} = x_{t,i} * exp(-eta * g_i) / Z

const cs = document.getElementById('simplex');
const cp = document.getElementById('objplot');
const ctxS = cs.getContext('2d');
const ctxP = cp.getContext('2d');
const WS = cs.width, HS = cs.height;
const WP = cp.width, HP = cp.height;

// Canvas pixel coordinates of the three simplex vertices
const V = [
  [WS/2,  10],         // top vertex: x0=1
  [10,   HS-10],       // bottom-left vertex: x1=1
  [WS-10, HS-10]       // bottom-right vertex: x2=1
];

// Barycentric to canvas-pixel conversion
function toPx(x) {
  return [
    x[0]*V[0][0] + x[1]*V[1][0] + x[2]*V[2][0],
    x[0]*V[0][1] + x[1]*V[1][1] + x[2]*V[2][1]
  ];
}

// Linear objective gradients — one per target vertex
const GRADS = [
  [-1,  0.5, 0.5],   // pushes toward vertex x0=1
  [ 0.5, -1, 0.5],   // pushes toward vertex x1=1
  [ 0.5, 0.5, -1]    // pushes toward vertex x2=1
];

// Evaluate the linear objective f(x) = g . x
function objective(pt, g) { return g[0]*pt[0] + g[1]*pt[1] + g[2]*pt[2]; }

// Project onto the simplex using the O(n log n) sort algorithm
function projSimplex(v) {
  const u = [...v].sort((a, b) => b - a);
  let cssv = 0, rho = 0;
  for (let j = 0; j < 3; j++) {
    cssv += u[j];
    if (u[j] - (cssv - 1) / (j + 1) > 0) rho = j;
  }
  const theta = (u.slice(0, rho+1).reduce((a,b) => a+b, 0) - 1) / (rho + 1);
  return v.map(vi => Math.max(vi - theta, 0));
}

// Shared state: current points, paths, and objective histories
let eucl, mirr, path_e, path_m, obj_e, obj_m, running, animId, stepCount;
const MAX_STEPS = 60;

function getEta() { return parseFloat(document.getElementById('eta').value); }
function getGrad() { return GRADS[parseInt(document.getElementById('dir').value)]; }

function reset() {
  if (animId) { cancelAnimationFrame(animId); animId = null; }
  running = false;
  stepCount = 0;
  // Start from the uniform distribution (centroid of the simplex)
  eucl = [1/3, 1/3, 1/3];
  mirr = [1/3, 1/3, 1/3];
  path_e = [[...eucl]];
  path_m = [[...mirr]];
  const g = getGrad();
  obj_e = [objective(eucl, g)];
  obj_m = [objective(mirr, g)];
  document.getElementById('btn-run').textContent = I18N.btn_run;
  setStatus('', '');
  draw();
}

// Euclidean projected gradient descent update
function stepEuclidean(g, eta) {
  const raw = eucl.map((xi, i) => xi - eta * g[i]);
  eucl = projSimplex(raw);
  path_e.push([...eucl]);
  obj_e.push(objective(eucl, g));
}

// Mirror descent update: multiply by exp(-eta*g), renormalize
function stepMirror(g, eta) {
  const raw = mirr.map((xi, i) => xi * Math.exp(-eta * g[i]));
  const Z = raw.reduce((a, b) => a + b, 0);
  mirr = raw.map(v => v / Z);
  path_m.push([...mirr]);
  obj_m.push(objective(mirr, g));
}

function drawSimplex() {
  ctxS.clearRect(0, 0, WS, HS);
  // Draw filled triangle representing the simplex
  ctxS.beginPath();
  ctxS.moveTo(V[0][0], V[0][1]);
  ctxS.lineTo(V[1][0], V[1][1]);
  ctxS.lineTo(V[2][0], V[2][1]);
  ctxS.closePath();
  ctxS.fillStyle = '#eef3f7';
  ctxS.fill();
  ctxS.strokeStyle = '#8a9aac';
  ctxS.lineWidth = 1.3;
  ctxS.stroke();

  // Label the three extreme points
  ctxS.font = '10px ui-monospace, monospace';
  ctxS.fillStyle = '#3d5166';
  ctxS.textAlign = 'center';
  ctxS.fillText('x₀=1', V[0][0], V[0][1] - 3);
  ctxS.fillText('x₁=1', V[1][0] - 2, V[1][1] + 11);
  ctxS.fillText('x₂=1', V[2][0] + 2, V[2][1] + 11);

  // Mark the shared starting point with a gray dot
  const [sx, sy] = toPx([1/3,1/3,1/3]);
  ctxS.beginPath(); ctxS.arc(sx, sy, 3, 0, 2*Math.PI);
  ctxS.fillStyle = '#888'; ctxS.fill();

  // Draw dashed trajectory lines for both algorithms
  for (const [pts, color] of [[path_e, '#e63946'], [path_m, '#1d6fa5']]) {
    if (pts.length < 2) continue;
    ctxS.beginPath();
    ctxS.strokeStyle = color; ctxS.lineWidth = 1.6; ctxS.setLineDash([3,3]);
    const [x0, y0] = toPx(pts[0]); ctxS.moveTo(x0, y0);
    for (let i = 1; i < pts.length; i++) { const [x,y] = toPx(pts[i]); ctxS.lineTo(x,y); }
    ctxS.stroke(); ctxS.setLineDash([]);
  }
  // Draw current position dots for both algorithms
  for (const [pt, color] of [[eucl, '#e63946'], [mirr, '#1d6fa5']]) {
    const [px, py] = toPx(pt);
    ctxS.beginPath(); ctxS.arc(px, py, 4, 0, 2*Math.PI);
    ctxS.fillStyle = color; ctxS.fill();
  }
}

function drawObjPlot() {
  ctxP.clearRect(0, 0, WP, HP);
  const PAD = { l: 26, r: 8, t: 14, b: 22 };
  const pw = WP - PAD.l - PAD.r, ph = HP - PAD.t - PAD.b;

  // Draw plot axes for the objective value chart
  ctxP.strokeStyle = '#8a9aac'; ctxP.lineWidth = 1;
  ctxP.beginPath();
  ctxP.moveTo(PAD.l, PAD.t); ctxP.lineTo(PAD.l, PAD.t + ph);
  ctxP.lineTo(PAD.l + pw, PAD.t + ph);
  ctxP.stroke();

  ctxP.font = '9px system-ui'; ctxP.fillStyle = '#3d5166'; ctxP.textAlign = 'center';
  ctxP.fillText(I18N.axis_x, PAD.l + pw/2, HP - 3);
  ctxP.save(); ctxP.translate(9, PAD.t + ph/2); ctxP.rotate(-Math.PI/2);
  ctxP.fillText(I18N.axis_y, 0, 0); ctxP.restore();

  const allVals = [...obj_e, ...obj_m];
  const minV = Math.min(...allVals), maxV = Math.max(...allVals);
  const range = maxV - minV || 1;
  const T = Math.max(obj_e.length, obj_m.length);

  const toXY = (t, v) => [
    PAD.l + (t / Math.max(T - 1, 1)) * pw,
    PAD.t + (1 - (v - minV) / range) * ph
  ];

  // Plot objective value over steps for both algorithms
  for (const [obj, color] of [[obj_e, '#e63946'], [obj_m, '#1d6fa5']]) {
    if (obj.length < 2) continue;
    ctxP.beginPath(); ctxP.strokeStyle = color; ctxP.lineWidth = 1.6;
    ctxP.setLineDash([]);
    const [x0, y0] = toXY(0, obj[0]); ctxP.moveTo(x0, y0);
    for (let i = 1; i < obj.length; i++) {
      const [x, y] = toXY(i, obj[i]); ctxP.lineTo(x, y);
    }
    ctxP.stroke();
  }

  ctxP.font = '9px system-ui'; ctxP.fillStyle = '#555'; ctxP.textAlign = 'right';
  ctxP.fillText(minV.toFixed(2), PAD.l - 2, PAD.t + ph);
  ctxP.fillText(maxV.toFixed(2), PAD.l - 2, PAD.t + 6);
}

function draw() { drawSimplex(); drawObjPlot(); }

function step() {
  if (stepCount >= MAX_STEPS) return;
  const g = getGrad(), eta = getEta();
  stepEuclidean(g, eta);
  stepMirror(g, eta);
  stepCount++;
  draw();
  const last_e = obj_e[obj_e.length - 1];
  const last_m = obj_m[obj_m.length - 1];
  setStatus(
    (I18N.msg_step||'')
      .replace('{n}', stepCount)
      .replace('{e}', last_e.toFixed(3))
      .replace('{m}', last_m.toFixed(3)),
    'ok'
  );
}

function setStatus(t, cls) {
  const s = document.getElementById('status');
  s.textContent = t;
  s.className = 'status ' + cls;
}

let I18N = {};

function animate() {
  if (stepCount < MAX_STEPS) {
    step();
    animId = requestAnimationFrame(() => setTimeout(animate, 120));
  } else {
    running = false;
    document.getElementById('btn-run').textContent = I18N.btn_run;
  }
}

document.getElementById('eta').addEventListener('input', function() {
  document.getElementById('eta-val').textContent = this.value;
  reset();
});
document.getElementById('btn-step').addEventListener('click', () => { if (!running) step(); });
document.getElementById('btn-run').addEventListener('click', function() {
  if (running) {
    running = false;
    if (animId) { cancelAnimationFrame(animId); animId = null; }
    this.textContent = I18N.btn_run;
  } else {
    running = true;
    this.textContent = I18N.btn_pause;
    animate();
  }
});
document.getElementById('btn-reset').addEventListener('click', reset);
document.getElementById('dir').addEventListener('change', reset);

// Receive translations from the parent kipu frame
window.addEventListener('message', function(e) {
  if (e.data && e.data.type === 'kipu-i18n') {
    I18N = e.data.translations;
    reset();
  }
});
// Fallback if message event never fires
setTimeout(() => { if (!Object.keys(I18N).length) { I18N = window.__KIPU_I18N_FALLBACK__ || {}; reset(); } }, 200);
Result
Console

Euclidean projected gradient descent moves in a straight line, clips to the simplex, and zig-zags near the boundary. Mirror descent with the entropy mirror map multiplies each coordinate by an exponential weight and renormalizes — it curves naturally along the simplex surface and reaches the vertex in far fewer steps.

Adjust the step size and gradient direction, then press Step or Run to watch the trajectories diverge.

The Real Complexity

The power of mirror descent is not that it is faster in wall-clock time — each step costs roughly the same as projected gradient descent. The gain is in how many steps you need.

The standard analysis tracks the Bregman divergence DΦ(y,x)=Φ(y)−Φ(x)−∇Φ(x)⊤(y−x)D_{\Phi}(y, x) = \Phi(y) - \Phi(x) - \nabla\Phi(x)^{\top}(y - x), which generalizes squared Euclidean distance. The key theorem is:

∑t=1T(f(xt)−f(x∗))  ≤  DΦ(x∗,x1)η+η∑t=1T∥∇f(xt)∥∗2\sum_{t=1}^{T} \bigl(f(x_t) - f(x^*)\bigr) \;\leq\; \frac{D_{\Phi}(x^*, x_1)}{\eta} + \eta \sum_{t=1}^{T} \|\nabla f(x_t)\|_{*}^{2}

where ∥⋅∥∗\|\cdot\|_{*} is the dual norm. Choosing η\eta optimally gives a regret of O ⁣(DΦ(x∗,x1)⋅T)O\!\left(\sqrt{D_{\Phi}(x^*, x_1) \cdot T}\right).

Now the geometry enters:

  • Euclidean mirror map Φ(x)=12∥x∥2\Phi(x) = \tfrac{1}{2}\|x\|^{2}: the Bregman divergence is the squared Euclidean distance. On the simplex DΦ(x∗,x1)≤nD_{\Phi}(x^*, x_1) \leq \sqrt{n} (diameter), giving regret O ⁣(n/T)O\!\left(\sqrt{n / T}\right).
  • Entropy mirror map Φ(x)=∑ixiln⁡xi\Phi(x) = \sum_{i} x_{i} \ln x_{i}: the Bregman divergence is the KL divergence DKL(x∗∥x1)D_{\mathrm{KL}}(x^* \| x_1). Starting from the uniform distribution, DKL(x∗∥x1)=ln⁡nD_{\mathrm{KL}}(x^* \| x_1) = \ln n, giving regret O ⁣((ln⁡n)/T)O\!\left(\sqrt{(\ln n) / T}\right).

The ratio between the two rates is n/ln⁡n\sqrt{n / \ln n}, which grows without bound. For n=1000n = 1000 outcomes, the entropy mirror map needs roughly 145 times fewer steps to reach the same accuracy — an exponential improvement hiding behind a logarithm.

This is not magic: the entropy mirror map is strongly convex with respect to the ℓ1\ell_1 norm on the simplex, and the ℓ1\ell_1 geometry is precisely what probability distributions live in. The map encodes the shape of the set into the algorithm's notion of distance.

Where It Matters

The mirror-descent framework unifies a surprising family of algorithms:

  • Multiplicative Weights Update (MWU): mirror descent with the entropy mirror map applied to the simplex. This is the engine behind Freund and Schapire's AdaBoost (1997), online portfolio management, and approximation algorithms for packing/covering LPs.
  • Exponentiated Gradient (EG): the same update viewed as a prediction algorithm. It achieves optimal regret for learning from expert advice — the Hedge algorithm is exactly entropy mirror descent.
  • Natural gradient descent: replace the Euclidean inner product with the Fisher information metric of a statistical model. This is mirror descent with the log-partition function as the mirror map, and it converges exponentially faster on curved statistical manifolds.
  • AdaGrad and Adam: modern deep-learning optimizers adapt the geometry per coordinate. AdaGrad's diagonal update is equivalent to mirror descent with the mirror map Φ(x)=12x⊤Hx\Phi(x) = \tfrac{1}{2} x^{\top} H x where HH accumulates gradient outer products.
  • Game theory and equilibrium: online mirror descent is the standard tool for computing Nash equilibria in large normal-form games — see Nash Equilibrium.

The unifying principle: whenever the constraint set has a natural geometry different from Euclidean, mirror descent is the right tool. The mirror map encodes what "distance" means in your problem, and that choice propagates into every convergence guarantee.

Related topics: Linear Programming, PAC Learning.

Conclusion

Mirror descent teaches a lesson that echoes far beyond optimization: the geometry you impose on a problem determines how hard the problem is.

Euclidean gradient descent is a brilliant algorithm for Euclidean problems. But the probability simplex is not Euclidean — it lives in ℓ1\ell_1 space, its corners are its extremes, and its natural notion of distance is the KL divergence. Once you use the entropy mirror map to match the algorithm's geometry to the problem's geometry, an exponential improvement falls out almost for free.

The same principle drives natural gradient, AdaGrad, and the multiplicative weights family. Every time a modern machine-learning paper introduces a custom optimizer or a new divergence, it is asking the same question Nemirovski and Yudin asked in 1983: what shape is this problem, really?

That question — matching geometry to structure — sits at the heart of non-convex optimization and the practical limits of learning algorithms everywhere.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

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