Convergence of Gradient EM on Multi-component Mixture of Gaussians
In this paper, we study convergence properties of the gradient variant of Expectation-Maximization algorithm [11] for Gaussian Mixture Models for arbitrary number of clusters and mixing coefficients. We derive the convergence rate depending on the mixing coefficients, minimum and maximum pairwise distances between the true centers, dimensionality and number of components; and obtain a near-optimal local contraction radius. While there have been some recent notable works that derive local convergence rates for EM in the two symmetric mixture of Gaussians, in the more general case, the derivations need structurally different and non-trivial arguments. We use recent tools from learning theory and empirical processes to achieve our theoretical results.
Summary: This paper derives statistical guarantees for the gradient EM algorithm applied to clustering in Gaussian mixture models, generalizing the results of [1] to multiple clusters and non-uniform cluster weights.
The first result (Theorem 1) concerns the "population EM algorithm", i.e., when the expectation step can be computed exactly rather than being estimated from data. For this case, if the cluster centers are sufficiently separated and all the estimated cluster centers are initialized sufficiently close to the true cluster centers (i.e., roughly if there is already a sufficiently clear 1-1 correspondence between the estimated and true cluster centers), then the estimated cluster centers converge linearly to the true centers. This result relies on first showing (Theorem 4) that, under these conditions, due to properties of the Gaussian distribution, the curvature of the Q function is bounded (i.e., specifically, the gradient is Lipschitz). By a standard proof, the Lipschitz gradient then implies convergence of gradient descent.
The paper then turns to showing that finite-sample gradient EM approximates population EM, based on a generalization [2] of McDiarmid's inequality (to unbounded data), and a novel bound on the Rademacher complexity of the gradient for GMMs. This in turn implies a linear convergence rate for finite-sample gradient EM, assuming sufficiently good initialization.
Finally, the paper concludes with some synthetic experiments verifying the linear convergence rate and the necessity of the assumption that the initial clusters are good.
Main Comments:
This paper proves fairly strong, tight convergence bounds on a classic clustering algorithm, significantly generalizing the results of [1]. The proofs are well-motivated and lucidly sketched. I'm not too familiar with related work in this area, but I believe the results are quite novel. Overall, this paper is a significant contribution. However, the paper needs extensive proof-reading (see some of the typos noted below).
Some thoughts:
1) The results rely on having a sufficiently good initialization of the estimated cluster centers. Although haven't thought in much detail, I suspect that (perhaps assuming the clusters centers are known to lie in a bounded region), it should be quite easy to derive a high-probability bound the number of random initializations needed to obtain such an initialization. Such a result might nicely complement the given results.
2) It is noted (Remark 4) that the altered version (from [2]) of McDiarmid's inequality used results in extra factors of sqrt(d) and log(n). I wonder if the recent variant (see [R1] below) of McDiarmid's inequality for sub-Gaussian data can give tighter results? This bound appears somewhat more similar to the original (bounded-differences) version of McDiarmid's inequality, though perhaps it is equivalent to that in [2].
The paper has a lot of typos and minor language issues:
Line 18: "loglikelihood" should be "log-likelihood"
Line 26 and Line 142: "convergence guarantees... is" should be "convergence guarantees... are"
Line 27: "converge to arbitrarily" should be "converge to an arbitrarily"
Line 30: The sentence "In [16]... is continuous." doesn't parse.
Line 52: "semi definite" should be "semi-definite"
Line 69: "Ledoux Talagrand" should be "Ledoux-Talagrand"
Line 122: "defined in 1". What is "1"? Should this be the reference [1]?
Lines 139-144: It looks like part of the related work section was randomly pasted into the middle of a sentence that should read "... contraction results [9] coupled with arguments that use..."
Line 187: "equivalent as" should be "equivalent to"
Hyphenation (e.g., "sub-Gaussian", "sub-optimal") is inconsistent throughout the paper.
[R1] Kontorovich, Aryeh. "Concentration in unbounded metric spaces and algorithmic stability." Proceedings of the 31st International Conference on Machine Learning (ICML-14). 2014.