On the Minimax Optimality of the EM Algorithm for Learning Two-Component Mixed Linear Regression

Abstract

We study the convergence rates of the EM algorithm for learning two-component mixed linear regression under all regimes of signal-to-noise ratio (SNR). We resolve a long-standing question that many recent results have attempted to tackle: we completely characterize the convergence behavior of EM, and show that the EM algorithm achieves minimax optimal sample complexity under all SNR regimes. In particular, when the SNR is sufficiently large, the EM updates converge to the true parameter ${\theta }^{\ast }$ at the standard parametric convergence rate $\mathcal{O}((d/n{)}^{1/2})$ after $\mathcal{O}(\log (n/d))$ iterations. In the regime where the SNR is above $\mathcal{O}((d/n{)}^{1/4})$ and below some constant, the EM iterates converge to a $\mathcal{O}({\mathrm{SNR}}^{-1}(d/n{)}^{1/2})$ neighborhood of the true parameter, when the number of iterations is of the order $\mathcal{O}({\mathrm{SNR}}^{-2}\log (n/d))$. In the low SNR regime where the SNR is below $\mathcal{O}((d/n{)}^{1/4})$, we show that EM converges to a $\mathcal{O}((d/n{)}^{1/4})$ neighborhood of the true parameters, after $\mathcal{O}((n/d{)}^{1/2})$ iterations. Notably, these results are achieved under mild conditions of either random initialization or an efficiently computable local initialization. By providing tight convergence guarantees of the EM algorithm in middle-to-low SNR regimes, we fill the remaining gap in the literature, and significantly, reveal that in low SNR, EM changes rate, matching the $n^{-1/4}$ rate of the MLE, a behavior that previous work had been unable to show.

arXiv commentAISTATS 2021

References in corpus (9)

• Hypothesis test for normal mixture models: The EM approach
• Alternating Minimization for Mixed Linear Regression
• Spectral Experts for Estimating Mixtures of Linear Regressions
• Global analysis of Expectation Maximization for mixtures of two Gaussians
• Solving a Mixture of Many Random Linear Equations by Tensor Decomposition and Alternating Minimization
• EM Converges for a Mixture of Many Linear Regressions
• Convergence Rates for Gaussian Mixtures of Experts
• The EM Algorithm gives Sample-Optimality for Learning Mixtures of Well-Separated Gaussians
• Alternating Minimization Converges Super-Linearly for Mixed Linear Regression