Continuous FunctionStart learning

Foundation Lab

Bregman Divergence & Mirror Descent

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

Concept 70 of 100TheoryPhase 10
Inspect equationAll Foundations
#70BregmanTheory
key equation
DΦ(p,q)=Φ(p)−Φ(q)−⟨∇Φ(q),p−q⟩D_\Phi(p, q) = \Phi(p) - \Phi(q) - \langle \nabla\Phi(q), p - q \rangle
Reading map and next steps

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Φ(p,q)=Φ(p)−Φ(q)−⟨∇Φ(q),p−q⟩D_\Phi(p, q) = \Phi(p) - \Phi(q) - \langle \nabla\Phi(q), p - q \rangle
PredictionCommit before tracing the equation.

Ask what should change under a concrete input, then trace that expectation through the equation.

EvidenceCompare the equation and source.

Use the key equation and canonical papers as the available witnesses, without implying that a runnable panel exists.

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.

Inspect equationBrowse atlasNext foundation

Why It Matters for Modern Models

  • 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 Tutorials Skip

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

Visualization Status

Core Math (Optional Deep Dive)

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

Key Equation
DΦ(p,q)=Φ(p)−Φ(q)−⟨∇Φ(q),p−q⟩D_\Phi(p, q) = \Phi(p) - \Phi(q) - \langle \nabla\Phi(q), p - q \rangle

Bregman divergence generated by strictly convex Φ\Phi:

DΦ(p,q)=Φ(p)−Φ(q)−⟨∇Φ(q),p−q⟩D_\Phi(p, q) = \Phi(p) - \Phi(q) - \langle \nabla\Phi(q), p - q \rangle

Mirror descent:

xt+1=arg⁡min⁡x∈X{⟨gt,x⟩+1ηDΦ(x,xt)}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:

  • Φ(x)=12∥x∥2\Phi(x) = \frac{1}{2}\|x\|^2 → Euclidean GD, DΦD_\Phi = squared distance
  • Φ(x)=∑ixilog⁡xi\Phi(x) = \sum_i x_i \log x_i → KL divergence on simplex (exponentiated gradient)

Canonical Papers

Mirror Descent and Nonlinear Projected Subgradient Methods

Beck & Teboulle2003Operations Research Letters
Read paper →

Prediction, Learning, and Games

Cesa-Bianchi & Lugosi2006Cambridge University Press
Read paper →

Connections

Prerequisites

ℐFisher Info🧭Natural Grad

Next Moves

Choose the next question to carry this object forward.