Is √d Separation Necessary for Gradient EM to Learn Gaussian Mixtures in High Dimensions?
Abstract
Learning Gaussian mixture models (GMMs) using the Expectation-Maximization (EM) algorithm and its gradient-based variants is a fundamental problem in machine learning. It is known that randomly initialized (gradient) EM fails to learn multi-component GMMs in the exact-parameterized setting, where the number of components matches that of the ground-truth GMM. Recently, global convergence of gradient EM has been established in the over-parameterized setting, where more components are used, provided that the ground-truth components are well separated. In particular, the minimum separation between ground-truth components is required to scale as Ω(√d), where d is the dimension. In this paper, we show that this dimensional dependence is unavoidable in high-dimensional settings. Specifically, we consider a hybrid EM algorithm that uses standard EM updates for the mixing weights and gradient EM updates for the component means. For any ε> 0, we prove that when the dimension is sufficiently large, in the worst case a separation of order Ω(d0.5−ε) is insufficient to guarantee global convergence of population gradient EM in sub-exponential time under random initialization, even in the over-parameterized regime. Our result establishes an almost optimal worst-case lower bound on the ground-truth separation required for learning Gaussian mixtures via gradient EM in high dimensions.
Related
- Entangled measurements are necessary for optimal tomography of mixed fermionic Gaussian states and of bosonic Gaussian states near the vacuum
- Dimension-free comparison inequalities between f-divergences for Gaussian location mixtures
- Solving the Ho--Nguyen Conjecture for Gaussian Mixtures: Applications to Mixtures of Experts
- Squarefree values of random polynomials are Gaussian mixtures
- Softmax Attention on Gaussian Mixtures: Linear When It Can, Selective When It Must
BibTeX
@misc{zhang2026separation,
title = {{Is $\sqrtd$ Separation Necessary for Gradient EM to Learn Gaussian Mixtures in High Dimensions?}},
author = {Yiran Zhang and Mo Zhou and Weihang Xu and Maryam Fazel and Simon S. Du},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.07551},
eprint = {2610.07551},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.07551},
}
RIS
TY - UNPB
TI - Is √d Separation Necessary for Gradient EM to Learn Gaussian Mixtures in High Dimensions?
AU - Yiran Zhang
AU - Mo Zhou
AU - Weihang Xu
AU - Maryam Fazel
AU - Simon S. Du
PY - 2026
DA - 2026/10/06
PB - arXiv
DO - 10.48550/arxiv.2610.07551
UR - https://arxiv.org/abs/2610.07551
AB - Learning Gaussian mixture models (GMMs) using the Expectation-Maximization (EM) algorithm and its gradient-based variants is a fundamental problem in machine learning. It is known that randomly initialized (gradient) EM fails to learn multi-component GMMs in the exact-parameterized setting, where the number of components matches that of the ground-truth GMM. Recently, global convergence of gradient EM has been established in the over-parameterized setting, where more components are used, provided that the ground-truth components are well separated. In particular, the minimum separation between ground-truth components is required to scale as Ω(√d), where d is the dimension. In this paper, we show that this dimensional dependence is unavoidable in high-dimensional settings. Specifically, we consider a hybrid EM algorithm that uses standard EM updates for the mixing weights and gradient EM updates for the component means. For any ε> 0, we prove that when the dimension is sufficiently large, in the worst case a separation of order Ω(d^0.5−ε) is insufficient to guarantee global convergence of population gradient EM in sub-exponential time under random initialization, even in the over-parameterized regime. Our result establishes an almost optimal worst-case lower bound on the ground-truth separation required for learning Gaussian mixtures via gradient EM in high dimensions.
ER -