Iterative Least Trimmed Squares for Mixed Linear Regression
arXiv:1902.03653
Abstract
Given a linear regression setting, Iterative Least Trimmed Squares (ILTS) involves alternating between (a) selecting the subset of samples with lowest current loss, and (b) re-fitting the linear model only on that subset. Both steps are very fast and simple. In this paper we analyze ILTS in the setting of mixed linear regression with corruptions (MLR-C). We first establish deterministic conditions (on the features etc.) under which the ILTS iterate converges linearly to the closest mixture component. We also provide a global algorithm that uses ILTS as a subroutine, to fully solve mixed linear regressions with corruptions. We then evaluate it for the widely studied setting of isotropic Gaussian features, and establish that we match or better existing results in terms of sample complexity. Finally, we provide an ODE analysis for a gradient-descent variant of ILTS that has optimal time complexity. Our results provide initial theoretical evidence that iteratively fitting to the best subset of samples -- a potentially widely applicable idea -- can provably provide state of the art performance in bad training data settings.
arXiv commentAccepted by NeurIPS 2019
References in corpus (9)
- Sever: A Robust Meta-Algorithm for Stochastic Optimization
- Learning with Bad Training Data via Iterative Trimmed Loss Minimization
- Robust Regression via Hard Thresholding
- Alternating Minimization for Mixed Linear Regression
- Spectral Experts for Estimating Mixtures of Linear Regressions
- Global analysis of Expectation Maximization for mixtures of two Gaussians
- Local Maxima in the Likelihood of Gaussian Mixture Models: Structural Results and Algorithmic Consequences
- Solving a Mixture of Many Random Linear Equations by Tensor Decomposition and Alternating Minimization
- High Dimensional Robust Sparse Regression
Cited by in corpus (5)
- Max-Affine Regression: Provable, Tractable, and Near-Optimal Statistical Estimation
- Estimation, Confidence Intervals, and Large-Scale Hypotheses Testing for High-Dimensional Mixed Linear Regression
- Alternating Minimization Converges Super-Linearly for Mixed Linear Regression
- Efficient Algorithms for Estimating the Parameters of Mixed Linear Regression Models
- Support Recovery of Sparse Signals from a Mixture of Linear Measurements