Jorge Quitério Search
Mathematics

Bregman divergences and the mean as optimal summary

Squared error, the Kullback-Leibler divergence and the Itakura-Saito distance appear unrelated, but all are Bregman divergences, and for every one of them the optimal single summary of the data is the mean. An interactive figure illustrates the result.

Squared error, the Kullback-Leibler divergence and a distance used to compare speech spectra appear to be unrelated tools. They are closely related. All three are Bregman divergences, and they share a notable property: for every one of them, the best single number to summarise a dataset is the plain arithmetic mean.

An earlier note compared the Kullback-Leibler divergence with the Hellinger distance. Both belong to the family of f-divergences. Kullback-Leibler also belongs to this second family, with practical consequences for clustering, regression and the choice of loss function. This note explains the family, proves the property, and illustrates it with an interactive example.

The relevant literature is as follows.

  • Bregman (1967) introduced the construction for an algorithm in convex optimisation.
  • Banerjee, Merugu, Dhillon and Ghosh (2005) proved that the mean minimises the expected Bregman divergence for every convex generator, generalised kk-means to all Bregman divergences, and established a one-to-one correspondence between regular exponential families and regular Bregman divergences.
  • Banerjee, Guo and Wang (2005) proved the converse: under mild conditions, Bregman divergences are the only losses for which the conditional expectation is the optimal predictor.
  • Dhillon (2007) gave a widely used tutorial on learning with Bregman divergences.

The definition

Take a strictly convex, differentiable function ϕ\phi. The Bregman divergence it generates is the gap between ϕ\phi and its tangent:

Dϕ(x,y)=ϕ(x)−ϕ(y)−⟨∇ϕ(y), x−y⟩. D_\phi(x, y) = \phi(x) - \phi(y) - \langle \nabla\phi(y),\, x - y \rangle .

Geometrically, it is the height of ϕ(x)\phi(x) above the tangent to ϕ\phi at yy. Because ϕ\phi is convex, the gap is never negative, and it is zero only when x=yx = y. Bregman introduced the construction in 1967 for an algorithm in convex optimisation; it has since spread through statistics, signal processing and machine learning.

Familiar members

Different choices of ϕ\phi give divergences that look unrelated:

ϕ(x)\phi(x) Dϕ(x,y)D_\phi(x, y) Name
x2x^2 (x−y)2(x - y)^2 squared error
x⊤Axx^\top A x (x−y)⊤A(x−y)(x-y)^\top A (x-y) squared Mahalanobis distance
xlog⁡xx \log x xlog⁡xy−x+yx \log\frac{x}{y} - x + y generalised Kullback-Leibler (I-divergence)
−log⁡x-\log x xy−log⁡xy−1\frac{x}{y} - \log\frac{x}{y} - 1 Itakura-Saito

Summed over the coordinates of two probability vectors, the third line is exactly the Kullback-Leibler divergence. The Itakura-Saito distance is a standard way to compare power spectra in speech processing.

Bregman divergences are generally not symmetric and do not satisfy the triangle inequality, so they are not distances in the strict sense. They do, however, have an important property concerning averages.

The mean as minimiser

Suppose a set of observations x1,…,xnx_1, \dots, x_n is summarised by a single value ss, chosen to minimise the average divergence 1n∑iDϕ(xi,s)\frac{1}{n}\sum_i D_\phi(x_i, s). For squared error, the answer is the sample mean; this is the familiar least-squares result. Banerjee, Merugu, Dhillon and Ghosh showed in 2005 that the same holds for every Bregman divergence: the minimiser is always the mean, whatever ϕ\phi is. And Banerjee, Guo and Wang proved the converse in the same year: under mild conditions, Bregman divergences are the only loss functions for which the mean, or more generally the conditional expectation, is the optimal predictor.

A four-number example makes this concrete. For the data 1, 2, 4 and 9, minimising the average squared error, I-divergence or Itakura-Saito distance gives 4.0 in every case, the arithmetic mean. Minimising the average absolute error, which is not a Bregman divergence, gives any value between 2 and 4 (the medians). Reversing the arguments of the I-divergence, which takes it out of the theorem's form, gives 2.91, the geometric mean.

The choice of loss therefore decides what a forecast aims at. A retailer forecasting tomorrow's sales of each product can score its forecasts by squared error or by the Poisson deviance, which is twice the I-divergence; both make the mean of tomorrow's sales the target. Scoring by absolute error makes the median the target instead. For a product that sells nothing on most days and twenty units on an occasional day, the mean may be 2 while the median is 0, and a forecast of 0 is of no use for stocking the shelf.

Implications

