Global analysis of Expectation Maximization for mixtures of two Gaussians

Abstract

Expectation Maximization (EM) is among the most popular algorithms for estimating parameters of statistical models. However, EM, which is an iterative algorithm based on the maximum likelihood principle, is generally only guaranteed to find stationary points of the likelihood objective, and these points may be far from any maximizer. This article addresses this disconnect between the statistical principles behind EM and its algorithmic properties. Specifically, it provides a global analysis of EM for specific models in which the observations comprise an i.i.d. sample from a mixture of two Gaussians. This is achieved by (i) studying the sequence of parameters from idealized execution of EM in the infinite sample limit, and fully characterizing the limit points of the sequence in terms of the initial parameters; and then (ii) based on this convergence analysis, establishing statistical consistency (or lack thereof) for the actual sequence of parameters produced by EM.

Cited by in corpus (28)

• Universal Inference
• The Landscape of Empirical Risk for Non-convex Losses
• $k$-means as a variational EM approximation of Gaussian mixture models
• Ten Steps of EM Suffice for Mixtures of Two Gaussians
• From Symmetry to Geometry: Tractable Nonconvex Problems
• Singularity, Misspecification, and the Convergence Rate of EM
• Optimal estimation of Gaussian mixtures via denoised method of moments
• Polynomial methods in statistical inference: theory and practice
• Statistical Convergence of the EM Algorithm on Gaussian Mixture Models
• The EM Algorithm gives Sample-Optimality for Learning Mixtures of Well-Separated Gaussians
• Solving general elliptical mixture models through an approximate Wasserstein manifold
• Global Convergence of EM Algorithm for Mixtures of Two Component Linear Regression
• Mixture Models, Robustness, and Sum of Squares Proofs
• Sharp Analysis of Expectation-Maximization for Weakly Identifiable Models
• Iterative Least Trimmed Squares for Mixed Linear Regression
• On the Minimax Optimality of the EM Algorithm for Learning Two-Component Mixed Linear Regression
• Maximum likelihood for high-noise group orbit estimation and single-particle cryo-EM
• Provable Hierarchical Imitation Learning via EM
• Convergence Analysis of Gradient EM for Multi-component Gaussian Mixture
• Learning Mixture of Gaussians with Streaming Data
• Estimating the Coefficients of a Mixture of Two Linear Regressions by Expectation Maximization
• On the Behavior of the Expectation-Maximization Algorithm for Mixture Models
• Cutoff for exact recovery of Gaussian mixture models
• High-Dimensional Differentially-Private EM Algorithm: Methods and Near-Optimal Statistical Guarantees
• Quantifying and Reducing Bias in Maximum Likelihood Estimation of Structured Anomalies
• Learning Mixtures of Graphs from Epidemic Cascades
• Benefits of over-parameterization with EM
• Comparing EM with GD in Mixture Models of Two Components