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 \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 l1 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.