Inmathematics, specificallystatistics andinformation geometry, aBregman divergence orBregman distance is a measure of difference between two points, defined in terms of a strictlyconvex function; they form an important class ofdivergences. When the points are interpreted asprobability distributions – notably as either values of the parameter of aparametric model or as a data set of observed values – the resulting distance is astatistical distance. The most basic Bregman divergence is thesquared Euclidean distance.

Bregman divergences are similar tometrics, but satisfy neither thetriangle inequality (ever) nor symmetry (in general). However, they satisfy a generalization of thePythagorean theorem, and ininformation geometry the correspondingstatistical manifold is interpreted as a (dually)flat manifold. This allows many techniques ofoptimization theory to be generalized to Bregman divergences, geometrically as generalizations ofleast squares.

Bregman divergences are named after Soviet and Israeli mathematicianLev M. Bregman, who introduced the concept in 1967.

Let${\displaystyle F:\mathrm{\Omega }\to \mathbb{R}}$ be a continuously-differentiable, strictlyconvex function defined on aconvex set${\displaystyle \mathrm{\Omega }}$.

The Bregman distance associated withF for points${\displaystyle p,q\in \mathrm{\Omega }}$ is the difference between the value ofF at pointp and the value of the first-orderTaylor expansion ofF around pointq evaluated at pointp:$${\displaystyle D_F(p,q)=F(p)-F(q)-⟨\mathrm{\nabla }F(q),p-q⟩.}$$

• Non-negativity:${\displaystyle D_F(p,q)\ge 0}$ for all${\displaystyle p}$,${\displaystyle q}$. This is a consequence of the convexity of${\displaystyle F}$.
• Positivity: When${\displaystyle F}$ is strictly convex,${\displaystyle D_F(p,q)=0}$ if and only if${\displaystyle p=q}$.
• Uniqueness up to affine difference:${\displaystyle D_F=D_G}$ if and only if${\displaystyle F-G}$ is an affine function.
• Convexity:${\displaystyle D_F(p,q)}$ is convex in its first argument, but not necessarily in the second argument. If F is strictly convex, then${\displaystyle D_F(p,q)}$ is strictly convex in its first argument.
  • For example, Takef(x) = |x|, smooth it at 0, then take${\displaystyle y=1,x_1=0.1,x_2=-0.9,x_3=0.9x_1+0.1x_2}$, then${\displaystyle D_f(y,x_3)\approx 1>0.9D_f(y,x_1)+0.1D_f(y,x_2)\approx 0.2}$.
• Linearity: If we think of the Bregman distance as an operator on the functionF, 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 \ge 0}$,$${\displaystyle D_{F_1+\lambda F_2}(p,q)=D_{F_1}(p,q)+\lambda D_{F_2}(p,q)}$$
• Duality: If F is strictly convex, then the function F has aconvex conjugate${\displaystyle F^{\ast }}$ which is also strictly convex and continuously differentiable on some convex set${\displaystyle {\mathrm{\Omega }}^{\ast }}$. The Bregman distance defined with respect to${\displaystyle F^{\ast }}$ is dual to${\displaystyle D_F(p,q)}$ as$${\displaystyle D_{F^{\ast }}(p^{\ast },q^{\ast })=D_F(q,p)}$$ Here,${\displaystyle p^{\ast }=\mathrm{\nabla }F(p)}$ and${\displaystyle q^{\ast }=\mathrm{\nabla }F(q)}$ are the dual points corresponding top andq.
  Moreover, using the same notations:$${\displaystyle D_F(p,q)=F(p)+F^{\ast }(q^{\ast })-⟨p,q^{\ast }⟩}$$
• Integral form: by the integral remainder form ofTaylor's Theorem, a Bregman divergence can be written as the integral of the Hessian of${\displaystyle F}$ along the line segment between the Bregman divergence's arguments.
• 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.
• Bregman balls are bounded, and compact if X is closed: Define Bregman ball centered at x with radius r by${\displaystyle B_f(x,r):=\left\{y\in X:D_f(y,x)\le r\right\}}$. When${\displaystyle X\subset {\mathbb{R}}^n}$ is finite dimensional,${\displaystyle \mathrm{\forall }x\in X}$, if${\displaystyle x}$ is in the relative interior of${\displaystyle X}$, or if${\displaystyle X}$ is locally closed at${\displaystyle x}$ (that is, there exists a closed ball${\displaystyle B(x,r)}$ centered at${\displaystyle x}$, such that${\displaystyle B(x,r)\cap X}$ is closed), then${\displaystyle B_f(x,r)}$ is bounded for all${\displaystyle r}$ . If${\displaystyle X}$ is closed, then${\displaystyle B_f(x,r)}$ is compact for all${\displaystyle r}$.
• Law of cosines:^[1]
  For any${\displaystyle p,q,z}$$${\displaystyle D_F(p,q)=D_F(p,z)+D_F(z,q)-(p-z{)}^T(\mathrm{\nabla }F(q)-\mathrm{\nabla }F(z))}$$
