Local Maxima in the Likelihood of Gaussian Mixture Models: Structural Results and Algorithmic Consequences

Abstract

We provide two fundamental results on the population (infinite-sample) likelihood function of Gaussian mixture models with $M\ge 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^{-\Omega (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.

arXiv commentNeural Information Processing Systems (NIPS) 2016

References in corpus (7)

• Regularized M-estimators with nonconvexity: Statistical and algorithmic theory for local optima
• Polynomial Learning of Distribution Families
• Gradient Descent Converges to Minimizers
• Learning mixtures of separated nonspherical Gaussians
• On the saddle point problem for non-convex optimization
• Gradient Descent Only Converges to Minimizers: Non-Isolated Critical Points and Invariant Regions
• Identifiability and optimal rates of convergence for parameters of multiple types in finite mixtures

Cited by in corpus (24)

• Universal Inference
• Sampling Can Be Faster Than Optimization
• From Symmetry to Geometry: Tractable Nonconvex Problems
• Scalable Nonparametric Sampling from Multimodal Posteriors with the Posterior Bootstrap
• The Limit Points of (Optimistic) Gradient Descent in Min-Max Optimization
• Statistical Convergence of the EM Algorithm on Gaussian Mixture Models
• Improved Deep Spectral Convolution Network For Hyperspectral Unmixing With Multinomial Mixture Kernel and Endmember Uncertainty
• The EM Algorithm gives Sample-Optimality for Learning Mixtures of Well-Separated Gaussians
• Optimal Subspace Estimation Using Overidentifying Vectors via Generalized Method of Moments
• Maximum likelihood estimation of determinantal point processes
• Global Convergence of EM Algorithm for Mixtures of Two Component Linear Regression
• Solving general elliptical mixture models through an approximate Wasserstein manifold
• Iterative Least Trimmed Squares for Mixed Linear Regression
• A universal framework for learning the elliptical mixture model
• MAP Clustering under the Gaussian Mixture Model via Mixed Integer Nonlinear Optimization
• On the Behavior of the Expectation-Maximization Algorithm for Mixture Models
• Convergence Analysis of Gradient EM for Multi-component Gaussian Mixture
• Breaking the gridlock in Mixture-of-Experts: Consistent and Efficient Algorithms
• Statistical Inference with Local Optima
• Benefits of over-parameterization with EM
• Quantum State Tomography as a Bilevel Problem, Utilizing I-Q Plane Data
• Deep Generative Variational Autoencoding for Replay Spoof Detection in Automatic Speaker Verification
• Comparing EM with GD in Mixture Models of Two Components
• Information Theoretic Structured Generative Modeling