Local Maxima in the Likelihood of Gaussian Mixture Models: Structural Results and Algorithmic Consequences
We provide two fundamental results on the population (infinite-sample) likelihood function of Gaussian mixture models with M ≥ 3 components. Our first main result shows that the population likelihood function has bad local maxima even in the special case of equally-weighted mixtures of well-separated and spherical Gaussians. We prove that the log-likelihood value of these bad local maxima can be arbitrarily worse than that of any global optimum, thereby resolving an open question of Srebro [2007]. Our second main result shows that the EM algorithm (or a first-order variant of it) with random initialization will converge to bad critical points with probability at least 1 − e −Ω(M ) . We further establish that a first-order variant of EM will not converge to strict saddle points almost surely, indicating that the poor performance of the first-order method can be attributed to the existence of bad local maxima rather than bad saddle points. Overall, our results highlight the necessity of careful initialization when using the EM algorithm in practice, even when applied in highly favorable settings.
The paper is concerned with the existence of local modes in the log-likelihood of Gaussian mixture models. The simplest possible mixture model is considered: isotropic Gaussian components with known scale. In addition the model is well-specified. The authors show that local modes exist, even when infinite data is available, and that these are arbitrarily bad, in term of differences in log-likelihood between the local and global optima. The paper focuses on particular configurations, in particular cases where the mixture centres are divided between well-spaced clusters. Under such configurations, the authors show that random initialization will make so that EM misses the global optima almost certainly, as the number of components increases.
The paper is well written, with occasional typos. I have two main doubts about the practical relevance of the paper.  1. Theorem 1 shows that the log-likelihood has a local modes, even when infinite data is available. The authors show that this mode exists when a particular configuration of the centres is chosen. My question is: how likely is this configuration to occur in practice? I would feel more confident about the practical relevance of the paper if, for instance, the authors made some assumptions about the distribution of the centres, and then showed that "bad" configurations become increasingly likely as the number of components (k) or the dimensionality of the problem increases. L210 to L218 of the paper say that Theorem 2 addresses these concerns, but I am not sure it does. It would be good to have a clear statement say how likely "bad" configurations are, under some assumptions. Notice that here I am talking about "bad" configurations (positions of the true centres), not "bad" initializations.  2. In theorem 2 the initialization of the EM algorithm comes to play.     The authors consider initializing the centres of the components by randomly sampling the mixture. With this initialization, and under specific configurations of the centres, the EM very often fails to converge to the global optimum. Now, let us consider the case where the data is generated using 3 Gaussian, 2 of which are close and one far apart. If we have the same number N of data-points from each Gaussian, then 2N points will fall close to the first cluster and N will fall close to the 3rd density. It seems to me that very odd that somebody could initialize EM by putting 2 centers where there are only N points and 1 center where there are N observations, especially given that the two clusters are very well separated from each other. Is random initialization practically relevant when the data is clearly clustered?   L74-81 I am not sure what the example on lines 74-81 is meant to convey. It does not convince me that Sresbro conjecture holds when k = 2, so what is its purpose?  L233-235 I understand requirement (2) here, but I don't see why requirement (1) is needed. You mean that, if you initialize a center between 2 clusters, you cannot guarantee that it will move toward the correct cluster?  L267-273 The authors prove that EM is unlikely to converge to a saddlepoint. From a practical point of view, why is this result important? Is converging to a saddlepoint more or less problematic than converging to a local optima?  MINOR POINTS:  L18 "We further show gradient EM algorithm" add "that the" before "gradient".  L38 "quality of the estimate" maybe "estimates" is better.  L60 "to characterize when it is that efficient algorithms..." I guess here you really mean "to characterize under which conditions efficient algorithms..."  L138 Just to be clear: O(d^1/2)-separated mean that all densities are c-separated, with c being O(d^1/2).  L172 Isn't this sentence redundant? Please reformulate it or remove it.  L177 "this is equivalent of sampling " maybe "equivalent to" is better.  L218 I don't understand what a "well-separated" constant is.  L220 " initialized by the the random initialization"  L225 I don't know what \Omega (k) means.  L245 "unfortunate coincident for one single algorithm" used "coincidence" instead.  L249 "Recall for uniform weighted" add "that" after "recall"  L308 "And claim when" add "that" after "claim"