# Alternating Minimization Converges Super-Linearly for Mixed Linear Regression

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

## Key facts

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

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

- [On Learning Mixture of Linear Regressions in the Non-Realizable Setting](https://mlsanity.com/paper/2205.13166/) (2022)
- [Convergence and Recovery Guarantees of the K-Subspaces Method for Subspace Clustering](https://mlsanity.com/paper/2206.05553/) (2022)
- [Equivariance Allows Handling Multiple Nuisance Variables When Analyzing Pooled Neuroimaging Datasets](https://mlsanity.com/paper/2203.15234/) (2022)
- [Statistical-Computational Tradeoffs in Mixed Sparse Linear Regression](https://mlsanity.com/paper/2303.02118/) (2023)
- [Sparse Mixed Linear Regression with Guarantees: Taming an Intractable Problem with Invex Relaxation](https://mlsanity.com/paper/2206.01167/) (2022)
- [Imbalanced Mixed Linear Regression](https://mlsanity.com/paper/2301.12559/) (2023)
- [Mixed Regression via Approximate Message Passing](https://mlsanity.com/paper/2304.02229/) (2023)
- [Asymptotic Dynamics of Alternating Minimization for Bilinear Regression](https://mlsanity.com/paper/2402.04751/) (2024)
- [Learning and Generalization with Mixture Data](https://mlsanity.com/paper/2504.20651/) (2025)
- [EM for Mixture of Linear Regression with Clustered Data](https://mlsanity.com/paper/2308.11518/) (2023)
- [Agnostic Learning of Mixed Linear Regressions with EM and AM Algorithms](https://mlsanity.com/paper/2406.01149/) (2024)
- [Expectation Maximization (EM) Converges for General Agnostic Mixtures](https://mlsanity.com/paper/2604.05842/) (2026)

## Abstract (arXiv)

We address the problem of solving mixed random linear equations. We have unlabeled observations coming from multiple linear regressions, and each observation corresponds to exactly one of the regression models. The goal is to learn the linear regressors from the observations. Classically, Alternating Minimization (AM) (which is a variant of Expectation Maximization (EM)) is used to solve this problem. AM iteratively alternates between the estimation of labels and solving the regression problems with the estimated labels. Empirically, it is observed that, for a large variety of non-convex problems including mixed linear regression, AM converges at a much faster rate compared to gradient based algorithms. However, the existing theory suggests similar rate of convergence for AM and gradient based methods, failing to capture this empirical behavior. In this paper, we close this gap between theory and practice for the special case of a mixture of 2 linear regressions. We show that, provided initialized properly, AM enjoys a super-linear rate of convergence in certain parameter regimes. To the best of our knowledge, this is the first work that theoretically establishes such rate for AM. Hence, if we want to recover the unknown regressors upto an error (in ℓ2 norm) of ε, AM only takes O(log log (1/ε)) iterations. Furthermore, we compare AM with a gradient based heuristic algorithm empirically and show that AM dominates in iteration complexity as well as wall-clock time.