Foundation Lab

Bregman Divergence & Mirror Descent

Explains why different geometries suit different problems—simplex needs KL, not Euclidean

Concept 70 of 100TheoryPhase 10

#70BregmanTheory

key equationD_\Phi(p, q) = \Phi(p) - \Phi(q) - \langle \nabla\Phi(q), p - q \rangle

Selected Foundation Object

Keep the equation fixed; move through the evidence.

Concept 70 of 100BregmanTheory / Phase 10: Mathematical foundations & information geometry

Current question

Euclidean gradient descent is ONE choice; mirror descent is the general framework

D_\Phi(p, q) = \Phi(p) - \Phi(q) - \langle \nabla\Phi(q), p - q \rangle

PredictionCommit before the demo.

Ask what should change when the equation is manipulated, then let the visualization test that expectation.

EvidenceCompare local witness and source.

Use the runnable panel, the key equation, and canonical papers as separate forms of evidence for the same object.

InvariantName what survives notation changes.

The useful learning product is the reusable mechanism you can carry into another model, paper, or engineering tradeoff.

Next moveContinue through the atlas.

Use prerequisites, dependents, and semantic links to repair the next gap without leaving the object behind.

Explains why different geometries suit different problems—simplex needs KL, not Euclidean
Exponentiated gradient (softmax updates) is mirror descent with entropy potential
Natural gradient is Bregman geometry with Fisher information as the potential

What is still poorly explained in textbooks and papers:

Euclidean gradient descent is ONE choice; mirror descent is the general framework
The "mirror map" transforms to dual coordinates where steps are linear
KL divergence is the Bregman divergence for probability distributions

If you want intuition first, start with the key equation and the visualization. Come back here for the full walkthrough.

Key Equation

D_\Phi(p, q) = \Phi(p) - \Phi(q) - \langle \nabla\Phi(q), p - q \rangle

Bregman divergence generated by strictly convex $\Phi$ :

D_\Phi(p, q) = \Phi(p) - \Phi(q) - \langle \nabla\Phi(q), p - q \rangle

Mirror descent:

x_{t+1} = \arg\min_{x \in \mathcal{X}} \left\{ \langle g_t, x \rangle + \frac{1}{\eta} D_\Phi(x, x_t) \right\}

Special cases:

$\Phi(x) = \frac{1}{2}\|x\|^2$ → Euclidean GD, $D_\Phi$ = squared distance
$\Phi(x) = \sum_i x_i \log x_i$ → KL divergence on simplex (exponentiated gradient)

Beck & Teboulle2003Operations Research Letters

Cesa-Bianchi & Lugosi2006Cambridge University Press

Choose the next question to carry this object forward.