# Statistical guarantees for the EM algorithm: From population to sample-based analysis

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

## Key facts

- Cited by 133 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Aug 2014.

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

- [Learning Diffusion Priors from Observations by Expectation Maximization](https://mlsanity.com/paper/2405.13712/) (2024)
- [Learning Mixtures of Gaussians Using the DDPM Objective](https://mlsanity.com/paper/2307.01178/) (2023)
- [Towards Understanding Mixture of Experts in Deep Learning](https://mlsanity.com/paper/2208.02813/) (2022)
- [Demystifying Softmax Gating Function in Gaussian Mixture of Experts](https://mlsanity.com/paper/2305.03288/) (2023)
- [On the computational and statistical complexity of over-parameterized matrix sensing](https://mlsanity.com/paper/2102.02756/) (2021)
- [Statistical Perspective of Top-K Sparse Softmax Gating Mixture of Experts](https://mlsanity.com/paper/2309.13850/) (2023)
- [Refined Convergence Rates for Maximum Likelihood Estimation under Finite Mixture Models](https://mlsanity.com/paper/2202.08786/) (2022)
- [Selective inference for k-means clustering](https://mlsanity.com/paper/2203.15267/) (2022)
- [Sublinear Regret for Learning POMDPs](https://mlsanity.com/paper/2107.03635/) (2021)
- [Mean-field Variational Inference via Wasserstein Gradient Flow](https://mlsanity.com/paper/2207.08074/) (2022)
- [Breaking the gridlock in Mixture-of-Experts: Consistent and Efficient Algorithms](https://mlsanity.com/paper/1802.07417/) (2018)
- [Error bounds for particle gradient descent, and extensions of the log-Sobolev and Talagrand inequalities](https://mlsanity.com/paper/2403.02004/) (2024)
- [Improved Convergence Guarantees for Learning Gaussian Mixture Models by EM and Gradient EM](https://mlsanity.com/paper/2101.00575/) (2021)
- [Learning Personalized Models with Clustered System Identification](https://mlsanity.com/paper/2304.01395/) (2023)
- [Tuning-Free Maximum Likelihood Training of Latent Variable Models via Coin Betting](https://mlsanity.com/paper/2305.14916/) (2023)
- [Provable Hierarchical Imitation Learning via EM](https://mlsanity.com/paper/2010.03133/) (2020)
- [On Learning Mixture of Linear Regressions in the Non-Realizable Setting](https://mlsanity.com/paper/2205.13166/) (2022)
- [The computational asymptotics of Gaussian variational inference and the Laplace approximation](https://mlsanity.com/paper/2104.05886/) (2021)
- [Model Selection for Generic Contextual Bandits](https://mlsanity.com/paper/2107.03455/) (2021)
- [Prediction Sets for High-Dimensional Mixture of Experts Models](https://mlsanity.com/paper/2210.16710/) (2022)
- [A Wasserstein Minimax Framework for Mixed Linear Regression](https://mlsanity.com/paper/2106.07537/) (2021)
- [Off-policy Evaluation in Doubly Inhomogeneous Environments](https://mlsanity.com/paper/2306.08719/) (2023)
- [Towards the Theory of Unsupervised Federated Learning: Non-asymptotic Analysis of Federated EM Algorithms](https://mlsanity.com/paper/2310.15330/) (2023)
- [Low-Tubal-Rank Tensor Recovery via Factorized Gradient Descent](https://mlsanity.com/paper/2401.11940/) (2024)
- [The EM Algorithm is Adaptively-Optimal for Unbalanced Symmetric Gaussian Mixtures](https://mlsanity.com/paper/2103.15653/) (2021)
- [Optimal Estimation and Computational Limit of Low-rank Gaussian Mixtures](https://mlsanity.com/paper/2201.09040/) (2022)
- [FOCUS: Fairness via Agent-Awareness for Federated Learning on Heterogeneous Data](https://mlsanity.com/paper/2207.10265/) (2022)
- [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)
- [When and How Unlabeled Data Provably Improve In-Context Learning](https://mlsanity.com/paper/2506.15329/) (2025)

## Abstract (arXiv)

We develop a general framework for proving rigorous guarantees on the performance of the EM algorithm and a variant known as gradient EM. Our analysis is divided into two parts: a treatment of these algorithms at the population level (in the limit of infinite data), followed by results that apply to updates based on a finite set of samples. First, we characterize the domain of attraction of any global maximizer of the population likelihood. This characterization is based on a novel view of the EM updates as a perturbed form of likelihood ascent, or in parallel, of the gradient EM updates as a perturbed form of standard gradient ascent. Leveraging this characterization, we then provide non-asymptotic guarantees on the EM and gradient EM algorithms when applied to a finite set of samples. We develop consequences of our general theory for three canonical examples of incomplete-data problems: mixture of Gaussians, mixture of regressions, and linear regression with covariates missing completely at random. In each case, our theory guarantees that with a suitable initialization, a relatively small number of EM (or gradient EM) steps will yield (with high probability) an estimate that is within statistical error of the MLE. We provide simulations to confirm this theoretically predicted behavior.