# Is √d Separation Necessary for Gradient EM to Learn Gaussian Mixtures in High Dimensions?

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 2 of its 40 references that are in the map.
- First posted on arXiv 6 Oct 2026.

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

- [Implicit High-Order Moment Tensor Estimation and Learning Latent Variable Models](https://mlsanity.com/paper/2411.15669/) (2024)
- [Global Convergence of Gradient EM for Over-Parameterized Gaussian Mixtures](https://mlsanity.com/paper/2506.06584/) (2025)

## Abstract (arXiv)

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 Omega(√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 Omega(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.