mlsanityData to 7 Oct 2026

Singularity, Misspecification, and the Convergence Rate of EM

arXiv 1810.00828 ↗First posted 1 Oct 2018math.ST stat.ML stat.THcited by 38

Not on the map. Why?

Abstract (arXiv)

A line of recent work has analyzed the behavior of the Expectation-Maximization (EM) algorithm in the well-specified setting, in which the population likelihood is locally strongly concave around its maximizing argument. Examples include suitably separated Gaussian mixture models and mixtures of linear regressions. We consider over-specified settings in which the number of fitted components is larger than the number of components in the true distribution. Such misspecified settings can lead to singularity in the Fisher information matrix, and moreover, the maximum likelihood estimator based on n i.i.d. samples in d dimensions can have a non-standard O((d/n)^frac14) rate of convergence. Focusing on the simple setting of two-component mixtures fit to a d-dimensional Gaussian distribution, we study the behavior of the EM algorithm both when the mixture weights are different (unbalanced case), and are equal (balanced case). Our analysis reveals a sharp distinction between these two cases: in the former, the EM algorithm converges geometrically to a point at Euclidean distance of O((d/n)^frac12) from the true parameter, whereas in the latter case, the convergence rate is exponentially slower, and the fixed point has a much lower O((d/n)^frac14) accuracy. Analysis of this singular case requires the introduction of some novel techniques: in particular, we make use of a careful form of localization in the associated empirical process, and develop a recursive argument to progressively sharpen the statistical rate.

Key facts. Cited by 38 papers in the map (data through 7 Oct 2026). First posted on arXiv 1 Oct 2018.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2020: 1; 2021: 9; 2022: 9; 2023: 9; 2024: 4; 2025: 4; 2026: 2.

38 papers.

Sort:

By area:

  1. 2023Demystifying Softmax Gating Function in Gaussian Mixture of Expertscited by 33
  2. 2021On the computational and statistical complexity of over-parameterized matrix sensingcited by 31
  3. 2021Improving Transformers with Probabilistic Attention Keyscited by 28
  4. 2023Statistical Perspective of Top-K Sparse Softmax Gating Mixture of Expertscited by 28
  5. 2023Over-Parameterization Exponentially Slows Down Gradient Descent for Learning a Single Neuroncited by 25
  6. 2025Dimension-Free Convergence of Diffusion Models for Approximate Gaussian Mixturescited by 23
  7. 2022Refined Convergence Rates for Maximum Likelihood Estimation under Finite Mixture Modelscited by 22
  8. 2022Mean-field Variational Inference via Wasserstein Gradient Flowcited by 19
  9. 2023How Over-Parameterization Slows Down Gradient Descent in Matrix Sensing: The Curses of Symmetry and Initializationcited by 18
  10. 2021Clustering a Mixture of Gaussians with Unknown Covariancecited by 14
  11. 2022Counterfactual inference in sequential experimentscited by 13
  12. 2020Provable Hierarchical Imitation Learning via EMcited by 10
26 more
  1. 2021Sharp global convergence guarantees for iterative nonconvex optimization: A Gaussian process perspectivecited by 10
  2. 2021The EM Algorithm is Adaptively-Optimal for Unbalanced Symmetric Gaussian Mixturescited by 6
  3. 2024How does promoting the minority fraction affect generalization? A theoretical study of the one-hidden-layer neural network on group imbalancecited by 6
  4. 2024Toward Global Convergence of Gradient EM for Over-Parameterized Gaussian Mixture Modelscited by 6
  5. 2021Towards Statistical and Computational Complexities of Polyak Step Size Gradient Descentcited by 5
  6. 2023Can semi-supervised learning use all the data effectively? A lower bound perspectivecited by 5
  7. 2023Bayesian Model Selection via Mean-Field Variational Approximationcited by 4
  8. 2021High-Dimensional Differentially-Private EM Algorithm: Methods and Near-Optimal Statistical Guaranteescited by 2
  9. 2021Non-negative matrix factorization algorithms generally improve topic model fitscited by 2
  10. 2022Beyond EM Algorithm on Over-specified Two-Component Location-Scale Gaussian Mixturescited by 2
  11. 2022EM's Convergence in Gaussian Latent Tree Modelscited by 2
  12. 2023Sharp-SSL: Selective high-dimensional axis-aligned random projections for semi-supervised learningcited by 2
  13. 2025Dendrograms of Mixing Measures for Softmax-Gated Gaussian Mixture of Experts: Consistency Without Model Sweepscited by 2
  14. 2021Jointly Modeling and Clustering Tensors in High Dimensionscited by 1
  15. 2022An Exponentially Increasing Step-size for Parameter Estimation in Statistical Modelscited by 1
  16. 2023Sharp analysis of EM for learning mixtures of pairwise differencescited by 1
  17. 2024Fast convergence of the Expectation Maximization algorithm under a logarithmic Sobolev inequalitycited by 1
  18. 2024In-context Learning for Mixture of Linear Regressions: Existence, Generalization and Training Dynamicscited by 1
  19. 2022Improving Computational Complexity in Statistical Models with Second-Order Informationcited by 0
  20. 2022Mean Estimation in High-Dimensional Binary Markov Gaussian Mixture Modelscited by 0
  21. 2022Characterizing Learning Dynamics under Relative Reparameterization of Singular Modelscited by 0
  22. 2023Scalable Clustering: Large Scale Unsupervised Learning of Gaussian Mixture Models with Outlierscited by 0
  23. 2025Learning Overspecified Gaussian Mixtures Exponentially Fast with the EM Algorithmcited by 0
  24. 2025Overspecified Mixture Discriminant Analysis: Exponential Convergence, Statistical Guarantees, and Remote Sensing Applicationscited by 0
  25. 2026Local linear convergence of gradient methods for overparameterized Gaussian mixturescited by 0
  26. 2026Statistical Inference on Gradient Flowscited by 0