SINGULARITY, MISSPECIFICATION AND THE CONVERGENCE RATE OF EM

• 成果类型: Article
• 署名作者: Dwivedi, Raaz; Nhat Ho; Khamaru, Koulik; Wainwright, Martin J.; Jordan, Michael, I; Yu, Bin
• 署名单位: University of California System; University of California Berkeley; University of California System; University of California Berkeley
• 刊物名称: ANNALS OF STATISTICS
• ISSN/ISSBN: 0090-5364
• DOI: 10.1214/19-AOS1924
• 发表日期: 2020
• 页码: 3161-3182
• 关键词: maximum-likelihood; mixture; Finite; algorithm

摘要

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 mis-specified 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 nonstandard O((d/n)(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 geomet- rically to a point at Euclidean distance of O((d/n)(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 O((d/n)(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.