EM Converges for a Mixture of Many Linear Regressions
This provides theoretical guarantees for a common algorithm in statistical learning, addressing a gap for noisy environments with multiple components, though it is incremental by extending prior noiseless results.
The paper tackles the problem of proving convergence for the Expectation-Maximization (EM) algorithm applied to mixtures of linear regressions with multiple components, showing that with sufficient signal-to-noise ratio and good initialization, EM converges to true parameters even in noisy settings, achieving a statistical error rate independent of parameter norms.
We study the convergence of the Expectation-Maximization (EM) algorithm for mixtures of linear regressions with an arbitrary number $k$ of components. We show that as long as signal-to-noise ratio (SNR) is $\tildeΩ(k)$, well-initialized 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 $σ\rightarrow 0$, in contrast to most previous local convergence results for EM, where the statistical error scaled with the norm of parameters. Standard moment-method approaches may be applied to guarantee we are in the region where our local convergence guarantees apply.