Gradient descent measures every step with a ruler — the straight-line, Euclidean one. Nemirovski & Yudin asked: what if the ruler fit the problem? On the probability simplex the right ruler is relative entropy, and the same descent step becomes multiplicative — each coordinate x₁ ← x₁·e−ηg₁, renormalized. No projection, and the price of dimension drops from d to log d. Down the center the pieces go in, the engine iterates, the proven geometry comes out. Blue builds; red breaks.
source Nemirovski & Yudin, Problem Complexity and Method Efficiency in Optimization (Wiley-Interscience, 1983) — the origin; no stable free scan, cited by author/title/year AMBER. Accessible modern treatment: Bubeck, arXiv:1405.4980 §4 AMBER. Rendered, not quoted.
A mirror descent step is not "move against the gradient." It is: move against the gradient in the dual, then map back. Pick a strictly convex mirror map ψ; the update is
∇ψ(xt+1) = ∇ψ(xt) − η·gt
Change ψ and you change the ruler:
| mirror map ψ(x) | ∇ψ | the step becomes |
|---|---|---|
| ½‖x‖² (Euclidean) | x | plain GD: x − ηg |
| Σ x₁ log x₁ (neg-entropy) | log x + 1 | EG: x₁·e−ηg₁ / Z |
For the panel's current step, the live entropy update vs. the plain step it replaces:
Mirror descent is the-gradient-descent read in a non-Euclidean geometry. The Euclidean map recovers it exactly — GD is the special case, not the general one.
On the simplex the natural ruler is the-kl-divergence: the Bregman divergence of neg-entropy is KL. That is why the update multiplies and why "stay on the simplex" is free. Its continuous kin is multiplicative weights — the same exponential update behind the-regret-matching. Each sphere is the next one's premise.
The blue team's live re-check of the invariants that make the geometry sound: the entropy step is exponentiated-gradient, the iterate sums to 1, Bregman is KL, and the radius is log d. If red skips the renormalization, this badge is where it shows.
Mirror descent needs four things fed in: a convex objective f, a mirror map ψ (which fixes the ruler), a step η, and a start point. Two constructed problems on the 3-simplex, each with a closed-form optimum:
| problem | gradient | known optimum |
|---|---|---|
| quadratic ½‖x−a‖² | x − a | interior a = (.5,.3,.2) |
| linear ⟨c,x⟩, c=(.2,.7,.5) | c | vertex e₁ = (1,0,0) |
The start is the simplex center u = (⅓,⅓,⅓) — whose worst-case Bregman radius is exactly log d. Feed these into the panel below.
Entropy map: the step is multiplicative and the ruler is KL — the iterate never leaves the simplex.
| step | divergence to opt |
|---|
Every iterate is computed from the mirror-descent update on the spot — the trajectory, the divergence, and the feasibility are never looked up.
What the machine proves, live: with the entropy map the update is exactly exponentiated-gradient and the iterate stays on the simplex (non-negative, sums to 1 to 1e-12) with no projection; the Euclidean map recovers plain gradient descent exactly; the neg-entropy Bregman divergence is the KL divergence (verified to 1e-9); and the initial radius from the center is log d, not d — the geometry pays off.
The witness (left) confirms these live; the red team (right) tries to make them false.
And it is still a first-order, sub-linear method: O(1/√t) for general non-smooth convex problems — the constant improves, the rate does not. Constant η converges only to a neighborhood in general; our two constructed problems are picked because the entropy update's fixed point is the optimum exactly (disclosed — that is why the panel reaches machine zero).
"Mirror descent is faster than gradient descent." Cut. Same O(1/√t) rate; what shrinks is the dimension factor in the constant (d → log d on the simplex). Speed of the bound, not the order.
"Exponentiated gradient needs a projection back onto the simplex." Cut. The renormalization is the Bregman (KL) projection — closed-form division by Z, no solver.
"The mirror map is just a fancy preconditioner / diagonal rescaling." Kept, corrected. A preconditioner is one fixed linear map; ψ warps the whole space and its dual, giving a state-dependent, non-linear step (here, exponential).
The red team's move: skip the renormalization. The exponentiated iterate x₁·e−ηg₁ is no longer divided by Z, so its mass drifts and it walks off the probability simplex — the witness (window 7) is watching the sum.
Skip the / Z and the iterate's coordinates stop summing to 1 — it leaves the simplex, the witness recomputes, disagrees, and turns red. Nothing is faked; the attack is real and it is caught.