---

Bregman Divergences

A Bregman Divergence is a general way to measure the distance between two points. The Euclidean Distance is a special case of Bregman Divergences, in fact the BD is a generalization of all ways to measure distances on strictly convex sets.

Let be a strictly convex, differentiable function

The Bregman Divergence (in some papers called Bregman Loss Function) is defined as:

• is the true value of
• is the gradient of
• note that is the first-order Taylor Approximation of around .

The divergence is the gap between the real value and the linear approximation (using taylor).

Some applications of the Bregman Divergences are in Clustering Algorithms (See Banjee et al., 2005).

BD requires that the function is strictly convex and differentiable.

Examples of Bregman Divergences

Some special cases of the Bregman Divergences are:

The Euclidean squared distance:

The Kullback-Leibler Divergence (from information theory)

That is used in t-SNE

The Itakura-Saito divergences (used for example in audio, speech):

Properties of Bregman Divergences

Non-negativity

with equality if and only if (iff)

Asymmetry (not symmetric)

in general.

Not a metric (triangle disequality doesn’t hold). Therefore it’s a divergence and not a distance.

Affine Invariance Adding and affine invariance does not change the divergences. Let .

Duality Property If is the convex conjugate of , then:

This connects divergences in the primal and dual spaces.

Connections to generalized means Centroids under Bregman Divergences corresponde to generalized means, not necessary Euclidean averages.