# The EM Algorithm is Adaptively-Optimal for Unbalanced Symmetric Gaussian Mixtures

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 45 references that are in the map.
- First posted on arXiv 29 Mar 2021.

## Builds on (most cited first, 11 of 11)

- [Statistical guarantees for the EM algorithm: From population to sample-based analysis](https://mlsanity.com/paper/1408.2156/) (2014)
- [Ten Steps of EM Suffice for Mixtures of Two Gaussians](https://mlsanity.com/paper/1609.00368/) (2016)
- [Singularity, Misspecification, and the Convergence Rate of EM](https://mlsanity.com/paper/1810.00828/) (2018)
- [Global analysis of Expectation Maximization for mixtures of two Gaussians](https://mlsanity.com/paper/1608.07630/) (2016)
- [Randomly initialized EM algorithm for two-component Gaussian mixture achieves near optimality in O(√n) iterations](https://mlsanity.com/paper/1908.10935/) (2019)
- [Global Convergence of EM Algorithm for Mixtures of Two Component Linear Regression](https://mlsanity.com/paper/1810.05752/) (2018)
- [Regularized EM Algorithms: A Unified Framework and Statistical Guarantees](https://mlsanity.com/paper/1511.08551/) (2015)
- [Estimating the Coefficients of a Mixture of Two Linear Regressions by Expectation Maximization](https://mlsanity.com/paper/1704.08231/) (2017)
- [Statistical and Computational Guarantees for the Baum-Welch Algorithm](https://mlsanity.com/paper/1512.08269/) (2015)
- [Statistical Guarantees for Estimating the Centers of a Two-component Gaussian Mixture by EM](https://mlsanity.com/paper/1608.02280/) (2016)
- [High Dimensional Expectation-Maximization Algorithm: Statistical Optimization and Asymptotic Normality](https://mlsanity.com/paper/1412.8729/) (2014)

## Built on by (most cited first, 6 of 6)

- [Toward Global Convergence of Gradient EM for Over-Parameterized Gaussian Mixture Models](https://mlsanity.com/paper/2407.00490/) (2024)
- [Nonparametric MLE for Gaussian Location Mixtures: Certified Computation and Generic Behavior](https://mlsanity.com/paper/2503.20193/) (2025)
- [Joint Problems in Learning Multiple Dynamical Systems](https://mlsanity.com/paper/2311.02181/) (2023)
- [In-context Learning for Mixture of Linear Regressions: Existence, Generalization and Training Dynamics](https://mlsanity.com/paper/2410.14183/) (2024)
- [Wasserstein Contraction of Coordinate Ascent Variational Inference](https://mlsanity.com/paper/2605.30253/) (2026)
- [Mean Estimation in High-Dimensional Binary Markov Gaussian Mixture Models](https://mlsanity.com/paper/2206.02455/) (2022)

## Abstract (arXiv)

This paper studies the problem of estimating the means ±θ*∈ℝd of a symmetric two-component Gaussian mixture δ*· N(θ*,I)+(1-δ*)· N(-θ*,I) where the weights δ* and 1-δ* are unequal. Assuming that δ* is known, we show that the population version of the EM algorithm globally converges if the initial estimate has non-negative inner product with the mean of the larger weight component. This can be achieved by the trivial initialization θ0=0. For the empirical iteration based on n samples, we show that when initialized at θ0=0, the EM algorithm adaptively achieves the minimax error rate tildeOBig(minBigfrac1(1-2δ*)√fracdn,frac1|θ*|√fracdn,left(fracdnright)1/4BigBig) in no more than OBig(frac1|θ*|(1-2δ*)Big) iterations (with high probability). We also consider the EM iteration for estimating the weight δ*, assuming a fixed mean θ (which is possibly mismatched to θ*). For the empirical iteration of n samples, we show that the minimax error rate tildeOBig(frac1|θ*|√fracdnBig) is achieved in no more than OBig(frac1|θ*|2Big) iterations. These results robustify and complement recent results of Wu and Zhou obtained for the equal weights case δ*=1/2.