EM Converges for a Mixture of Many Linear Regressions

Abstract

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{\Omega }(k)$, well-initialized EM converges to the true regression parameters. Previous results for $k\ge 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 \to 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.

SNR, initialization conditions improved from previous version

Cited by in corpus (6)

• On the Minimax Optimality of the EM Algorithm for Learning Two-Component Mixed Linear Regression
• Statistical Query Lower Bounds for List-Decodable Linear Regression
• Uniform Consistency in Nonparametric Mixture Models
• Learning Mixtures of Graphs from Epidemic Cascades
• A Wasserstein Minimax Framework for Mixed Linear Regression
• Learning Mixtures of Low-Rank Models