Metraipolis › archive › dc_ccf3ed23c635

Is $\sqrt{d}$ Separation Necessary for Gradient EM to Learn Gaussian Mixtures in High Dimensions? — arXiv:2610.07551

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.07551
License (as archived)
CC0-1.0
Archived
2026-10-07T11:42:27.886Z
SHA-256 of the archived text
55afc864aafae924f59ea4d26ea44fde8b681fadf622c471759b3d24b87ff42c
Stable URL of this page
https://metraipolis.com/documento/dc_ccf3ed23c635

How to cite

Is $\sqrt{d}$ Separation Necessary for Gradient EM to Learn Gaussian Mixtures in High Dimensions? — arXiv:2610.07551 — arXiv (en), https://arxiv.org/abs/2610.07551 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_ccf3ed23c635 (Metraipolis archive dc_ccf3ed23c635, sha256 55afc864aafae924f59ea4d26ea44fde8b681fadf622c471759b3d24b87ff42c)
BibTeX
@misc{dcccf3ed23c635,
  title = {Is $sqrtd$ Separation Necessary for Gradient EM to Learn Gaussian Mixtures in High Dimensions? — arXiv:2610.07551},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.07551},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_ccf3ed23c635; sha256 55afc864aafae924f59ea4d26ea44fde8b681fadf622c471759b3d24b87ff42c},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.07551. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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(\sqrt{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 $\epsilon > 0$, we prove that when the dimension is sufficiently large, in the worst case a separation of order $\Omega(d^{0.5-\epsilon})$ 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.

Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.LG, nuovi lavori del giorno).
Categorie arXiv: Machine Learning (stat.ML) ; Machine Learning (cs.LG).
Pagina del lavoro: https://arxiv.org/abs/2610.07551 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T11:19:24.898Z dalla pagina https://arxiv.org/list/cs.LG/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).