# Learning Mixtures of Linear Regressions with Nearly Optimal Complexity

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

## Key facts

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

## Built on by (most cited first, 30 of 37)

- [Statistical Query Lower Bounds for List-Decodable Linear Regression](https://mlsanity.com/paper/2106.09689/) (2021)
- [Provably learning a multi-head attention layer](https://mlsanity.com/paper/2402.04084/) (2024)
- [Towards Sample-efficient Overparameterized Meta-learning](https://mlsanity.com/paper/2201.06142/) (2022)
- [Learning Mixtures of Linear Dynamical Systems](https://mlsanity.com/paper/2201.11211/) (2022)
- [Transformers can optimally learn regression mixture models](https://mlsanity.com/paper/2311.08362/) (2023)
- [On Learning Mixture of Linear Regressions in the Non-Realizable Setting](https://mlsanity.com/paper/2205.13166/) (2022)
- [Tensor Decompositions Meet Control Theory: Learning General Mixtures of Linear Dynamical Systems](https://mlsanity.com/paper/2307.06538/) (2023)
- [On the identifiability of mixtures of ranking models](https://mlsanity.com/paper/2201.13132/) (2022)
- [What Makes A Good Fisherman? Linear Regression under Self-Selection Bias](https://mlsanity.com/paper/2205.03246/) (2022)
- [Statistical-Computational Tradeoffs in Mixed Sparse Linear Regression](https://mlsanity.com/paper/2303.02118/) (2023)
- [Multi-Model 3D Registration: Finding Multiple Moving Objects in Cluttered Point Clouds](https://mlsanity.com/paper/2402.10865/) (2024)
- [Global Convergence of Federated Learning for Mixed Regression](https://mlsanity.com/paper/2206.07279/) (2022)
- [Non-Clashing Teaching Maps for Balls in Graphs](https://mlsanity.com/paper/2309.02876/) (2023)
- [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)
- [Efficient List-Decodable Regression using Batches](https://mlsanity.com/paper/2211.12743/) (2022)
- [Bayesian Active Learning for Discrete Latent Variable Models](https://mlsanity.com/paper/2202.13426/) (2022)
- [SQ Lower Bounds for Learning Mixtures of Linear Classifiers](https://mlsanity.com/paper/2310.11876/) (2023)
- [Imbalanced Mixed Linear Regression](https://mlsanity.com/paper/2301.12559/) (2023)
- [Mixed Regression via Approximate Message Passing](https://mlsanity.com/paper/2304.02229/) (2023)
- [A Parameterized Theory of PAC Learning](https://mlsanity.com/paper/2304.14058/) (2023)
- [Linear Regression using Heterogeneous Data Batches](https://mlsanity.com/paper/2309.01973/) (2023)
- [The Computational Complexity of Positive Non-Clashing Teaching in Graphs](https://mlsanity.com/paper/2503.07665/) (2025)
- [Sample Efficient Subspace-based Representations for Nonlinear Meta-Learning](https://mlsanity.com/paper/2102.07206/) (2021)
- [Support Recovery in Mixture Models with Sparse Parameters](https://mlsanity.com/paper/2202.11940/) (2022)
- [Sharp analysis of EM for learning mixtures of pairwise differences](https://mlsanity.com/paper/2302.10066/) (2023)
- [Learning and Generalization with Mixture Data](https://mlsanity.com/paper/2504.20651/) (2025)
- [Multiple Support Recovery Using Very Few Measurements Per Sample](https://mlsanity.com/paper/2105.09855/) (2021)
- [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)

## Abstract (arXiv)

Mixtures of Linear Regressions (MLR) is an important mixture model with many applications. In this model, each observation is generated from one of the several unknown linear regression components, where the identity of the generated component is also unknown. Previous works either assume strong assumptions on the data distribution or have high complexity. This paper proposes a fixed parameter tractable algorithm for the problem under general conditions, which achieves global convergence and the sample complexity scales nearly linearly in the dimension. In particular, different from previous works that require the data to be from the standard Gaussian, the algorithm allows the data from Gaussians with different covariances. When the conditional number of the covariances and the number of components are fixed, the algorithm has nearly optimal sample complexity N = tildeO(d) as well as nearly optimal computational complexity tildeO(Nd), where d is the dimension of the data space. To the best of our knowledge, this approach provides the first such recovery guarantee for this general setting.