Continuous Function

Foundation reference

Bregman Divergence & Mirror Descent

A Bregman divergence D_Φ(p, q) measures how far a strictly convex, differentiable function Φ, evaluated at p, lies above its tangent plane at q. Mirror descent uses this divergence in place of squared Euclidean distance, so choosing Φ chooses the geometry of the update. On the probability simplex, entropic mirror descent has an error bound that grows only like √(ln n) with dimension n, which can beat projected gradient descent by a factor of order √(n / ln n) (Beck & Teboulle, 2003).

Concept 70 of 100TheoryStudy phase 10
Go to the mathAll concepts
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

Study guide

Where to start

Concept 70 of 100Bregman DivergenceTheory · Study phase 10: Mathematical foundations & information geometry
Question

Gradient descent is mirror descent with the squared Euclidean distance; what changes when that distance is replaced by the KL divergence on the probability simplex?

Go to the mathAll conceptsNext concept
How to study this pagePredict · Check · Generalize · Continue
PredictSay what you expect.

Pick a concrete input and say what the equation should give before you read the math.

CheckCheck against the math and the papers.

Work through the math, then read the cited papers for the original argument.

GeneralizeName what stays the same.

Identify the part of the idea that survives a change of notation or model, so you can recognize it in another paper or system.

ContinueFollow the connections.

Use the prerequisites and related concepts at the end of the page to fill the next gap.

Why It Matters for Modern Models

  • A Bregman divergence D_Φ(p, q) measures how far a strictly convex, differentiable function Φ, evaluated at p, lies above its tangent plane at q. Mirror descent uses this divergence in place of squared Euclidean distance, so choosing Φ chooses the geometry of the update. On the probability simplex, entropic mirror descent has an error bound that grows only like √(ln n) with dimension n, which can beat projected gradient descent by a factor of order √(n / ln n) (Beck & Teboulle, 2003).
  • The exponentiated-gradient and multiplicative-weights algorithms of online learning are mirror descent with the negative entropy (Cesa-Bianchi & Lugosi, 2006).
  • It connects to natural gradient through exponential families: with log-partition function A, the KL divergence between two members is the Bregman divergence of A, and the Fisher matrix is the Hessian ∇²A. Raskutti & Mukherjee (2015) show that mirror descent with this potential is natural gradient descent in the dual (mean) parameters.

Questions to Think About

  • Why is a mirror-descent step the same as mapping the point to the coordinates ∇Φ(x), taking an ordinary gradient step there, and mapping back with the inverse of ∇Φ?
  • Why does the negative entropy Φ(p) = Σᵢ pᵢ log pᵢ generate the KL divergence as its Bregman divergence on the probability simplex?

Core Math

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

Let Φ\Phi be a strictly convex, differentiable function. The Bregman divergence it generates measures how far Φ(p)\Phi(p) lies above the tangent plane of Φ\Phi at qq (Bregman, 1967):

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

It is zero only when p=qp = q, but in general it is not symmetric and does not satisfy the triangle inequality.

Mirror descent replaces the squared Euclidean distance in a gradient step with a Bregman divergence (Beck & Teboulle, 2003):

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\}

Without constraints, setting the gradient to zero shows that this is an ordinary gradient step in the "mirror" coordinates ∇Φ(x)\nabla\Phi(x): ∇Φ(xt+1)=∇Φ(xt)−η gt\nabla\Phi(x_{t+1}) = \nabla\Phi(x_t) - \eta\, g_t.

Special cases:

  • Φ(x)=12∥x∥2\Phi(x) = \frac{1}{2}\|x\|^2 gives DΦ(p,q)=12∥p−q∥2D_\Phi(p, q) = \frac{1}{2}\|p - q\|^2, and mirror descent is gradient descent.
  • Φ(x)=∑ixilog⁡xi\Phi(x) = \sum_i x_i \log x_i (the negative entropy) gives the KL divergence on the probability simplex, and mirror descent becomes the exponentiated-gradient update xt+1,i∝xt,i e−ηgt,ix_{t+1,i} \propto x_{t,i}\, e^{-\eta g_{t,i}}.

Key Papers and Books

Mirror descent and nonlinear projected subgradient methods for convex optimization

Beck & Teboulle2003Operations Research Letters
Read paper →

Prediction, Learning, and Games

Cesa-Bianchi & Lugosi2006Cambridge University Press
View book →

The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming

Bregman1967USSR Computational Mathematics and Mathematical Physics
Read paper →

The Information Geometry of Mirror Descent

Raskutti & Mukherjee2015IEEE Transactions on Information Theory
Read paper →

Connections

Prerequisites

Fisher InformationNatural Gradient