Global Convergence of Gradient EM for Over-Parameterized Gaussian Mixtures
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 = Ω(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$.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Toward Global Convergence of Gradient EM for Over-Parameterized Gaussian Mixture Models
We study the gradient Expectation-Maximization (EM) algorithm for Gaussian Mixture Models (GMM) in the over-parameterized setting, where a general GMM with $n>1$ components learns from data that are generated by a single…
Convergence Dynamics of Over-Parameterized Score Matching for a Single Gaussian
Score matching has become a central training objective in modern generative modeling, particularly in diffusion models, where it is used to learn high-dimensional data distributions through the estimation of score functi…
Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks
We study the problem of training deep neural networks with Rectified Linear Unit (ReLU) activation function using gradient descent and stochastic gradient descent. In particular, we study the binary classification proble…
Binary ClassificationOn the Gradient Domination of the LQG Problem
We consider solutions to the linear quadratic Gaussian (LQG) regulator problem via policy gradient (PG) methods. Although PG methods have demonstrated strong theoretical guarantees in solving the linear quadratic regulat…
Global Convergence of Adaptive Gradient Methods for An Over-parameterized Neural Network
Adaptive gradient methods like AdaGrad are widely used in optimizing neural networks. Yet, existing convergence guarantees for adaptive gradient methods require either convexity or smoothness, and, in the smooth setting,…