# Global Convergence of EM Algorithm for Mixtures of Two Component Linear Regression

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

## Key facts

- Cited by 25 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Oct 2018.

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

- [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)
- [A General Theory for Softmax Gating Multinomial Logistic Mixture of Experts](https://mlsanity.com/paper/2310.14188/) (2023)
- [Refined Convergence Rates for Maximum Likelihood Estimation under Finite Mixture Models](https://mlsanity.com/paper/2202.08786/) (2022)
- [Towards Convergence Rates for Parameter Estimation in Gaussian-gated Mixture of Experts](https://mlsanity.com/paper/2305.07572/) (2023)
- [On Learning Mixture of Linear Regressions in the Non-Realizable Setting](https://mlsanity.com/paper/2205.13166/) (2022)
- [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)
- [The EM Algorithm is Adaptively-Optimal for Unbalanced Symmetric Gaussian Mixtures](https://mlsanity.com/paper/2103.15653/) (2021)
- [Toward Global Convergence of Gradient EM for Over-Parameterized Gaussian Mixture Models](https://mlsanity.com/paper/2407.00490/) (2024)
- [Imbalanced Mixed Linear Regression](https://mlsanity.com/paper/2301.12559/) (2023)
- [Online Learning and Information Exponents: On The Importance of Batch size, and Time/Complexity Tradeoffs](https://mlsanity.com/paper/2406.02157/) (2024)
- [High-Dimensional Differentially-Private EM Algorithm: Methods and Near-Optimal Statistical Guarantees](https://mlsanity.com/paper/2104.00245/) (2021)
- [Support Recovery in Mixture Models with Sparse Parameters](https://mlsanity.com/paper/2202.11940/) (2022)
- [Beyond EM Algorithm on Over-specified Two-Component Location-Scale Gaussian Mixtures](https://mlsanity.com/paper/2205.11078/) (2022)
- [EM's Convergence in Gaussian Latent Tree Models](https://mlsanity.com/paper/2211.11904/) (2022)
- [Learning Mixtures of Experts with EM: A Mirror Descent Perspective](https://mlsanity.com/paper/2411.06056/) (2024)
- [Efficient Algorithms for Estimating the Parameters of Mixed Linear Regression Models](https://mlsanity.com/paper/2105.05953/) (2021)
- [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)
- [Agnostic Learning of Mixed Linear Regressions with EM and AM Algorithms](https://mlsanity.com/paper/2406.01149/) (2024)
- [In-context Learning for Mixture of Linear Regressions: Existence, Generalization and Training Dynamics](https://mlsanity.com/paper/2410.14183/) (2024)
- [Fast convergence of a Federated Expectation-Maximization Algorithm](https://mlsanity.com/paper/2408.05819/) (2024)
- [Expectation Maximization (EM) Converges for General Agnostic Mixtures](https://mlsanity.com/paper/2604.05842/) (2026)

## Abstract (arXiv)

The Expectation-Maximization algorithm is perhaps the most broadly used algorithm for inference of latent variable problems. A theoretical understanding of its performance, however, largely remains lacking. Recent results established that EM enjoys global convergence for Gaussian Mixture Models. For Mixed Linear Regression, however, only local convergence results have been established, and those only for the high SNR regime. We show here that EM converges for mixed linear regression with two components (it is known that it may fail to converge for three or more), and moreover that this convergence holds for random initialization. Our analysis reveals that EM exhibits very different behavior in Mixed Linear Regression from its behavior in Gaussian Mixture Models, and hence our proofs require the development of several new ideas.