Global Convergence of Gradient EM for Over-Parameterized Gaussian Mixtures

Abstract

Learning Gaussian Mixture Models (GMMs) is a fundamental problem in statistics and machine learning, with the Expectation-Maximization (EM) algorithm and its popular variant gradient EM being arguably the most widely used algorithms in practice. In the exact-parameterized setting, where both the ground truth GMM and the learning model have the same number of components $m$, a vast line of work has aimed to establish rigorous recovery guarantees for EM. However, global convergence has only been proven for the case of $m=2$, and EM is known to fail to recover the ground truth when $m\geq 3$. In this paper, we consider the $\textit{over-parameterized}$ setting, where the learning model uses $n>m$ components to fit an $m$-component ground truth GMM. In contrast to the exact-parameterized case, we provide a guarantee for convergence to the globally optimal solution (the ground truth) for gradient EM. Specifically, for any well-separated GMMs, we prove that with only mild over-parameterization $n = \Omega(m\log m)$, randomly initialized gradient EM converges to the ground truth with polynomial time and samples. Our analysis proceeds in two stages and introduces a suite of novel tools for Gaussian Mixture analysis to study the dynamics of gradient EM and characterize the geometric landscape of the likelihood loss. This is the first global convergence and recovery result for EM or Gradient EM beyond the special case of $m=2$.