Bregman Divergence

Learnt a new mathematical concept: Bregman divergence. Knew about Kullback-Leibler divergence but this one I didn't know about. The concept of dual space is very interesting.  the following is from Wiki page.

Definition[edit]

Let ${\displaystyle F\mathrm{\Omega }\mathbb{R}}$ be a continuously-differentiable real-valued and strictly convex function defined on a closed convex set ${\displaystyle \mathrm{\Omega }}$.

The Bregman distance associated with F for points ${\displaystyle pq\mathrm{\Omega }}$ is the difference between the value of F at point p and the value of the first-order Taylor expansion of Faround point q evaluated at point p:

${\displaystyle D_F}$ p qF pF q∇F q pq 

Properties[edit]

• Non-negativity: ${\displaystyle D_F}$ p q0 for all p, q. This is a consequence of the convexity of F.
• Convexity:${\displaystyle D_F}$ p q is convex in its first argument, but not necessarily in the second argument (see ^[1])
• 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 ${\displaystyle F_1{F}_2}$strictly convex and differentiable, and ${\displaystyle \lambda 0}$,

${\displaystyle D_{F_1\lambda F_2}}$ p  q  DF1 p  q  λ DF2 p  q 

• Duality: The function F has a convex conjugate ${\displaystyle F^{}}$. The Bregman distance defined with respect to ${\displaystyle F^{}}$ has an interesting relationship to ${\displaystyle D_F}$ p q

${\displaystyle D_{F^{}}{p}^{}{q}^{}}$ DF q p

Here, ${\displaystyle p^{}\mathrm{\nabla }Fp}$ and ${\displaystyle q^{}\mathrm{\nabla }Fq}$ are the dual points corresponding to p and q.

• Mean as minimizer: A key result about Bregman divergences is that, given a random vector, the mean vector minimizes the expected Bregman divergence from the random vector. This result generalizes the textbook result that the mean of a set minimizes total squared error to elements in the set. This result was proved for the vector case by (Banerjee et al. 2005), and extended to the case of functions/distributions by (Frigyik et al. 2008). This result is important because it further justifies using a mean as a representative of a random set, particularly in Bayesian estimation.

Examples[edit]

• Squared Euclidean distance ${\displaystyle D_F}$ x yxy2 is the canonical example of a Bregman distance, generated by the convex function ${\displaystyle Fxx{}^2}$
• The squared Mahalanobis distance, ${\displaystyle D_F}$ x y12 xyTQ xy  which is generated by the convex function ${\displaystyle Fx\frac{1}{2}{x}^{T}Qx}$. This can be thought of as a generalization of the above squared Euclidean distance.
• The generalized Kullback–Leibler divergence

${\displaystyle D_F}$ p  q  p i logpiqi p  i  q i 

is generated by the convex function

${\displaystyle F}$ p ip i logp i p i 

• The Itakura–Saito distance,

${\displaystyle D_F}$  p  q   ipiqilogpiqi1

is generated by the convex function

${\displaystyle F}$ p logp i