Convergence and Optimality of the EM Algorithm Under Multi-Component Gaussian Mixture Models
TL;DR
Two novel analytical approaches are developed, each tailored to a different separation regime, reflecting two complementary perspectives on the use of EM: parameter estimation and clustering, which allow the number of Gaussian components, the minimum mixing weight, the component separation, and the dimension to grow with the sample size.
Abstract
Gaussian mixture models are fundamental statistical tools for modeling heterogeneous data. Due to the nonconcavity of the likelihood function, the Expectation-Maximization (EM) algorithm is widely used for parameter estimation of each Gaussian component. Existing analyses of the EM algorithm’s convergence to the true parameter focus on either the two-component case or multi-component settings with known mixing probabilities and isotropic covariance matrices. In this work, we study the convergence of the EM algorithm for multi-component Gaussian mixture models in full generality. The population-level EM algorithm converges to the true parameters provided that the minimum pairwise separation between Gaussian components exceeds a logarithmic factor of the maximum separation and the inverse of the smallest mixing weight. At the sample level, the EM algorithm is further shown to be minimax rate-optimal. We develop two novel analytical approaches, each tailored to a different separation regime, reflecting two complementary perspectives on the use of EM: parameter estimation and clustering. As a byproduct, our analysis reveals that the EM algorithm, when used for community detection, also achieves the minimax optimal rate of misclustering error, an interesting result in its own right. Our results allow the number of Gaussian components, the minimum mixing weight, the component separation, and the dimension to grow with the sample size. Simulation studies corroborate our theoretical findings.