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.
is compact, it achieves minimal value
is continuous and strictly convex on it, and bounded below by
has continuous derivative, and given any line segment
Proof idea: For any quadratic function
still has such derivative-linearity, so we will subtract away a few quadratic functions and show that
The proof idea can be illustrated fully for the case of
is a quadratic function on any line segment in
respectively to remove the quadratic terms along the three lines.
A key tool in computational geometry is the idea of projective duality, which maps points to hyperplanes and vice versa, while preserving incidence and above-below relationships.
There are numerous analytical forms of the projective dual: one common form maps the point
This mapping can be interpreted (identifying the hyperplane with its normal) as the convex conjugate mapping that takes the point p to its dual point
If we now replace the paraboloid by an arbitrary convex function, we obtain a different dual mapping that retains the incidence and above-below properties of the standard projective dual.
This implies that natural dual concepts in computational geometry like Voronoi diagrams and Delaunay triangulations retain their meaning in distance spaces defined by an arbitrary Bregman divergence.
Thus, algorithms from "normal" geometry extend directly to these spaces (Boissonnat, Nielsen and Nock, 2010) Bregman divergences can be interpreted as limit cases of skewed Jensen divergences (see Nielsen and Boltz, 2011).
Jensen divergences can be generalized using comparative convexity, and limit cases of these skewed Jensen divergences generalizations yields generalized Bregman divergence (see Nielsen and Nock, 2017).
Bregman divergences can also be defined between matrices, between functions, and between measures (distributions).
Bregman divergences between matrices include the Stein's loss and von Neumann entropy.
Bregman divergences between functions include total squared error, relative entropy, and squared bias; see the references by Frigyik et al. below for definitions and properties.
Similarly Bregman divergences have also been defined over sets, through a submodular set function which is known as the discrete analog of a convex function.
The submodular Bregman divergences subsume a number of discrete distance measures, like the Hamming distance, precision and recall, mutual information and some other set based distance measures (see Iyer & Bilmes, 2012 for more details and properties of the submodular Bregman.)
For a list of common matrix Bregman divergences, see Table 15.1 in.
[8] In machine learning, Bregman divergences are used to calculate the bi-tempered logistic loss, performing better than the softmax function with noisy datasets.
[9] Bregman divergence is used in the formulation of mirror descent, which includes optimization algorithms used in machine learning such as gradient descent and the hedge algorithm.
