Singularity, Misspecification, and the Convergence Rate of EM

Abstract

A line of recent work has analyzed the behavior of the Expectation-Maximization (EM) algorithm in the well-specified setting, in which the population likelihood is locally strongly concave around its maximizing argument. Examples include suitably separated Gaussian mixture models and mixtures of linear regressions. We consider over-specified settings in which the number of fitted components is larger than the number of components in the true distribution. Such misspecified settings can lead to singularity in the Fisher information matrix, and moreover, the maximum likelihood estimator based on $n$ i.i.d. samples in $d$ dimensions can have a non-standard $\mathcal{O}((d/n{)}^{\frac{1}{4}})$ rate of convergence. Focusing on the simple setting of two-component mixtures fit to a $d$-dimensional Gaussian distribution, we study the behavior of the EM algorithm both when the mixture weights are different (unbalanced case), and are equal (balanced case). Our analysis reveals a sharp distinction between these two cases: in the former, the EM algorithm converges geometrically to a point at Euclidean distance of $\mathcal{O}((d/n{)}^{\frac{1}{2}})$ from the true parameter, whereas in the latter case, the convergence rate is exponentially slower, and the fixed point has a much lower $\mathcal{O}((d/n{)}^{\frac{1}{4}})$ accuracy. Analysis of this singular case requires the introduction of some novel techniques: in particular, we make use of a careful form of localization in the associated empirical process, and develop a recursive argument to progressively sharpen the statistical rate.

arXiv comment63 pages, 12 figures. The first three authors contributed equally to this work. To appear in Annals of Statistics

References in corpus (5)

• 2004 IMS Medallion Lecture: Local Rademacher complexities and oracle inequalities in risk minimization
• Hypothesis test for normal mixture models: The EM approach
• Global analysis of Expectation Maximization for mixtures of two Gaussians
• Regularized EM Algorithms: A Unified Framework and Statistical Guarantees
• Statistical Inference with Local Optima

Cited by in corpus (6)

• Provable Hierarchical Imitation Learning via EM
• A Diffusion Process Perspective on Posterior Contraction Rates for Parameters
• Estimating the Coefficients of a Mixture of Two Linear Regressions by Expectation Maximization
• The EM Algorithm is Adaptively-Optimal for Unbalanced Symmetric Gaussian Mixtures
• Cutoff for exact recovery of Gaussian mixture models
• A Doubly-Enhanced EM Algorithm for Model-Based Tensor Clustering