Bregman divergences arise from convex potentials. They are the divergence side of dually flat geometry and mirror descent.
Convex potential
A Bregman divergence measures the gap between a convex function and its tangent plane.
Definition. For a differentiable strictly convex function \(\varphi\) on a convex domain, \[ D_\varphi(x,y)=\varphi(x)-\varphi(y)-\langle\nabla\varphi(y),x-y\rangle. \]
Proposition. \(D_\varphi(x,y)\ge0\), with equality iff \(x=y\) when \(\varphi\) is strictly convex.
Proof. Convexity gives \(\varphi(x)\ge\varphi(y)+\langle\nabla\varphi(y),x-y\rangle\). Strict convexity makes equality possible only at \(x=y\).
Metric and dual coordinates
The Hessian of the potential is the metric in primal affine coordinates.
Proposition. The local quadratic expansion is \[ D_\varphi(x,x+\mathrm{d}x) =\frac12\partial_i\partial_j\varphi(x)\,\mathrm{d}x^i\mathrm{d}x^j+o(\|\mathrm{d}x\|^2). \]
Proof. Taylor expand \(\varphi(x+\mathrm{d}x)\) and \(\nabla\varphi(x+\mathrm{d}x)\) in the definition. First-order terms cancel, leaving half the Hessian quadratic form.
Generalized Pythagorean theorem
Bregman projections satisfy an exact additive identity when the residual is dual-orthogonal.
Theorem. If \(y\) is the Bregman projection of \(x\) onto a convex affine set \(C\), then for \(z\in C\), \[ D_\varphi(z,x)=D_\varphi(z,y)+D_\varphi(y,x) \] when the first-order optimality condition gives the required orthogonality; in general the right side is a lower bound.
Proof. A direct three-point identity gives \[ D_\varphi(z,x)-D_\varphi(z,y)-D_\varphi(y,x) =\langle\nabla\varphi(y)-\nabla\varphi(x),z-y\rangle. \] For projection onto an affine set, the first-order condition makes this inner product zero for feasible \(z-y\).
Examples
KL on exponential families is a Bregman divergence of the log-partition function.
Remark. Squared Euclidean distance comes from \(\varphi(x)=\|x\|^2/2\). KL divergence between members of the same exponential family comes from the cumulant potential.
Legendre potentials and dual coordinates
Let \(\Omega\subset\mathbb R^d\) be open and convex and let \(\psi\in C^2(\Omega)\) be strictly convex. Its Bregman divergence is \[ B_\psi(x,y) =\psi(x)-\psi(y)-\langle\nabla\psi(y),x-y\rangle. \] Convexity gives nonnegativity; strict convexity gives equality only at \(x=y\). It is convex in its first argument but generally not its second.
Proposition (duality). If \(\psi\) is Legendre type and \(x^*=\nabla\psi(x)\), then \[ B_\psi(x,y)=B_{\psi^*}(y^*,x^*). \]
Proof. Fenchel equality gives \(\psi(x)+\psi^*(x^*)=\langle x,x^*\rangle\), and similarly for \(y\). Substitute these identities into the right side and simplify.
The three-point identity
Lemma. For \(x,y,z\in\Omega\), \[ B_\psi(x,z) =B_\psi(x,y)+B_\psi(y,z) +\langle x-y,\nabla\psi(y)-\nabla\psi(z)\rangle. \]
Proof. Expand the three divergences. The potential values cancel, leaving exactly the displayed pairing.
Theorem (Bregman projection). Let \(\mathcal C\subset\Omega\) be closed and convex, and suppose \(y=\arg\min_{z\in\mathcal C}B_\psi(z,x)\) exists. Then \[ \langle z-y,\nabla\psi(y)-\nabla\psi(x)\rangle\ge0 \quad(z\in\mathcal C) \] and \[ B_\psi(z,x)\ge B_\psi(z,y)+B_\psi(y,x). \]
Proof. Differentiate \(t\mapsto B_\psi(y+t(z-y),x)\) at \(0+\) to obtain the variational inequality. Insert it into the three-point identity.
Canonical examples
- \(\psi(x)=\tfrac12\|x\|_2^2\) gives squared Euclidean distance \(\tfrac12\|x-y\|_2^2\).
- \(\psi(p)=\sum_i p_i\log p_i\) on the positive orthant gives generalized KL: \(\sum_i p_i\log(p_i/q_i)-p_i+q_i\).
- \(\psi(x)=-\sum_i\log x_i\) gives Itakura--Saito geometry: \(\sum_i\{x_i/y_i-\log(x_i/y_i)-1\}\).
Bregman divergences are coordinate objects generated by a convex potential; not every Bregman divergence is an \(f\)-divergence. On a probability simplex, the only divergence that is both separable Bregman and an \(f\)-divergence, under standard regularity, is KL up to scale and affine terms.