• Parallelogram law: for any${\displaystyle \theta ,{\theta }_1,{\theta }_2}$,$${\displaystyle B_F\left({\theta }_1:\theta \right)+B_F\left({\theta }_2:\theta \right)=B_F\left({\theta }_1:\frac{{\theta }_1+{\theta }_2}{2}\right)+B_F\left({\theta }_2:\frac{{\theta }_1+{\theta }_2}{2}\right)+2B_F\left(\frac{{\theta }_1+{\theta }_2}{2}:\theta \right)}$$

  

• Bregman projection: For any${\displaystyle W\subset \mathrm{\Omega }}$, define the "Bregman projection" of${\displaystyle q}$ onto${\displaystyle W}$:$${\displaystyle P_W(q)=\underset{\omega \in W}{\mathrm{argmin}}{D}_F(\omega ,q).}$$ Then
  • if${\displaystyle W}$ is convex, then the projection is unique if it exists;
  • if${\displaystyle W}$ is nonempty, closed, and convex and${\displaystyle \mathrm{\Omega }\subset {\mathbb{R}}^n}$ is finite dimensional, then the projection exists and is unique.^[3]
• Generalized Pythagorean Theorem:^[1]
  For any${\displaystyle v\in \mathrm{\Omega },a\in W}$,$${\displaystyle D_F(a,v)\ge D_F(a,P_W(v))+D_F(P_W(v),v).}$$ This is an equality if${\displaystyle P_W(v)}$ is in therelative interior of${\displaystyle W}$.
  In particular, this always happens when${\displaystyle W}$ is an affine set.
• Lack of triangle inequality: Since the Bregman divergence is essentially a generalization of squared Euclidean distance, there is no triangle inequality. Indeed,${\displaystyle D_F(z,x)-D_F(z,y)-D_F(y,x)=⟨\mathrm{\nabla }f(y)-\mathrm{\nabla }f(x),z-y⟩}$, which may be positive or negative.

• The only symmetric Bregman divergences on${\displaystyle X\subset {\mathbb{R}}^n}$ are squared generalized Euclidean distances (Mahalanobis distance), that is,${\displaystyle D_f(y,x)=(y-x{)}^{T}A(y-x)}$ for somepositive definite${\displaystyle A}$.^[5]

Proof

For any${\displaystyle x\ne y\in X}$ , define${\displaystyle r=\Vert y-x\Vert ,v=(y-x)/r,g(t)=f(x+tv)}$ for${\displaystyle t\in [0,r]}$ . Let${\displaystyle z(t)=x+tv}$.

Then${\displaystyle g^{\prime }(t)=⟨\mathrm{\nabla }f(z(t)),v⟩}$ for${\displaystyle t\in (0,r)}$ , and since${\displaystyle \mathrm{\nabla }f}$ is continuous, also for${\displaystyle t=0,r}$ .

Then, from the diagram, we see that for${\displaystyle D_f(x;z(t))=D_f(z(t);x)}$ for all${\displaystyle t\in [0,r]}$ , we must have${\displaystyle g^{\prime }(t)}$ linear on${\displaystyle t\in [0,r]}$.

Thus we find that${\displaystyle \mathrm{\nabla }f}$ varies linearly along any direction. By the next lemma,${\displaystyle f}$ is quadratic. Since${\displaystyle f}$ is also strictly convex, it is of form${\displaystyle f(x)+x^{T}Ax+B^{T}x+C}$ , where${\displaystyle A\succ 0}$.

Lemma: If${\displaystyle S}$ is an open subset of${\displaystyle {\mathbb{R}}^n}$ ,${\displaystyle f:S\to \mathbb{R}}$ has continuous derivative, and given any line segment${\displaystyle [x,x+v]\subset S}$ , the function${\displaystyle h(t):=⟨\mathrm{\nabla }f(x+tv),v⟩}$ is linear in${\displaystyle t}$ , then${\displaystyle f}$ is a quadratic function.

Proof idea: For any quadratic function${\displaystyle q:S\to \mathbb{R}}$ , we have${\displaystyle f-q}$ still has such derivative-linearity, so we will subtract away a few quadratic functions and show that${\displaystyle f}$ becomes zero.

The proof idea can be illustrated fully for the case of${\displaystyle S={\mathbb{R}}^2}$ , so we prove it in this case.

By the derivative-linearity,${\displaystyle f}$ is a quadratic function on any line segment in${\displaystyle {\mathbb{R}}^2}$. We subtract away four quadratic functions, such that${\displaystyle g:=f-q_0-q_1-q_2-q_3}$ becomes identically zero on the x-axis, y-axis, and the${\displaystyle \{x=y\}}$ line.

Let${\displaystyle q_0(x,y)=f(0,0)+\mathrm{\nabla }f(0,0)\cdot (x,y),q_1(x,y)=A_1{x}^2,q_2(x,y)=A_2{y}^2,q_3(x,y)=A_{3}xy}$, for well-chosen${\displaystyle A_1,A_2,A_3}$. Now use${\displaystyle q_0}$ to remove the linear term, and use${\displaystyle q_1,q_2,q_3}$ respectively to remove the quadratic terms along the three lines.

