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

arXiv: https://arxiv.org/abs/2006.02601 · HTML: https://mlsanity.com/paper/2006.02601/

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Jun 2020.

## Built on by (most cited first, 24 of 24)

- [RL for Latent MDPs: Regret Guarantees and a Lower Bound](https://mlsanity.com/paper/2102.04939/) (2021)
- [Demystifying Softmax Gating Function in Gaussian Mixture of Experts](https://mlsanity.com/paper/2305.03288/) (2023)
- [On the computational and statistical complexity of over-parameterized matrix sensing](https://mlsanity.com/paper/2102.02756/) (2021)
- [Statistical Perspective of Top-K Sparse Softmax Gating Mixture of Experts](https://mlsanity.com/paper/2309.13850/) (2023)
- [A General Theory for Softmax Gating Multinomial Logistic Mixture of Experts](https://mlsanity.com/paper/2310.14188/) (2023)
- [Towards Convergence Rates for Parameter Estimation in Gaussian-gated Mixture of Experts](https://mlsanity.com/paper/2305.07572/) (2023)
- [Reinforcement Learning in Reward-Mixing MDPs](https://mlsanity.com/paper/2110.03743/) (2021)
- [Learning Mixtures of Linear Dynamical Systems](https://mlsanity.com/paper/2201.11211/) (2022)
- [Tensor Decompositions Meet Control Theory: Learning General Mixtures of Linear Dynamical Systems](https://mlsanity.com/paper/2307.06538/) (2023)
- [Uniform Consistency in Nonparametric Mixture Models](https://mlsanity.com/paper/2108.14003/) (2021)
- [Towards Statistical and Computational Complexities of Polyak Step Size Gradient Descent](https://mlsanity.com/paper/2110.07810/) (2021)
- [Reward-Mixing MDPs with a Few Latent Contexts are Learnable](https://mlsanity.com/paper/2210.02594/) (2022)
- [Tight Bounds on the Hardness of Learning Simple Nonparametric Mixtures](https://mlsanity.com/paper/2203.15150/) (2022)
- [Imbalanced Mixed Linear Regression](https://mlsanity.com/paper/2301.12559/) (2023)
- [High-Dimensional Differentially-Private EM Algorithm: Methods and Near-Optimal Statistical Guarantees](https://mlsanity.com/paper/2104.00245/) (2021)
- [Geometry of EM and related iterative algorithms](https://mlsanity.com/paper/2209.01301/) (2022)
- [EM's Convergence in Gaussian Latent Tree Models](https://mlsanity.com/paper/2211.11904/) (2022)
- [Jointly Modeling and Clustering Tensors in High Dimensions](https://mlsanity.com/paper/2104.07773/) (2021)
- [An Exponentially Increasing Step-size for Parameter Estimation in Statistical Models](https://mlsanity.com/paper/2205.07999/) (2022)
- [Sharp analysis of EM for learning mixtures of pairwise differences](https://mlsanity.com/paper/2302.10066/) (2023)
- [EM for Mixture of Linear Regression with Clustered Data](https://mlsanity.com/paper/2308.11518/) (2023)
- [Global Convergence of Online Identification for Mixed Linear Regression](https://mlsanity.com/paper/2311.18506/) (2023)
- [In-context Learning for Mixture of Linear Regressions: Existence, Generalization and Training Dynamics](https://mlsanity.com/paper/2410.14183/) (2024)
- [Improving Computational Complexity in Statistical Models with Second-Order Information](https://mlsanity.com/paper/2202.04219/) (2022)

## Abstract (arXiv)

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 θ* at the standard parametric convergence rate O((d/n)1/2) after O(log(n/d)) iterations. In the regime where the SNR is above O((d/n)1/4) and below some constant, the EM iterates converge to a O(rm SNR-1 (d/n)1/2) neighborhood of the true parameter, when the number of iterations is of the order O(rm SNR-2 log(n/d)). In the low SNR regime where the SNR is below O((d/n)1/4), we show that EM converges to a O((d/n)1/4) neighborhood of the true parameters, after 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.