mlsanityData to 7 Oct 2026

Learning Mixtures of Linear Regressions with Nearly Optimal Complexity

arXiv 1802.07895 ↗First posted 22 Feb 2018cs.LGcited by 37

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year

Citing papers per year: 2021: 4; 2022: 9; 2023: 15; 2024: 5; 2025: 4.

37 papers.

Sort:

By area:

  1. 2021Statistical Query Lower Bounds for List-Decodable Linear Regressioncited by 25
  2. 2022Towards Sample-efficient Overparameterized Meta-learningcited by 21
  3. 2024Provably learning a multi-head attention layercited by 21
  4. 2022Learning Mixtures of Linear Dynamical Systemscited by 15
  5. 2023Transformers can optimally learn regression mixture modelscited by 15
  6. 2022On Learning Mixture of Linear Regressions in the Non-Realizable Settingcited by 10
  7. 2023Tensor Decompositions Meet Control Theory: Learning General Mixtures of Linear Dynamical Systemscited by 10
  8. 2022On the identifiability of mixtures of ranking modelscited by 7
  9. 2022What Makes A Good Fisherman? Linear Regression under Self-Selection Biascited by 7
  10. 2023Statistical-Computational Tradeoffs in Mixed Sparse Linear Regressioncited by 7
  11. 2024Multi-Model 3D Registration: Finding Multiple Moving Objects in Cluttered Point Cloudscited by 7
  12. 2022Global Convergence of Federated Learning for Mixed Regressioncited by 6
25 more
  1. 2021Uniform Consistency in Nonparametric Mixture Modelscited by 5
  2. 2022Efficient List-Decodable Regression using Batchescited by 5
  3. 2023Non-Clashing Teaching Maps for Balls in Graphscited by 5
  4. 2024Implicit High-Order Moment Tensor Estimation and Learning Latent Variable Modelscited by 5
  5. 2022Bayesian Active Learning for Discrete Latent Variable Modelscited by 4
  6. 2023SQ Lower Bounds for Learning Mixtures of Linear Classifierscited by 4
  7. 2023Imbalanced Mixed Linear Regressioncited by 3
  8. 2023Mixed Regression via Approximate Message Passingcited by 3
  9. 2023A Parameterized Theory of PAC Learningcited by 3
  10. 2023Linear Regression using Heterogeneous Data Batchescited by 3
  11. 2021Sample Efficient Subspace-based Representations for Nonlinear Meta-Learningcited by 2
  12. 2022Support Recovery in Mixture Models with Sparse Parameterscited by 2
  13. 2025The Computational Complexity of Positive Non-Clashing Teaching in Graphscited by 2
  14. 2025Learning and Generalization with Mixture Datacited by 2
  15. 2021Multiple Support Recovery Using Very Few Measurements Per Samplecited by 1
  16. 2023Sharp analysis of EM for learning mixtures of pairwise differencescited by 1
  17. 2023EM for Mixture of Linear Regression with Clustered Datacited by 1
  18. 2023Global Convergence of Online Identification for Mixed Linear Regressioncited by 1
  19. 2024Agnostic Learning of Mixed Linear Regressions with EM and AM Algorithmscited by 1
  20. 2024Finite Sample Analysis of Tensor Decomposition for Learning Mixtures of Linear Systemscited by 1
  21. 2025Multi-convex Programming for Discrete Latent Factor Models Prototypingcited by 1
  22. 2023On the robust learning mixtures of linear regressionscited by 0
  23. 2023Clustered Linear Contextual Bandits with Knapsackscited by 0
  24. 2023Estimation of Models with Limited Data by Leveraging Shared Structurecited by 0
  25. 2025Learning Mixtures of Linear Dynamical Systems via Hybrid Tensor-EM Methodcited by 0