Robust Regression Revisited: Acceleration and Improved Estimation Rates
  We study fast algorithms for statistical regression problems under the strong
contamination model, where the goal is to approximately optimize a generalized
linear model (GLM) given adversarially corrupted samples. Prior works in this
line of research were based on the robust gradient descent framework of Prasad
et. al., a first-order method using biased gradient queries, or the Sever
framework of Diakonikolas et. al., an iterative outlier-removal method calling
a stationary point finder.
  We present nearly-linear time algorithms for robust regression problems with
improved runtime or estimation guarantees compared to the state-of-the-art. For
the general case of smooth GLMs (e.g. logistic regression), we show that the
robust gradient descent framework of Prasad et. al. can be accelerated, and
show our algorithm extends to optimizing the Moreau envelopes of Lipschitz GLMs
(e.g. support vector machines), answering several open questions in the
literature.
  For the well-studied case of robust linear regression, we present an
alternative approach obtaining improved estimation rates over prior
nearly-linear time algorithms. Interestingly, our method starts with an
identifiability proof introduced in the context of the sum-of-squares algorithm
of Bakshi and Prasad, which achieved optimal error rates while requiring large
polynomial runtime and sample complexity. We reinterpret their proof within the
Sever framework and obtain a dramatically faster and more sample-efficient
algorithm under fewer distributional assumptions.
