Global Convergence and Stationary-Point Characterization of EM for Two-Component Gaussian Mixtures

A global dynamical and statistical consistency analysis (introduced by Ji Xu, Daniel J. Hsu, and Arian Maleki in 2016) of the Expectation-Maximization (EM) algorithm for balanced two-component Gaussian mixtures $0.5\mathcal{N}(\boldsymbol{\mu}_1^\star,\boldsymbol{\Sigma}) + 0.5\mathcal{N}(\boldsymbol{\mu}_2^\star,\boldsymbol{\Sigma})$ with known covariance $\boldsymbol{\Sigma}$ and arbitrary non-zero separation $\boldsymbol{\theta}^\star = (\boldsymbol{\mu}_2^\star - \boldsymbol{\mu}_1^\star)/2 \ne \mathbf{0}$. Re-parameterizing the iterates by the mean-shift error $\boldsymbol{a}^{\langle t\rangle} = \frac{\boldsymbol{\mu}_1^{\langle t\rangle} + \boldsymbol{\mu}_2^{\langle t\rangle}}{2} - \frac{\boldsymbol{\mu}_1^\star + \boldsymbol{\mu}_2^\star}{2}$ and half-separation $\boldsymbol{b}^{\langle t\rangle} = \frac{\boldsymbol{\mu}_2^{\langle t\rangle} - \boldsymbol{\mu}_1^{\langle t\rangle}}{2}$ (Equation 11), Lemmas 6–8 prove that all population EM updates lie in the two-dimensional subspace $\mathrm{span}(\boldsymbol{b}^{\langle 0\rangle},\boldsymbol{\theta}^\star)$ and that the angle $\beta^{\langle t\rangle} = \arccos(\frac{\langle\boldsymbol{b}^{\langle t\rangle},\boldsymbol{\theta}^\star\rangle}{\|\boldsymbol{b}^{\langle t\rangle}\|\|\boldsymbol{\theta}^\star\|})$ decreases monotonically: (1) for any initialization outside the measure-zero orthogonal hyperplane $\langle\boldsymbol{b}^{\langle 0\rangle},\boldsymbol{\theta}^\star\rangle \ne 0$, Theorems 1, 3, and 4 prove linear contraction $\sin(\beta^{\langle t+1\rangle}) \le \kappa_\beta^t\sin(\beta^{\langle 0\rangle})$, $\|\boldsymbol{a}^{\langle t+1\rangle}\|^2 \le \kappa_a^2\|\boldsymbol{a}^{\langle t\rangle}\|^2 + \frac{\|\boldsymbol{\theta}^\star\|^2\sin^2(\beta^{\langle t\rangle})}{4}$, and $\boldsymbol{b}^{\langle t\rangle} \to \mathrm{sgn}(\langle\boldsymbol{b}^{\langle 0\rangle},\boldsymbol{\theta}^\star\rangle)\boldsymbol{\theta}^\star$; (2) if $\langle\boldsymbol{b}^{\langle 0\rangle},\boldsymbol{\theta}^\star\rangle = 0$, Theorems 2 and 5 prove $(\boldsymbol{a}^{\langle t\rangle},\boldsymbol{b}^{\langle t\rangle}) \to (\mathbf{0},\mathbf{0})$, which is the unique non-global stationary point (a local minimum for $d=1$ and a saddle point for $d > 1$, Corollaries 3–4); and (3) Theorem 7 proves that sample-based EM initialized at any $(\boldsymbol{\mu}_1^{\langle 0\rangle},\boldsymbol{\mu}_2^{\langle 0\rangle})$ with $\langle\boldsymbol{\mu}_2^{\langle 0\rangle} - \boldsymbol{\mu}_1^{\langle 0\rangle},\boldsymbol{\theta}^\star\rangle \ne 0$ is globally statistically consistent ($\limsup_{t\to\infty}\|\hat{\boldsymbol{\mu}}_i^{\langle t\rangle} - \boldsymbol{\mu}_i^{\langle t\rangle}\| \xrightarrow{p} 0$ as $n\to\infty$).