# Ten Steps of EM Suffice for Mixtures of Two Gaussians

arXiv: https://arxiv.org/abs/1609.00368 · HTML: https://mlsanity.com/paper/1609.00368/

## Key facts

- Cited by 40 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Sep 2016.

## Built on by (most cited first, 30 of 40)

- [Learning Mixtures of Gaussians Using the DDPM Objective](https://mlsanity.com/paper/2307.01178/) (2023)
- [Clustering Mixtures with Almost Optimal Separation in Polynomial Time](https://mlsanity.com/paper/2112.00706/) (2021)
- [Breaking the gridlock in Mixture-of-Experts: Consistent and Efficient Algorithms](https://mlsanity.com/paper/1802.07417/) (2018)
- [Improved Convergence Guarantees for Learning Gaussian Mixture Models by EM and Gradient EM](https://mlsanity.com/paper/2101.00575/) (2021)
- [Provable Hierarchical Imitation Learning via EM](https://mlsanity.com/paper/2010.03133/) (2020)
- [The EM Algorithm is Adaptively-Optimal for Unbalanced Symmetric Gaussian Mixtures](https://mlsanity.com/paper/2103.15653/) (2021)
- [Fit Like You Sample: Sample-Efficient Generalized Score Matching from Fast Mixing Diffusions](https://mlsanity.com/paper/2306.09332/) (2023)
- [Toward Global Convergence of Gradient EM for Over-Parameterized Gaussian Mixture Models](https://mlsanity.com/paper/2407.00490/) (2024)
- [PAGE: Prototype-Based Model-Level Explanations for Graph Neural Networks](https://mlsanity.com/paper/2210.17159/) (2022)
- [Can semi-supervised learning use all the data effectively? A lower bound perspective](https://mlsanity.com/paper/2311.18557/) (2023)
- [Lower Bounds on the Total Variation Distance Between Mixtures of Two Gaussians](https://mlsanity.com/paper/2109.01064/) (2021)
- [Imbalanced Mixed Linear Regression](https://mlsanity.com/paper/2301.12559/) (2023)
- [Nonparametric MLE for Gaussian Location Mixtures: Certified Computation and Generic Behavior](https://mlsanity.com/paper/2503.20193/) (2025)
- [Convergence Dynamics of Over-Parameterized Score Matching for a Single Gaussian](https://mlsanity.com/paper/2511.22069/) (2025)
- [High-Dimensional Differentially-Private EM Algorithm: Methods and Near-Optimal Statistical Guarantees](https://mlsanity.com/paper/2104.00245/) (2021)
- [A Geometric Approach to k-means](https://mlsanity.com/paper/2201.04822/) (2022)
- [Beyond EM Algorithm on Over-specified Two-Component Location-Scale Gaussian Mixtures](https://mlsanity.com/paper/2205.11078/) (2022)
- [EM's Convergence in Gaussian Latent Tree Models](https://mlsanity.com/paper/2211.11904/) (2022)
- [Sharp-SSL: Selective high-dimensional axis-aligned random projections for semi-supervised learning](https://mlsanity.com/paper/2304.09154/) (2023)
- [Learning Mixtures of Gaussians with Censored Data](https://mlsanity.com/paper/2305.04127/) (2023)
- [Big Learning Expectation Maximization](https://mlsanity.com/paper/2312.11926/) (2023)
- [On the Optimization Landscape of Maximum Mean Discrepancy](https://mlsanity.com/paper/2110.13452/) (2021)
- [An Exponentially Increasing Step-size for Parameter Estimation in Statistical Models](https://mlsanity.com/paper/2205.07999/) (2022)
- [Differentiable Outlier Detection Enable Robust Deep Multimodal Analysis](https://mlsanity.com/paper/2302.05608/) (2023)
- [Sharp analysis of EM for learning mixtures of pairwise differences](https://mlsanity.com/paper/2302.10066/) (2023)
- [EM for Mixture of Linear Regression with Clustered Data](https://mlsanity.com/paper/2308.11518/) (2023)
- [Joint Problems in Learning Multiple Dynamical Systems](https://mlsanity.com/paper/2311.02181/) (2023)
- [Global Convergence of Online Identification for Mixed Linear Regression](https://mlsanity.com/paper/2311.18506/) (2023)
- [Factor Adjusted Spectral Clustering for Mixture Models](https://mlsanity.com/paper/2408.12564/) (2024)
- [In-context Learning for Mixture of Linear Regressions: Existence, Generalization and Training Dynamics](https://mlsanity.com/paper/2410.14183/) (2024)

## Abstract (arXiv)

The Expectation-Maximization (EM) algorithm is a widely used method for maximum likelihood estimation in models with latent variables. For estimating mixtures of Gaussians, its iteration can be viewed as a soft version of the k-means clustering algorithm. Despite its wide use and applications, there are essentially no known convergence guarantees for this method. We provide global convergence guarantees for mixtures of two Gaussians with known covariance matrices. We show that the population version of EM, where the algorithm is given access to infinitely many samples from the mixture, converges geometrically to the correct mean vectors, and provide simple, closed-form expressions for the convergence rate. As a simple illustration, we show that, in one dimension, ten steps of the EM algorithm initialized at infinity result in less than 1% error estimation of the means. In the finite sample regime, we show that, under a random initialization, tildeO(d/ε2) samples suffice to compute the unknown vectors to within ε in Mahalanobis distance, where d is the dimension. In particular, the error rate of the EM based estimator is tildeOleft(√d over nright) where n is the number of samples, which is optimal up to logarithmic factors.