Statistical Convergence of the EM Algorithm on Gaussian Mixture Models

Abstract

We study the convergence behavior of the Expectation Maximization (EM) algorithm on Gaussian mixture models with an arbitrary number of mixture components and mixing weights. We show that as long as the means of the components are separated by at least $\Omega (\sqrt{\min \{M,d\}})$, where $M$ is the number of components and $d$ is the dimension, the EM algorithm converges locally to the global optimum of the log-likelihood. Further, we show that the convergence rate is linear and characterize the size of the basin of attraction to the global optimum.

References in corpus (8)

• Polynomial Learning of Distribution Families
• Learning mixtures of separated nonspherical Gaussians
• Statistical and Computational Guarantees of Lloyd's Algorithm and its Variants
• The Landscape of Empirical Risk for Non-convex Losses
• Settling the Polynomial Learnability of Mixtures of Gaussians
• Global analysis of Expectation Maximization for mixtures of two Gaussians
• Local Maxima in the Likelihood of Gaussian Mixture Models: Structural Results and Algorithmic Consequences
• Statistical Guarantees for Estimating the Centers of a Two-component Gaussian Mixture by EM

Cited by in corpus (2)

• The EM Algorithm gives Sample-Optimality for Learning Mixtures of Well-Separated Gaussians
• The EM Algorithm is Adaptively-Optimal for Unbalanced Symmetric Gaussian Mixtures