Iterative Least Trimmed Squares for Mixed Linear Regression
  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.
