Mirror Descent

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 $n$ outcomes: each coordinate $x_{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 $x$ to the dual space via $\nabla\Phi(x)$.
2. Take the gradient step there.
3. Map back to primal space via $(\nabla\Phi)^{-1}$.

On the simplex the natural mirror map is the negative entropy $\Phi(x) = \sum_{i} x_{i} \ln x_{i}$. The resulting update is the multiplicative weights rule: each coordinate is multiplied by $e^{-\eta g_{i}}$ and renormalized, where $g_{i}$ is the $i$-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$, instead of the Euclidean diameter $\sqrt{n}$. That logarithmic versus square-root gap is the whole story of why mirror descent matters.

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

<!-- {{c_html_desc}} -->
<div class="controls">
  <label>{{lbl_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>{{lbl_direction}}
    <select id="dir">
      <option value="0">{{dir_opt0}}</option>
      <option value="1">{{dir_opt1}}</option>
      <option value="2">{{dir_opt2}}</option>
    </select>
  </label>
</div>
<div class="panels">
  <canvas id="simplex" width="200" height="180" title="{{canvas_title}}"></canvas>
  <canvas id="objplot" width="200" height="180" title="{{objplot_title}}"></canvas>
</div>
<div class="legend">
  <span class="dot eucl"></span>{{lbl_eucl}}
  <span class="dot mirr"></span>{{lbl_mirr}}
</div>
<div id="status" class="status"></div>
<div class="btns">
  <button id="btn-step">{{btn_step}}</button>
  <button id="btn-run">{{btn_run}}</button>
  <button id="btn-reset" class="ghost">{{btn_reset}}</button>
</div>

/* {{c_css_desc}} */
* { 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; }

// Code not found

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 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_{\Phi}(y, x) = \Phi(y) - \Phi(x) - \nabla\Phi(x)^{\top}(y - x)$, which generalizes squared Euclidean distance. The key theorem is:

$$\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\!\left(\sqrt{D_{\Phi}(x^*, x_1) \cdot T}\right)$.

Now the geometry enters:

• Euclidean mirror map $\Phi(x) = \tfrac{1}{2}\|x\|^{2}$: the Bregman divergence is the squared Euclidean distance. On the simplex $D_{\Phi}(x^*, x_1) \leq \sqrt{n}$ (diameter), giving regret $O\!\left(\sqrt{n / T}\right)$.
• Entropy mirror map $\Phi(x) = \sum_{i} x_{i} \ln x_{i}$: the Bregman divergence is the KL divergence $D_{\mathrm{KL}}(x^* \| x_1)$. Starting from the uniform distribution, $D_{\mathrm{KL}}(x^* \| x_1) = \ln n$, giving regret $O\!\left(\sqrt{(\ln n) / T}\right)$.

The ratio between the two rates is $\sqrt{n / \ln n}$, which grows without bound. For $n = 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 $\ell_1$ norm on the simplex, and the $\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.

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 $\Phi(x) = \tfrac{1}{2} x^{\top} H x$ where $H$ 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.

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 $\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.