Statistical guarantees for the EM algorithm: From population to sample-based analysis
This work offers statistical guarantees for EM algorithms, addressing a foundational problem in machine learning for researchers and practitioners dealing with incomplete data, though it is incremental in extending existing theory.
The authors developed a theoretical framework to provide rigorous performance guarantees for the EM and gradient EM algorithms, showing that with proper initialization, a small number of steps yields estimates within statistical error of the MLE for problems like Gaussian mixtures, with simulations confirming these predictions.
We develop a general framework for proving rigorous guarantees on the performance of the EM algorithm and a variant known as gradient EM. Our analysis is divided into two parts: a treatment of these algorithms at the population level (in the limit of infinite data), followed by results that apply to updates based on a finite set of samples. First, we characterize the domain of attraction of any global maximizer of the population likelihood. This characterization is based on a novel view of the EM updates as a perturbed form of likelihood ascent, or in parallel, of the gradient EM updates as a perturbed form of standard gradient ascent. Leveraging this characterization, we then provide non-asymptotic guarantees on the EM and gradient EM algorithms when applied to a finite set of samples. We develop consequences of our general theory for three canonical examples of incomplete-data problems: mixture of Gaussians, mixture of regressions, and linear regression with covariates missing completely at random. In each case, our theory guarantees that with a suitable initialization, a relatively small number of EM (or gradient EM) steps will yield (with high probability) an estimate that is within statistical error of the MLE. We provide simulations to confirm this theoretically predicted behavior.