Agnostic Learning of Mixed Linear Regressions with EM and AM Algorithms
Not on the map. Why?
Abstract (arXiv)
Mixed linear regression is a well-studied problem in parametric statistics and machine learning. Given a set of samples, tuples of covariates and labels, the task of mixed linear regression is to find a small list of linear relationships that best fit the samples. Usually it is assumed that the label is generated stochastically by randomly selecting one of two or more linear functions, applying this chosen function to the covariates, and potentially introducing noise to the result. In that situation, the objective is to estimate the ground-truth linear functions up to some parameter error. The popular expectation maximization (EM) and alternating minimization (AM) algorithms have been previously analyzed for this. In this paper, we consider the more general problem of agnostic learning of mixed linear regression from samples, without such generative models. In particular, we show that the AM and EM algorithms, under standard conditions of separability and good initialization, lead to agnostic learning in mixed linear regression by converging to the population loss minimizers, for suitably defined loss functions. In some sense, this shows the strength of AM and EM algorithms that converges to ``optimal solutions'' even in the absence of realizable generative models.
Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Builds on 20 of its 32 references that are in the map. First posted on arXiv 3 Jun 2024.
Builds on
20 of 32 references.
References · 20
- 2020An Efficient Framework for Clustered Federated Learningcited by 511
- 2017On the Properties of the Softmax Function with Application in Game Theory and Reinforcement Learningcited by 142
- 2014Statistical guarantees for the EM algorithm: From population to sample-based analysiscited by 133
- 2018Gradient Descent with Random Initialization: Fast Global Convergence for Nonconvex Phase Retrievalcited by 71
- 2013Phase Retrieval using Alternating Minimizationcited by 58
- 2018Learning Mixtures of Linear Regressions with Nearly Optimal Complexitycited by 37
- 2016Solving a Mixture of Many Random Linear Equations by Tensor Decomposition and Alternating Minimizationcited by 26
- 2018Global Convergence of EM Algorithm for Mixtures of Two Component Linear Regressioncited by 25
- 2013Spectral Experts for Estimating Mixtures of Linear Regressionscited by 22
- 2013Faster and Sample Near-Optimal Algorithms for Proper Learning Mixtures of Gaussianscited by 20
- 2017Estimating the Coefficients of a Mixture of Two Linear Regressions by Expectation Maximizationcited by 19
- 2016Phase retrieval with random Gaussian sensing vectors by alternating projectionscited by 15
8 more
- 2019Max-Affine Regression: Provable, Tractable, and Near-Optimal Statistical Estimationcited by 15
- 2019Iterative Least Trimmed Squares for Mixed Linear Regressioncited by 13
- 2020Alternating Minimization Converges Super-Linearly for Mixed Linear Regressioncited by 12
- 2021Sharp global convergence guarantees for iterative nonconvex optimization: A Gaussian process perspectivecited by 10
- 2022On Learning Mixture of Linear Regressions in the Non-Realizable Settingcited by 10
- 2019Sample Complexity of Learning Mixtures of Sparse Linear Regressionscited by 7
- 2020Recovery of Sparse Signals from a Mixture of Linear Samplescited by 6
- 2021Support Recovery of Sparse Signals from a Mixture of Linear Measurementscited by 6
Built on by
Citing papers per year: 2026: 1.
1 paper.