Bregman Centroid Asymmetry

Bregman divergences are generalized distance-like measures generated by convex functions. Unlike standard metrics, they are generally not symmetric. This means that the left and right centroids of a dataset can be different.

Worked Example

Let's calculate the left and right optimal centroids for the Spread dataset using the Generalized KL divergence.

Data: 1, 2, 4

The Right objective minimizes the mean of D_φ(data, c). The optimal centroid is always the arithmetic mean of the data.
Arithmetic mean: (1 + 2 + 4)/3 = 7/3 ≈ 2.3333333333333335
The Left objective minimizes the mean of D_φ(c, data). The optimal centroid depends on the divergence. For Generalized KL, it is the geometric mean.
Geometric mean: (1 · 2 · 4)^(1/3) = 8^(1/3) = 2.0

Experiment

Explore how different divergences affect the left centroid.

Open the module at Bregman Centroid Asymmetry.
Set Data to "Spread".
Set Divergence to "Generalized KL". Observe the Left dual centroid is 2.0.
Change Divergence to "Squared". Observe that the Left dual centroid is now equal to the right arithmetic centroid, 2.3333333333333335, since squared distance is symmetric.
Change Divergence to "Itakura Saito". Observe the Left dual centroid becomes 1.7142857142857142, which is the harmonic mean.

Limitations

Bregman divergences like Generalized KL and Itakura Saito require positive scalar data to avoid logarithms of zero or negative numbers. Equal data points lead to zero optimal divergence, where only analytic zero roundoff may normalize below 1e-14.

References

Banerjee, A., Merugu, S., Dhillon, I. S., & Ghosh, J. (2005). Clustering with Bregman Divergences. See https://arxiv.org/abs/0711.3242. This paper supports the properties of right and left centroids under different Bregman divergences.

Bregman Centroid Asymmetry