Measure of difference between two points, defined in terms of a strictly [[Convexity|convex function]], they form an important class of [[Divergence|divergences]]. When the points are interpreted as [[Probability Distribution|probability distributions]] – notably as either values of the parameter of a [parametric model](https://en.wikipedia.org/wiki/Parametric_model "Parametric model") or as a data set of observed values – the resulting distance is a [statistical distance](https://en.wikipedia.org/wiki/Statistical_distance "Statistical distance"). The most basic Bregman divergence is the [squared Euclidean distance](https://en.wikipedia.org/wiki/Squared_Euclidean_distance "Squared Euclidean distance"). Bregman divergences are similar to [metrics](https://en.wikipedia.org/wiki/Metric_(mathematics) "Metric (mathematics)"), but satisfy neither the [triangle inequality](https://en.wikipedia.org/wiki/Triangle_inequality "Triangle inequality") (ever) nor symmetry (in general). However, they satisfy a generalization of the [Pythagorean theorem](https://en.wikipedia.org/wiki/Pythagorean_theorem "Pythagorean theorem"). ### Definition Let $\phi \colon \Omega \rightarrow \mathbb{R}$ be a continuously-differentiable, strictly [[Convexity|convex]] function defined on a [[Convexity|convex set]] $\Omega$. The Bregman distance associated with the function $\phi$ for points $p,y \in \Omega$ is the difference between the value of $\phi$ at point $p$ and the value of the first-order [Taylor expansion](https://en.wikipedia.org/wiki/Taylor_expansion) of $\phi$ around point $q$ evaluated at point $p$: $B_{\phi}(p,q)=\phi(p)-\phi(q) -\langle \nabla \phi(q),p-q\rangle$ - **Properties** - Non-negative - Not commutative - [[Convexity|Convex]] in first argument, not necessarily in second - Linearity --- ### Examples - For $\phi(\mathbf{x})=\frac{1}{2}||\mathbf{x}||^{2}$ the associated divergence is $B_{\phi}(\mathbf{x },\mathbf{y})=\frac{1}{2}||\mathbf{y}-\mathbf{x}||^{2}$ - For the negative [[Shannon Entropy|entropy]]-function $\phi=\sum\limits_{i}x_{i} \ln ( x_{i})-\sum\limits_{i}x_{i}$, the associated divergence is the (generalized) [[Kullback-Leibler Divergence|KL-Divergence]]$B_{\phi}(\mathbf{x,y})=\sum\limits_{i=1}^{n}x_{i}\log(\frac{x_{i}}{y_{i}})-\sum\limits_{i=1}^{n}x_{i}+\sum\limits_{i=1}^{n}y_{i}.$ --- ### Bregman Projection Bregman projection of $\mathbf{y}$ onto set $\mathcal{X}$ under function $\phi$ defined as $P_{\mathcal{X},\phi}(\mathbf{y})=\arg \min_{\mathbf{x} \in \mathcal{X}}B_{\phi}(\mathbf{x,y})$ - In contrast to euclidean geometry, bregman uses general curved geometry![[Pasted image 20230603121713.png|center|300]]