# Learning Mixtures of Linear Regressions in Subexponential Time via Fourier Moments

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

## Key facts

- Cited by 26 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Dec 2019.

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

- [Statistical Query Lower Bounds for List-Decodable Linear Regression](https://mlsanity.com/paper/2106.09689/) (2021)
- [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)
- [Tensor Decompositions Meet Control Theory: Learning General Mixtures of Linear Dynamical Systems](https://mlsanity.com/paper/2307.06538/) (2023)
- [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)
- [Implicit High-Order Moment Tensor Estimation and Learning Latent Variable Models](https://mlsanity.com/paper/2411.15669/) (2024)
- [A Fourier Approach to Mixture Learning](https://mlsanity.com/paper/2210.02415/) (2022)
- [Efficient List-Decodable Regression using Batches](https://mlsanity.com/paper/2211.12743/) (2022)
- [SQ Lower Bounds for Learning Mixtures of Linear Classifiers](https://mlsanity.com/paper/2310.11876/) (2023)
- [Efficient Certificates of Anti-Concentration Beyond Gaussians](https://mlsanity.com/paper/2405.15084/) (2024)
- [Imbalanced Mixed Linear Regression](https://mlsanity.com/paper/2301.12559/) (2023)
- [Mixed Regression via Approximate Message Passing](https://mlsanity.com/paper/2304.02229/) (2023)
- [Linear Regression using Heterogeneous Data Batches](https://mlsanity.com/paper/2309.01973/) (2023)
- [Sample Efficient Subspace-based Representations for Nonlinear Meta-Learning](https://mlsanity.com/paper/2102.07206/) (2021)
- [Multiple Support Recovery Using Very Few Measurements Per Sample](https://mlsanity.com/paper/2105.09855/) (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)
- [In-context Learning for Mixture of Linear Regressions: Existence, Generalization and Training Dynamics](https://mlsanity.com/paper/2410.14183/) (2024)
- [Learning Mixture Models via Efficient High-dimensional Sparse Fourier Transforms](https://mlsanity.com/paper/2601.05157/) (2026)
- [On the robust learning mixtures of linear regressions](https://mlsanity.com/paper/2305.15317/) (2023)
- [Clustered Linear Contextual Bandits with Knapsacks](https://mlsanity.com/paper/2308.10722/) (2023)
- [Sample-Efficient Linear Regression with Self-Selection Bias](https://mlsanity.com/paper/2402.14229/) (2024)
- [Batch List-Decodable Linear Regression via Higher Moments](https://mlsanity.com/paper/2503.09802/) (2025)
- [Which Coauthor Should I Nominate in My 99 ICLR Submissions? A Mathematical Analysis of the ICLR 2026 Reciprocal Reviewer Nomination Policy](https://mlsanity.com/paper/2512.17950/) (2025)

## Abstract (arXiv)

We consider the problem of learning a mixture of linear regressions (MLRs). An MLR is specified by k nonnegative mixing weights p1, ldots, pk summing to 1, and k unknown regressors w1,...,wk∈ℝd. A sample from the MLR is drawn by sampling i with probability pi, then outputting (x, y) where y = langle x, wi rangle + η, where η~N(0,varsigma2) for noise rate varsigma. Mixtures of linear regressions are a popular generative model and have been studied extensively in machine learning and theoretical computer science. However, all previous algorithms for learning the parameters of an MLR require running time and sample complexity scaling exponentially with k. In this paper, we give the first algorithm for learning an MLR that runs in time which is sub-exponential in k. Specifically, we give an algorithm which runs in time widetildeO(d)·exp(widetildeO(√k)) and outputs the parameters of the MLR to high accuracy, even in the presence of nontrivial regression noise. We demonstrate a new method that we call "Fourier moment descent" which uses univariate density estimation and low-degree moments of the Fourier transform of suitable univariate projections of the MLR to iteratively refine our estimate of the parameters. To the best of our knowledge, these techniques have never been used in the context of high dimensional distribution learning, and may be of independent interest. We also show that our techniques can be used to give a sub-exponential time algorithm for learning mixtures of hyperplanes, a natural hard instance of the subspace clustering problem.