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 [PSBR20], a firstorder method using biased gradient queries, or the Sever framework of [DKK+19], 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.