Online Robust Regression via SGD on the l1 loss
  We consider the robust linear regression problem in the online setting where
we have access to the data in a streaming manner, one data point after the
other. More specifically, for a true parameter $\theta^*$, we consider the
corrupted Gaussian linear model $y = \langle x , \ \theta^* \rangle +
\varepsilon + b$ where the adversarial noise $b$ can take any value with
probability $\eta$ and equals zero otherwise. We consider this adversary to be
oblivious (i.e., $b$ independent of the data) since this is the only
contamination model under which consistency is possible. Current algorithms
rely on having the whole data at hand in order to identify and remove the
outliers. In contrast, we show in this work that stochastic gradient descent on
the $\ell_1$ loss converges to the true parameter vector at a $\tilde{O}( 1 /
(1 - \eta)^2 n )$ rate which is independent of the values of the contaminated
measurements. Our proof relies on the elegant smoothing of the non-smooth
$\ell_1$ loss by the Gaussian data and a classical non-asymptotic analysis of
Polyak-Ruppert averaged SGD. In addition, we provide experimental evidence of
the efficiency of this simple and highly scalable algorithm.
