Part 9 of 15. Every strictly convex function gives you a divergence. KL is one. Squared Euclidean distance is another. The unifying object is the Bregman divergence, and all the machinery of Part 8 (Pythagorean projection, dually flat geometry) works for every Bregman divergence, with the convex generator replacing the log-partition function.
Play: Select a convex generator function (like negative entropy for KL) and drag the reference point y (amber) or the target point x (red). The Bregman divergence is exactly the vertical gap between the true function value at x and the linear approximation made at y.
A Bregman divergence is a measure of difference between two points, generated entirely by a single strictly convex, differentiable function . For any two points , the divergence from to is:
Because the function is strictly convex, its tangent plane always sits below the graph. Therefore, the gap—the Bregman divergence—is always strictly positive unless .
By dropping the requirement that must be a log-partition function of a probability distribution (as in Parts 2–8), we generalise the geometry. Every Bregman divergence induces its own dually flat geometry with its own Pythagorean theorem. The choice of generator function determines the specific divergence (e.g., squared Euclidean, KL, Itakura-Saito, or Logistic).
Here are the four most common Bregman divergences and the convex generators that produce them.
| Name | φ(x) | D_φ(x ‖ y) | Where it shows up |
|---|---|---|---|
| Squared Euclidean | least-squares, Gaussian regression, k-means clustering | ||
| Kullback-Leibler | exp families, maximum likelihood, cross-entropy loss | ||
| Itakura-Saito | speech and audio (NMF), scale-invariant reconstruction | ||
| Logistic | binary classification, logistic regression, Bernoulli likelihood |
Each generator picks a kind of error. Squared Euclidean is symmetric and scale-free. KL is asymmetric and tail-sensitive. Itakura-Saito is scale-invariant (), which fits audio power spectra where shape matters more than magnitude. Logistic divergence sharpens near the classification boundary.
KL is two things at once. The information-theoretic excess description length from Part 4, and the Bregman divergence of the negative-entropy generator. The exponential family's log-partition function is the Legendre dual of negative entropy, and Bregman divergences are invariant under the dual.
Every Bregman divergence satisfies a Pythagorean theorem. Pick a convex generator , define the divergence , and consider three points . If the straight line from to (in coordinates) is "orthogonal" to the straight line from to , in the sense that the inner product of -differences and -differences is zero, where is the dual coordinate, then
Identical in form to Part 8 with replaced by . The Bregman setting is the natural home of the theorem; KL on exponential families is the special case.
The Pythagorean theorem gives a projection theorem: the Bregman projection onto a convex set is unique, exists, and decomposes additively. That underpins Bregman-ball clustering (k-means generalised), Bregman-Voronoi diagrams (Part 11), and mirror descent's convergence proof.
K-means generalises to any Bregman divergence (Banerjee-Merugu-Dhillon-Ghosh, 2005). Replace "distance from point to centre" with the Bregman divergence and "centre is the mean of assigned points" with "centre is the Bregman centroid." For squared Euclidean, the centroid is the arithmetic mean. For KL, it is the expectation-parameter average (moment-matched distribution). For Itakura-Saito, the geometric mean on a log scale.
If your data is a set of probability distributions, use KL. Audio power spectra: Itakura-Saito. Spatial points: squared Euclidean.
A second application that links Bregman divergences to Part 10's natural gradient. Ordinary gradient descent on a convex loss takes the step . You can reinterpret this as choosing the next iterate to minimise a squared-Euclidean-penalised surrogate:
The surrogate is a linear approximation of the loss plus a squared Euclidean regulariser that keeps you near the current iterate. Now replace the squared Euclidean regulariser with a generic Bregman divergence:
This is mirror descent (Nemirovski-Yudin 1983, Beck-Teboulle 2003). Different give different methods. On the simplex, negative entropy gives multiplicative weights (exponentiated gradient). On the positive orthant, the log-barrier gives an interior-point method. On , you recover ordinary gradient descent.
Natural gradient descent (Part 10) is mirror descent with the Fisher quadratic form as regulariser, equivalently with the log-partition function as generator.
Bregman unifies everything in this series. The Fisher metric is the Hessian of a Bregman generator. KL is a Bregman divergence. Natural gradient is a Bregman-regularised step. The e- and m-connections are the primal and dual gradient fields. Parts 2–8 are the special case where the generator is an exponential family's log-partition function.
Part 10 turns this scaffolding into an algorithm: natural gradient descent. Rediscovered many times in deep learning under different names, now standard in variational quantum computing as "Quantum Natural Gradient." We will see it beat vanilla SGD on a toy landscape where the difference is visible.