Clustering with Bregman Divergences: an Asymptotic Analysis
Clustering, in particular k-means clustering, is a central topic in data analysis. Clustering with Bregman divergences is a recently proposed generalization of k-means clustering which has already been widely used in applications. In this paper we analyze theoretical properties of Bregman clustering when the number of the clusters k is large. We establish quantization rates and describe the limiting distribution of the centers as k → ∞, extending well-known results for k-means clustering.
This paper present an asymptotic result for optimal k-means clustering, when there is infinite data and as the number of clusters goes to infinity. Essentially, if we process (15), the limiting distribution is proportional to the eigenvalues of the Hessian of the generator of the divergence.
There are several points that need clarification, from the most important to the less important one:  * One key missing point is the reason to exist of the k^{2r/d} factor which appears in (14). The only motivation is intuition, but I do not get it at all. It must be introduced rigorously.   * In (47) of the supplementary information, the authors claim that the difference between eigenvalues (max - min) of the Hessian is slammer then epsilon. If I am not mistaken, epsilon in (45), epsilon can be chosen arbitrarily small. If this is the case, then (47) is wrong, even for Mahalanobis, since is enforces the Hessian to be essentially spherical. Or if it is right, then the result cannot hold for any Bregman divergence, as claimed by the authors. This is important, because if there is a mistake, this invalidates (50) (supplement), and therefore Lemma 2, which is central to the paper.  * In page 7, the authors claim “In addition, we only verify r = 1 cases here, since  the Bregman clustering algorithm, which utilizes Lloyd’s method, cannot address Bregman quantization problems with r != 1”. This, I suspect, is wrong, or the authors need to make it formal. Bregman divergences are exhaustive for the population minimiser as an average (right population minimiser) or f-mean (left population minimiser). Generalisations of Bregman divergences exist that allow to satisfy additional properties that Bregman divergences would not satisfy, such as population minimisers that are invariant to rotations of the coordinate axes [1] (and references therein). It turns out that in this case, even when there is no equivalent Bregman divergence, Lloyd’s quantisation can still be used (see for example the optimisation of the left population minimiser in Total Bregmen divergences) !  Two suggestions, in decreasing order of importance:  * I strongly encourage the authors to pursue drilling down Lemma 3 and one if its implication that I can see, in the finite sample / finite k regime: there seems to be a seeding mechanism in the distribution defined in (20), and I wonder whether this seeding distribution would be better than the state of the art in this field, which is basically the infamous k-means++ algorithm [2] and its extensions to various Bregman divergences and Beyond [1,3].  * Additional remark: the “Remark” before Section 4 follows the well known fact that f-means associated to the KL and IS divergences are zero-attracting. I suggest the authors also put this in context with the paper’s results: there must be a link between the properties of the f-mean associated to the divergence and the limit distribution of centroids (Section 3.2).  Typos:  Pg 11 supplement: existance -> existence  Ref [2] is incomplete  Additional reference:  [1] Richard Nock, Frank Nielsen, Shun-ichi Amari: On Conformal Divergences and Their Population Minimizers. IEEE Trans. Information Theory 62(1): 527-538 (2016)  [2] David Arthur, Sergei Vassilvitskii: k-means++: the advantages of careful seeding. SODA 2007: 1027-1035  [3] Richard Nock, Raphaël Canyasse, Roksana Boreli, Frank Nielsen: k-variates++: more pluses in the k-means++. ICML 2016: 145-154