arXiv：cs.LG· Yiran Zhang, Mo Zhou, Weihang Xu, Maryam Fazel, Simon S. Du·· 4 小时前AI 评分28
梯度 EM 学习高维高斯混合模型是否必须要求 √d 分离度？
Is $\sqrt{d}$ Separation Necessary for Gradient EM to Learn Gaussian Mixtures in High Dimensions?
AI 导读
一项理论分析证明，梯度 EM 在高维下学习高斯混合模型时，真值分量间的分离度要求无法摆脱维度依赖。作者证明：维度足够大时，即便在过参数化设置下，最坏情况下 Ω(d^{0.5-ε}) 量级的分离度也不足以保证随机初始化下总体梯度 EM 在次指数时间内全局收敛，从而给出近乎最优的最坏情况分离度下界。
正文
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 $\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.
| Comments: | 51 pages |
| Subjects: | Machine Learning (stat.ML); Machine Learning (cs.LG) |
| Cite as: | arXiv:2610.07551 [stat.ML] |
| (or arXiv:2610.07551v1 [stat.ML] for this version) | |
| https://doi.org/10.48550/arXiv.2610.07551 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Yiran Zhang [view email]
[v1]
Tue, 6 Oct 2026 00:29:03 UTC (158 KB)
来源：arXiv：cs.LG · arxiv.org