${\displaystyle \mathrm{\forall }(x,y)\in {\mathbb{R}}^2}$ not on the origin, there exists a line${\displaystyle l}$ across${\displaystyle (x,y)}$ that intersects the x-axis, y-axis, and the${\displaystyle \{x=y\}}$ line at three different points. Since${\displaystyle g}$ is quadratic on${\displaystyle l}$ , and is zero on three different points,${\displaystyle g}$ is identically zero on${\displaystyle l}$ , thus${\displaystyle g(x,y)=0}$. Thus${\displaystyle f=q_0+q_1+q_2+q_3}$ is quadratic.

The following two characterizations are for divergences on${\displaystyle {\mathrm{\Gamma }}_n}$, the set of all probability measures on${\displaystyle \{1,2,...,n\}}$, with${\displaystyle n\ge 2}$.

Define a divergence on${\displaystyle {\mathrm{\Gamma }}_n}$ as any function of type${\displaystyle D:{\mathrm{\Gamma }}_n\times {\mathrm{\Gamma }}_n\to [0,\mathrm{\infty }]}$, such that${\displaystyle D(x,x)=0}$ for all${\displaystyle x\in {\mathrm{\Gamma }}_n}$, then:

• The only divergence on${\displaystyle {\mathrm{\Gamma }}_n}$ that is both a Bregman divergence and anf-divergence is theKullback–Leibler divergence.^[6]
• If${\displaystyle n\ge 3}$, then any Bregman divergence on${\displaystyle {\mathrm{\Gamma }}_n}$ that satisfies thedata processing inequality must be the Kullback–Leibler divergence. (In fact, a weaker assumption of "sufficiency" is enough.) Counterexamples exist when${\displaystyle n=2}$.^[6]

Given a Bregman divergence${\displaystyle D_F}$, its "opposite", defined by${\displaystyle D_F^{\ast }(v,w)=D_F(w,v)}$, is generally not a Bregman divergence. For example, the Kullback-Leiber divergence is both a Bregman divergence and an f-divergence. Its reverse is also an f-divergence, but by the above characterization, the reverse KL divergence cannot be a Bregman divergence.

• The canonical example of a Bregman distance is the squared Euclidean distance${\displaystyle D_F(x,y)=\Vert x-y{\Vert }^2}$.
• The squaredMahalanobis distance${\displaystyle D_F(x,y)=\frac{1}{2}(x-y{)}^{T}Q(x-y)}$ is generated by the convexquadratic form${\displaystyle F(x)=\frac{1}{2}{x}^{T}Qx}$. The squared Euclidean distance is the special case where${\displaystyle Q}$ is the identity, i.e. for${\displaystyle F(x)=\Vert x{\Vert }^2}$. As noted, affine differences, i.e. the lower orders added in${\displaystyle F}$, are irrelevant to${\displaystyle D_F}$.
• The generalized Kullback–Leibler divergence$${\displaystyle D_F(p,q)=\sum _{i}p(i)\log \frac{p(i)}{q(i)}-\sum _{i}p(i)+\sum _{i}q(i)}$$ is generated by the negativeentropy function$${\displaystyle F(p)=\sum _{i}p(i)\log p(i)}$$ When restricted to thesimplex, the last two terms cancel, giving the usualKullback–Leibler divergence for distributions.
• TheItakura–Saito distance,$${\displaystyle D_F(p,q)=\sum _i\left(\frac{p(i)}{q(i)}-\log \frac{p(i)}{q(i)}-1\right)}$$ is generated by the convex function$${\displaystyle F(p)=-\sum _i\log p(i)}$$

A key tool incomputational geometry is the idea ofprojective 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${\displaystyle p=(p_1,\dots p_d)}$ to the hyperplane$x_{d+1}=\sum _{i=1}^{d}2p_i{x}_i$. This mapping can be interpreted (identifying thehyperplane with its normal) as the convex conjugate mapping that takes the point p to its dual point${\displaystyle p^{\ast }=\mathrm{\nabla }F(p)}$, whereF defines thed-dimensional paraboloid$x_{d+1}=\sum _i{x}_i^2$.

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 likeVoronoi diagrams andDelaunay 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 skewedJensen 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).The Bregman chord divergence^[7] is obtained by taking a chord instead of a tangent line.

Bregman divergences can also be defined between matrices, between functions, and between measures (distributions). Bregman divergences between matrices include theStein's loss andvon 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 asubmodular set function which is known as the discrete analog of aconvex function. The submodular Bregman divergences subsume a number of discrete distance measures, like theHamming 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 thesoftmax function with noisy datasets.^[9]

Bregman divergence is used in the formulation ofmirror descent, which includes optimization algorithms used in machine learning such asgradient descent and thehedge algorithm.

• Geometric algorithms
• Statistical distance

• Articles with short description
• Short description is different from Wikidata
• Use dmy dates from August 2023