Is a Bregman divergence always a distance?

It is distance-like in some uses, but generally fails the requirements of a metric.

Can two different generators give the same divergence?

Yes. Adding an affine function to a generator cancels out in the divergence formula.

Does multiplying the generator change the divergence?

Multiplying by a positive constant scales the divergence by that constant, which can affect its balance against other objective terms.

AI Glossary / Mathematics and optimization / Advanced

Bregman divergence

Definition

A Bregman divergence measures the gap between a convex function's value at one point and its first-order linear approximation around another point. For a differentiable convex generator phi, it is D_phi(x,y)=phi(x)-phi(y)-gradient(phi)(y) dot (x-y). It generalizes useful discrepancies such as squared Euclidean distance, but is not generally a metric.

What it means

Convexity ensures that a tangent approximation does not rise above the function on its convex domain. The difference between the actual value and that approximation is therefore nonnegative.

The second argument supplies the point where the tangent is constructed, so reversing the arguments can change the answer. If the generator is strictly convex under the appropriate domain assumptions, divergence is zero only when the points coincide. For a merely convex generator, distinct points can have zero divergence. Naming the generator and argument order is essential to defining the comparison.

How it works

Choose a convex generator that is differentiable at the reference point y. Evaluate the generator at x and y, calculate its gradient at y, and subtract the first-order prediction from the actual value at x.

With phi(x)=one-half the squared Euclidean norm, the formula reduces to one-half the squared distance between x and y. With negative entropy on positive probability vectors, it gives Kullback - Leibler divergence, with appropriate conventions needed at the boundary.

Optimization methods can use a Bregman divergence to penalize movement away from a current point in geometry suited to the domain. This is central to mirror descent. Choosing a generator changes the meaning of a small step; it is not just renaming ordinary Euclidean distance.

Three practical examples

1. Optimization design: use a suitable divergence in a mirror-descent update when the variable domain has structure such as a probability simplex.

2. Distribution comparison: express a KL-based discrepancy through its negative-entropy generator while respecting support and zero-probability conditions.

3. Clustering research: define an objective using a selected Bregman discrepancy instead of assuming squared Euclidean distance is appropriate for every data representation.

Think of it this way

Imagine drawing a tangent line to a bowl-shaped curve at a reference point. At another horizontal position, measure the vertical gap between the curve and that tangent.

The analogy captures the one-dimensional formula, but the gap is not the straight-line distance between the two points. Moving the tangent's anchor changes the comparison, which helps explain why reversing arguments can produce a different result.

Worked example

Take the scalar generator phi(t)=t log t for t>0, using natural logarithms. Its derivative is log t+1. Substituting into the definition gives D(x,y)=x log(x/y)-x+y.

For x=4 and y=2, D(4,2)=4 log 2-2, approximately 0.77259. Reverse the arguments: D(2,4)=2 log(1/2)+2, approximately 0.61371. Both are positive, but they are unequal.

For comparison, choose phi(t)=t^2/2. Its divergence is (x-y)^2/2, so the same two inputs produce 2 in either order. Symmetry holds for this generator, yet the result is still not a metric: D(0,2)=2, while D(0,1)+D(1,2)=0.5+0.5=1, violating the triangle inequality.

The positive-scalar logarithmic example is a generalized divergence, not KL between normalized probability distributions by itself. The calculations show why the generator, domain, and mathematical properties must be stated separately.

Illustrative case study

Fictional case: a research team compares ways to update a vector of positive allocation weights. Its first prototype penalizes changes using squared Euclidean distance. A second uses an entropy-based geometry suited to the normalized weights.

The team derives the update rules and checks that the iterates respect the intended domain. It compares convergence and sensitivity on controlled examples rather than assuming that a more sophisticated divergence must perform better.

The final documentation records the generator and the order of arguments. This avoids a later implementation change accidentally replacing one directed discrepancy with its reverse. No measured speedup or real allocation result is claimed.

Common misconceptions and mistakes

Do not assume every divergence is symmetric or satisfies the triangle inequality. Bregman divergences generally do neither.

Convexity of the generator ensures nonnegativity, but strict convexity is needed for the usual distinct-points-positive property. A linear generator produces zero divergence everywhere on its domain.

The second argument must lie where the required gradient exists. Boundary values for entropy-based generators need explicit extensions or limiting conventions.

A Bregman divergence is convex in its first argument for fixed second argument, but is not necessarily jointly convex or convex in the second argument. Optimization claims should not assume those stronger properties without verification.

Business use

The concept helps technical teams choose objectives and optimization updates that reflect the structure of their data or parameters. It provides a common mathematical language for several familiar discrepancy measures.

For practical use, document the generator, scaling, domain restrictions, and numerical handling near boundaries. Test whether a chosen divergence reflects the intended meaning of error. A mathematically convenient discrepancy does not automatically correspond to business cost, and changing it can change both fitted solutions and the interpretation of model comparisons.

Check your understanding

Why does the logarithmic example give different values for D(4,2) and D(2,4)?

Answer: Each order uses a different tangent reference point. The definition is directed, and symmetry is not guaranteed for that generator.

Related terms

Convex function
Gradient
Mirror descent
Metric
first-order approximation
squared Euclidean distance
Kullback–Leibler divergence
negative entropy
proximal method

Learn next

Derive the quadratic and positive-scalar logarithmic formulas from the definition. Plot each generator with its tangent at two reference points and compare the gaps. Then study mirror descent to see how replacing a squared-distance penalty changes an optimization update while preserving a clear mathematical objective.

Mirror descent

Sources

Primary glossary formula checked: The Aalto Dictionary of Machine Learning, Bregman divergence: https://aaltodictionaryofml.github.io/ADictML_Main.pdf . Primary university slides read: Stanford EE364b, Mirror Descent and Variable Metric Methods: https://web.stanford.edu/class/ee364b/lectures/mirror_descent_slides.pdf . The directed scalar calculations and triangle-inequality counterexample are original and hand-checked.

Previous: Breadth First Search on Edges Next: Bregman method