mlsanityData to 7 Oct 2026

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

arXiv 1408.2156 ↗First posted 9 Aug 2014math.ST cs.LG stat.MLcited by 131

Not on the map. Why?

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.

Key facts. Cited by 131 papers in the map (data through 7 Oct 2026). First posted on arXiv 9 Aug 2014.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2018: 1; 2019: 0; 2020: 1; 2021: 21; 2022: 31; 2023: 25; 2024: 20; 2025: 18; 2026: 14.

131 papers.

Sort:

By area:

  1. 2024Learning Diffusion Priors from Observations by Expectation Maximizationcited by 60
  2. 2023Learning Mixtures of Gaussians Using the DDPM Objectivecited by 56
  3. 2022Towards Understanding Mixture of Experts in Deep Learningcited by 52
  4. 2023Demystifying Softmax Gating Function in Gaussian Mixture of Expertscited by 33
  5. 2021On the computational and statistical complexity of over-parameterized matrix sensingcited by 31
  6. 2023Statistical Perspective of Top-K Sparse Softmax Gating Mixture of Expertscited by 28
  7. 2022Refined Convergence Rates for Maximum Likelihood Estimation under Finite Mixture Modelscited by 22
  8. 2022Selective inference for k-means clusteringcited by 21
  9. 2021Sublinear Regret for Learning POMDPscited by 19
  10. 2022Mean-field Variational Inference via Wasserstein Gradient Flowcited by 19
  11. 2018Breaking the gridlock in Mixture-of-Experts: Consistent and Efficient Algorithmscited by 13
  12. 2024Error bounds for particle gradient descent, and extensions of the log-Sobolev and Talagrand inequalitiescited by 13
38 more
  1. 2021Improved Convergence Guarantees for Learning Gaussian Mixture Models by EM and Gradient EMcited by 11
  2. 2023Tuning-Free Maximum Likelihood Training of Latent Variable Models via Coin Bettingcited by 11
  3. 2020Provable Hierarchical Imitation Learning via EMcited by 10
  4. 2022On Learning Mixture of Linear Regressions in the Non-Realizable Settingcited by 10
  5. 2023Learning Personalized Models with Clustered System Identificationcited by 10
  6. 2021The computational asymptotics of Gaussian variational inference and the Laplace approximationcited by 8
  7. 2022Prediction Sets for High-Dimensional Mixture of Experts Modelscited by 8
  8. 2021A Wasserstein Minimax Framework for Mixed Linear Regressioncited by 7
  9. 2021Model Selection for Generic Contextual Banditscited by 7
  10. 2023Off-policy Evaluation in Doubly Inhomogeneous Environmentscited by 7
  11. 2023Towards the Theory of Unsupervised Federated Learning: Non-asymptotic Analysis of Federated EM Algorithmscited by 7
  12. 2024Low-Tubal-Rank Tensor Recovery via Factorized Gradient Descentcited by 7
  13. 2021The EM Algorithm is Adaptively-Optimal for Unbalanced Symmetric Gaussian Mixturescited by 6
  14. 2022Optimal Estimation and Computational Limit of Low-rank Gaussian Mixturescited by 6
  15. 2022FOCUS: Fairness via Agent-Awareness for Federated Learning on Heterogeneous Datacited by 6
  16. 2023Fit Like You Sample: Sample-Efficient Generalized Score Matching from Fast Mixing Diffusionscited by 6
  17. 2024Toward Global Convergence of Gradient EM for Over-Parameterized Gaussian Mixture Modelscited by 6
  18. 2021Uniform Consistency in Nonparametric Mixture Modelscited by 5
  19. 2021Towards Statistical and Computational Complexities of Polyak Step Size Gradient Descentcited by 5
  20. 2022Matrix Completion with Hierarchical Graph Side Informationcited by 5
  21. 2022Optimal Clustering by Lloyd Algorithm for Low-Rank Mixture Modelcited by 5
  22. 2023Can semi-supervised learning use all the data effectively? A lower bound perspectivecited by 5
  23. 2025When and How Unlabeled Data Provably Improve In-Context Learningcited by 5
  24. 2021From inexact optimization to learning via gradient concentrationcited by 4
  25. 2021Adaptive Clustering and Personalization in Multi-Agent Stochastic Linear Banditscited by 4
  26. 2021Time varying regression with hidden linear dynamicscited by 4
  27. 2022Moment Estimation for Nonparametric Mixture Models Through Implicit Tensor Decompositioncited by 4
  28. 2023Adversarially robust clustering with optimality guaranteescited by 4
  29. 2024Prototypical Transformer as Unified Motion Learnerscited by 4
  30. 2022Tight Bounds on the Hardness of Learning Simple Nonparametric Mixturescited by 3
  31. 2022Sharper Utility Bounds for Differentially Private Modelscited by 3
  32. 2023Imbalanced Mixed Linear Regressioncited by 3
  33. 2023Efficient and Accurate Learning of Mixtures of Plackett-Luce Modelscited by 3
  34. 2023Mixed Regression via Approximate Message Passingcited by 3
  35. 2024Variance-Aware Linear UCB with Deep Representation for Neural Contextual Banditscited by 3
  36. 2024Towards Sample-Efficiency and Generalization of Transfer and Inverse Reinforcement Learning: A Comprehensive Literature Reviewcited by 3
  37. 2025Nonparametric MLE for Gaussian Location Mixtures: Certified Computation and Generic Behaviorcited by 3
  38. 2021High-Dimensional Differentially-Private EM Algorithm: Methods and Near-Optimal Statistical Guaranteescited by 2

50 most cited of 131 All 131 (JSON)