الملخص
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 $Ω(\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 $ε> 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.
الكلمات المفتاحية
الموضوع
بيانات النشر
- المجلة
- غير متاح
- وصول مفتوح
- وصول مفتوح أخضر
اقتبس هذه المقالة
APA 7
Zhang, Y., Zhou, M., Xu, W., Fazel, M., & Du, S. S. (2026). Is $\sqrt{d}$ Separation Necessary for Gradient EM to Learn Gaussian Mixtures in High Dimensions? https://omanscience.com/ar/articles/is-sqrt-d-separation-necessary-for-gradient-em-to-learn-gaussian-mixtures-in-high-dimensions
MLA 9
Zhang, Yiran, et al. "Is $\sqrt{d}$ Separation Necessary for Gradient EM to Learn Gaussian Mixtures in High Dimensions?" https://omanscience.com/ar/articles/is-sqrt-d-separation-necessary-for-gradient-em-to-learn-gaussian-mixtures-in-high-dimensions.
شيكاغو (المؤلف–التاريخ)
Zhang, Yiran, Mo Zhou, Weihang Xu, Maryam Fazel, and Simon S. Du. 2026. "Is $\sqrt{d}$ Separation Necessary for Gradient EM to Learn Gaussian Mixtures in High Dimensions?" https://omanscience.com/ar/articles/is-sqrt-d-separation-necessary-for-gradient-em-to-learn-gaussian-mixtures-in-high-dimensions.
هارفارد
Zhang, Y., Zhou, M., Xu, W., Fazel, M. and Du, S. S. (2026) 'Is $\sqrt{d}$ Separation Necessary for Gradient EM to Learn Gaussian Mixtures in High Dimensions?', Available at: https://omanscience.com/ar/articles/is-sqrt-d-separation-necessary-for-gradient-em-to-learn-gaussian-mixtures-in-high-dimensions.
فانكوفر
Zhang Y, Zhou M, Xu W, Fazel M, Du SS. Is $\sqrt{d}$ Separation Necessary for Gradient EM to Learn Gaussian Mixtures in High Dimensions? https://omanscience.com/ar/articles/is-sqrt-d-separation-necessary-for-gradient-em-to-learn-gaussian-mixtures-in-high-dimensions
IEEE
Y. Zhang, M. Zhou, W. Xu, M. Fazel, and S. S. Du, "Is $\sqrt{d}$ Separation Necessary for Gradient EM to Learn Gaussian Mixtures in High Dimensions?," https://omanscience.com/ar/articles/is-sqrt-d-separation-necessary-for-gradient-em-to-learn-gaussian-mixtures-in-high-dimensions.