pipette
ENEnglish

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

Yiran Zhang, Mo Zhou, Weihang Xu, Maryam Fazel, Simon S. Du

Preprint

En palabras de los autores

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 , where 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 , we prove that when the dimension is sufficiently large, in the worst case a separation of order 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.

Resultado principalLimitación que admiten los autores

Apareció: miércoles, 7 de octubre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: 51 pages