EM Converges for a Mixture of Many Linear Regressions
[edit]
Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, PMLR 108:17271736, 2020.
Abstract
We study the convergence of the ExpectationMaximization (EM) algorithm for mixtures of linear regressions with an arbitrary number $k$ of components. We show that as long as signaltonoise ratio (SNR) is $\tilde{\Omega}(k)$, wellinitialized EM converges to the true regression parameters. Previous results for $k \geq 3$ have only established local convergence for the noiseless setting, i.e., where SNR is infinitely large. Our results enlarge the scope to the environment with noises, and notably, we establish a statistical error rate that is independent of the norm (or pairwise distance) of the regression parameters. In particular, our results imply exact recovery as $\sigma \rightarrow 0$, in contrast to most previous local convergence results for EM, where the statistical error scaled with the norm of parameters. Standard momentmethod approaches may be applied to guarantee we are in the region where our local convergence guarantees apply.
Related Material


