# EM Converges for a Mixture of Many Linear Regressions

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

## Key facts

- Cited by 27 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 May 2019.

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

- [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)
- [Statistical Perspective of Top-K Sparse Softmax Gating Mixture of Experts](https://mlsanity.com/paper/2309.13850/) (2023)
- [Statistical Query Lower Bounds for List-Decodable Linear Regression](https://mlsanity.com/paper/2106.09689/) (2021)
- [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)
- [Prediction Sets for High-Dimensional Mixture of Experts Models](https://mlsanity.com/paper/2210.16710/) (2022)
- [A Wasserstein Minimax Framework for Mixed Linear Regression](https://mlsanity.com/paper/2106.07537/) (2021)
- [What Makes A Good Fisherman? Linear Regression under Self-Selection Bias](https://mlsanity.com/paper/2205.03246/) (2022)
- [Towards the Theory of Unsupervised Federated Learning: Non-asymptotic Analysis of Federated EM Algorithms](https://mlsanity.com/paper/2310.15330/) (2023)
- [Multi-Model 3D Registration: Finding Multiple Moving Objects in Cluttered Point Clouds](https://mlsanity.com/paper/2402.10865/) (2024)
- [Implicit High-Order Moment Tensor Estimation and Learning Latent Variable Models](https://mlsanity.com/paper/2411.15669/) (2024)
- [Uniform Consistency in Nonparametric Mixture Models](https://mlsanity.com/paper/2108.14003/) (2021)
- [Imbalanced Mixed Linear Regression](https://mlsanity.com/paper/2301.12559/) (2023)
- [EM's Convergence in Gaussian Latent Tree Models](https://mlsanity.com/paper/2211.11904/) (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)
- [On Minimax Estimation of Parameters in Softmax-Contaminated Mixture of Experts](https://mlsanity.com/paper/2505.18455/) (2025)
- [Embedding Functional Data: Multidimensional Scaling and Manifold Learning](https://mlsanity.com/paper/2208.14540/) (2022)
- [On the robust learning mixtures of linear regressions](https://mlsanity.com/paper/2305.15317/) (2023)
- [Sample-Efficient Linear Regression with Self-Selection Bias](https://mlsanity.com/paper/2402.14229/) (2024)
- [Fast convergence of a Federated Expectation-Maximization Algorithm](https://mlsanity.com/paper/2408.05819/) (2024)
- [Learning a Class of Mixed Linear Regressions: Global Convergence under General Data Conditions](https://mlsanity.com/paper/2503.18500/) (2025)
- [Linearly Solving Robust Rotation Estimation](https://mlsanity.com/paper/2506.11547/) (2025)
- [Rethinking Multinomial Logistic Mixture of Experts with Sigmoid Gating Function](https://mlsanity.com/paper/2602.01466/) (2026)

## Abstract (arXiv)

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 tildeOmega(k), well-initialized EM converges to the true regression parameters. Previous results for k ≥ 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.