Over-Specified Gaussian Mixture EM Singularity Dichotomy and Annulus-Based Epoch Localization

A non-asymptotic statistical and algorithmic theory (introduced by Raaz Dwivedi, Nhat Ho, Koulik Khamaru, Martin J. Wainwright, Michael I. Jordan, and Bin Yu in 2020) characterizing the phase transition of Expectation-Maximization (EM) when fitting over-specified two-component location Gaussian mixtures $\pi\phi(x;\theta,\sigma^2 I_d) + (1-\pi)\phi(x;-\theta,\sigma^2 I_d)$ (and over-specified mixtures of linear regressions) to homogeneous data $X\sim\mathcal{N}(0,\sigma^2 I_d)$ ($\theta^* = 0$). At $\theta^* = 0$, the Fisher information matrix is $\mathcal{I}^\pi(0) = (1 - 4\pi(1-\pi))I_d = \rho^2 I_d$ where $\rho = |1 - 2\pi|$ (Equation 84): (1) in the *unbalanced* case ($\pi \ne 1/2$, $\rho > 0$), $\mathcal{I}^\pi(0) \succ 0$, the population EM operator $M(\theta) = \mathbb{E}[(2w_\theta^\pi(X)-1)X]$ is globally strictly contractive $\|M(\theta)\|_2 \le (1 - \rho^2/2)\|\theta\|_2$ (Theorem 1a, Equation 10a), and sample EM converges in $O(\log(n/d)/\rho^2)$ steps to parametric $O((d/n)^{1/2})$ error (Theorem 1b, Equation 10b); (2) in the *balanced* case ($\pi = 1/2$, $\rho = 0$), $\mathcal{I}^{1/2}(0) = 0$ is singular (quartic population log-likelihood $\mathcal{L}^{1/2}(\theta)\approx -c\|\theta\|_2^4$), population EM exhibits state-dependent sub-geometric contraction $\frac{1}{1+2\|\theta\|_2^2/\sigma^2} \le \frac{\|M(\theta)\|_2}{\|\theta\|_2} \le 1 - p + \frac{p}{1+\|\theta\|_2^2/(2\sigma^2)}$ requiring $\Theta(\epsilon^{-2}\log(1/\epsilon))$ steps (Theorem 2, Equations 13–15), and an *annulus-based epoch localization* argument over shells $(d/n)^{\alpha_{\ell+1}} \le \|\theta^t\|_2 \le (d/n)^{\alpha_\ell}$ with exponent recursion $\alpha_{\ell+1} = \frac{1}{3}\alpha_\ell + \frac{1}{6} \to \alpha^* = 1/4$ (Equations 22–25) proves that sample EM reaches the sharp singular rate $O((d/n)^{1/4-\alpha})$ in $O((n/d)^{1/2-2\alpha}\log(n/d))$ steps (Theorem 3, Equation 16) with matching $\Omega(n^{-1/4})$ fixed-point lower bound (Theorem 4, Equation 17).