Randomly initialized EM algorithm for two-component Gaussian mixture achieves near optimality in \(O(\sqrt{n})\) iterations (Q2113265)

Summary: We analyze the classical EM algorithm for parameter estimation in the symmetric two-component Gaussian mixtures in \(d\) dimensions. We show that, even in the absence of any separation between components, provided that the sample size satisfies \(n=\Omega (d \log^4 d)\), the randomly initialized EM algorithm converges to an estimate in at most \(O(\sqrt{n})\) iterations with high probability, which is at most \(O((d/n)^{1/4} \log n)\) in Euclidean distance from the true parameter and within logarithmic factors of the minimax rate of \((d/n)^{1/4}\). Both the nonparametric statistical rate and the sublinear convergence rate are direct consequences of the zero Fisher information in the worst case. Refined pointwise guarantees beyond worst-case analysis and convergence to the MLE are also shown under mild conditions. This improves the previous result of \textit{S. Balakrishnan} et al. [Ann. Stat. 45, No. 1, 77--120 (2017; Zbl 1367.62052)], which requires strong conditions on both the separation of the components and the quality of the initialization, and that of \textit{C. Daskalakis}, \textit{C. Tzamos} and \textit{M. Zampetakis} [``Ten steps of EM suffice for mixtures of two Gaussians'', Proc. Mach. Learn. Res. (PMLR) 65, 704--710 (2017)], which requires sample splitting and restarting the EM iteration.