Population-to-Sample Contraction, First-Order Stability (FOS), and Gradient Stability (GS) Framework for the EM Algorithm

A two-stage population-to-sample non-asymptotic analytical framework (introduced by Sivaraman Balakrishnan, Martin J. Wainwright, and Bin Yu in 2017) for establishing local geometric convergence and minimax-rate statistical guarantees for the Expectation-Maximization (EM) operator $M_n(\theta) = \arg\max_{\theta'\in\Omega} Q_n(\theta'\mid\theta)$ and first-order gradient EM operator $G_n(\theta) = \theta + \alpha\nabla Q_n(\theta\mid\theta)$ around a population likelihood maximizer $\theta^*$. Exploiting the self-consistency identity $\theta^* = \arg\max_{\theta\in\Omega} Q(\theta\mid\theta^*)$ (Equation 24), Theorem 1 proves that if the oracle surrogate $q(\theta) = Q(\theta\mid\theta^*)$ is $\lambda$-strongly concave (Equation 25) and the family $\{Q(\cdot\mid\theta)\}$ satisfies *First-Order Stability* $\mathrm{FOS}(\gamma)$: $\|\nabla Q(M(\theta)\mid\theta^*) - \nabla Q(M(\theta)\mid\theta)\|_2 \le \gamma\|\theta - \theta^*\|_2$ on $\mathbb{B}_2(r;\theta^*)$ with $0 \le \gamma < \lambda$ (Definition 1, Equation 29), then the population EM operator is $\kappa$-contractive with $\kappa = \gamma/\lambda < 1$ ($\|M(\theta) - \theta^*\|_2 \le \frac{\gamma}{\lambda}\|\theta - \theta^*\|_2$). Analogously, under $\mu$-smoothness of $q$ and *Gradient Stability* $\mathrm{GS}(\gamma)$: $\|\nabla Q(\theta\mid\theta^*) - \nabla Q(\theta\mid\theta)\|_2 \le \gamma\|\theta - \theta^*\|_2$ (Definition 2, Equation 46), Theorem 3 proves that population gradient EM with step size $\alpha = \frac{2}{\mu+\lambda}$ contracts with factor $1 - \frac{2\lambda - 2\gamma}{\mu+\lambda} < 1$. Coupling population contraction with uniform empirical-process deviation bounds $\sup_{\theta\in\mathbb{B}_2(r;\theta^*)}\|M_n(\theta) - M(\theta)\|_2 \le \varepsilon_M^{\mathrm{unif}}(n,\delta)$ (or pointwise sample-splitting bounds $\varepsilon_M(n/T,\delta/T)$), Theorems 2 and 4 guarantee $\|\theta^t - \theta^*\|_2 \le \kappa^t\|\theta^0 - \theta^*\|_2 + \frac{1}{1-\kappa}\varepsilon_M^{\mathrm{unif}}(n,\delta)$ (Equations 35b, 51b), yielding $O(\sqrt{(d/n)\log(1/\delta)})$ statistical accuracy across Gaussian mixtures, mixtures of regressions, and missing-covariate linear regression.