Clustering. The kk-means algorithm, widely used to group customers by their purchasing behaviour, alternates between assigning points to the nearest centre and moving each centre to the mean of its points. The second step is optimal only because squared error is a Bregman divergence. The theorem therefore lets kk-means run with any Bregman divergence, with exactly the same update, and Banerjee and colleagues used this to build a family of clustering algorithms. Clustering word-count vectors with the Kullback-Leibler divergence, for example, is kk-means with a different ϕ\phi.

Exponential families. The same paper establishes a correspondence between regular exponential families and regular Bregman divergences. The normal goes with squared error, the Poisson with the I-divergence, the exponential and gamma with Itakura-Saito. Maximising a likelihood in an exponential family is equivalent to minimising the matching divergence, which explains why least squares is appropriate for normal errors and another divergence is appropriate for counts or positive scale data.

Choosing a loss. The correspondence also works as a guide in reverse. If the data are counts or positive quantities whose variance grows with the mean, squared error corresponds to an inappropriate family, and a Bregman divergence matched to the data's variance structure is a principled alternative that keeps the mean as the target.

The figure below illustrates the result. For every Bregman divergence the summary that minimises the average divergence is the arithmetic mean, while losses outside the family land elsewhere: absolute error at the median, the reversed I-divergence at the geometric mean.

The top strip holds the data; the curve is the average divergence for each candidate summary ss, and the marker shows its minimum.

Suggested settings:

  1. Three divergences. With the data 1, 2, 4 and 9, switch between squared error, I-divergence and Itakura-Saito. The curves have very different shapes, steep on one side and shallow on the other, yet each bottoms out at exactly 4.00, the mean.
  2. Losses outside the family. Choose absolute error. The curve is flat at its bottom: any value from 2 to 4 is optimal, the whole median interval. Choose the reversed I-divergence: the minimum moves to 2.91, the geometric mean.
  3. Outlier. With squared error, drag the 9 out to 10 and back down to 5. The minimum follows the mean exactly. Switch to absolute error and repeat: the median does not change.
  4. Random data. Press "New random data" and cycle through the Bregman divergences. The minimiser always matches the "arithmetic mean" readout.

Proof. For data x1,…,xnx_1, \dots, x_n with mean xˉ\bar x and any candidate ss,

1n∑iDϕ(xi,s)−1n∑iDϕ(xi,xˉ)=ϕ(xˉ)−ϕ(s)−ϕ′(s)(xˉ−s)=Dϕ(xˉ,s)  ≥  0. \frac1n \sum_i D_\phi(x_i, s) - \frac1n \sum_i D_\phi(x_i, \bar x) = \phi(\bar x) - \phi(s) - \phi'(s)(\bar x - s) = D_\phi(\bar x, s) \;\ge\; 0 .

To see the first equality, expand both averages: the terms 1n∑ϕ(xi)\frac1n\sum \phi(x_i) cancel, and 1n∑(xi−xˉ)=0\frac1n\sum (x_i - \bar x) = 0 removes the tangent term of the second average, leaving exactly the expression shown. Since Dϕ(xˉ,s)≥0D_\phi(\bar x, s) \ge 0, with equality only at s=xˉs = \bar x, the mean is the unique minimiser, whatever the convex ϕ\phi. The reversed I-divergence, D(s,xi)D(s, x_i) instead of D(xi,s)D(x_i, s), swaps the roles of the arguments, so the argument above no longer applies; differentiating its average gives ln⁡s=1n∑ln⁡xi\ln s = \frac1n\sum \ln x_i, the geometric mean.

Summary:

  • The mean is the optimal summary for squared error and for every other Bregman divergence, which is why kk-means works unchanged with any of them.
  • Each regular exponential family has its matching Bregman divergence; minimising it is maximising the likelihood. Choose the loss to match the variance structure of the data.
  • Heavy-tailed families such as Student's tt, or the γ-order generalized normal away from its normal member, are not exponential families with the location as natural parameter, and their maximum-likelihood location estimates are not the sample mean. That is part of why they are used: under heavy tails the mean is a poor summary, and the loss that fits the data falls outside the Bregman class. It is useful to know where the theorem ceases to apply.

References

  1. L. M. Bregman, "The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming", USSR Computational Mathematics and Mathematical Physics, 7(3), 200-217, 1967.
  2. A. Banerjee, S. Merugu, I. S. Dhillon and J. Ghosh, "Clustering with Bregman divergences", Journal of Machine Learning Research, 6, 1705-1749, 2005.
  3. A. Banerjee, X. Guo and H. Wang, "On the optimality of conditional expectation as a Bregman predictor", IEEE Transactions on Information Theory, 51(7), 2664-2669, 2005.
  4. I. S. Dhillon, "Learning with Bregman divergences: machine learning and optimization", tutorial, Banff International Research Station, 2007.