# Iterative Least Trimmed Squares for Mixed Linear Regression

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Feb 2019.

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

- [Rank-based Decomposable Losses in Machine Learning: A Survey](https://mlsanity.com/paper/2207.08768/) (2022)
- [On Learning Mixture of Linear Regressions in the Non-Realizable Setting](https://mlsanity.com/paper/2205.13166/) (2022)
- [Statistical-Computational Tradeoffs in Mixed Sparse Linear Regression](https://mlsanity.com/paper/2303.02118/) (2023)
- [Insufficient Statistics Perturbation: Stable Estimators for Private Least Squares](https://mlsanity.com/paper/2404.15409/) (2024)
- [Support Recovery of Sparse Signals from a Mixture of Linear Measurements](https://mlsanity.com/paper/2106.05951/) (2021)
- [Trimmed Maximum Likelihood Estimation for Robust Learning in Generalized Linear Models](https://mlsanity.com/paper/2206.04777/) (2022)
- [Imbalanced Mixed Linear Regression](https://mlsanity.com/paper/2301.12559/) (2023)
- [Mixed Regression via Approximate Message Passing](https://mlsanity.com/paper/2304.02229/) (2023)
- [Outlier detection in regression: conic quadratic formulations](https://mlsanity.com/paper/2307.05975/) (2023)
- [Efficient Algorithms for Estimating the Parameters of Mixed Linear Regression Models](https://mlsanity.com/paper/2105.05953/) (2021)
- [Agnostic Learning of Mixed Linear Regressions with EM and AM Algorithms](https://mlsanity.com/paper/2406.01149/) (2024)
- [Computation of Least Trimmed Squares: A Branch-and-Bound framework with Hyperplane Arrangement Enhancements](https://mlsanity.com/paper/2604.11584/) (2026)
- [Expectation Maximization (EM) Converges for General Agnostic Mixtures](https://mlsanity.com/paper/2604.05842/) (2026)

## Abstract (arXiv)

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.