Learning Gaussian Mixture Models (GMMs) is a fundamental problem in machine learning, and the Expectation-Maximization (EM) algorithm (Dempster,’77) and its variant gradient-EM are widely used algorithms for it. When the ground-truth GMM and the learning model have the same number of components m, a line of prior work has attempted to establish rigorous recovery guarantees; however, EM methods are known to fail to recover the ground truth when m>2.

This talk considers the “over-parameterized” case, where the learning model uses n>m components to fit an m-component GMM. I will show that gradient-EM converges globally and recovers the GMM: for a well-separated GMM with only mild over-parameterization n = \Omega(m log m), randomly initialized gradient-EM converges to the ground truth at a polynomial rate with polynomial samples. The analysis relies on novel characterization of the geometric landscape of the likelihood loss. This is the first global convergence result for EM methods beyond the special case of m=2. We will also discuss a way to speed up gradient-EM. More broadly, this talk highlights how over-parameterization or “scaling” can fundamentally alter optimization outcomes favorably for machine learning models.