Bregman divergence

In mathematics, specifically statistics and information geometry, a Bregman divergence or Bregman distance is a measure of difference between two points, defined in terms of a strictly convex function; they form an important class of divergences. When the points are interpreted as probability distributions – notably as either values of the parameter of a parametric model or as a data set of observed values – the resulting distance is a statistical distance. The most basic Bregman divergence is the squared Euclidean distance. Bregman divergences are similar to metrics, but satisfy neither the triangle inequality (ever) nor symmetry (in general). However, they satisfy a generalization of the Pythagorean theorem, and in information geometry the corresponding statistical manifold is interpreted as a (dually) flat manifold. This allows many techniques of optimization theory to be generalized to Bregman divergences, geometrically as generalizations of least squares. Bregman divergences are named after Russian mathematician Lev M. Bregman, who introduced the concept in 1967. Let be a continuously-differentiable, strictly convex function defined on a convex set . The Bregman distance associated with F for points is the difference between the value of F at point p and the value of the first-order Taylor expansion of F around point q evaluated at point p: Non-negativity: for all , . This is a consequence of the convexity of . Positivity: When is strictly convex, iff . Uniqueness up to affine difference: iff is an affine function. Convexity: is convex in its first argument, but not necessarily in the second argument. If F is strictly convex, then is strictly convex in its first argument. For example, Take f(x) = |x|, smooth it at 0, then take , then . Linearity: If we think of the Bregman distance as an operator on the function F, then it is linear with respect to non-negative coefficients. In other words, for strictly convex and differentiable, and , Duality: If F is strictly convex, then the function F has a convex conjugate which is also strictly convex and continuously differentiable on some convex set .