  This paper considers the problem of supervised learning with linear methods
when both features and labels can be corrupted, either in the form of heavy
tailed data and/or corrupted rows. We introduce a combination of coordinate
gradient descent as a learning algorithm together with robust estimators of the
partial derivatives. This leads to robust statistical learning methods that
have a numerical complexity nearly identical to non-robust ones based on
empirical risk minimization. The main idea is simple: while robust learning
with gradient descent requires the computational cost of robustly estimating
the whole gradient to update all parameters, a parameter can be updated
immediately using a robust estimator of a single partial derivative in
coordinate gradient descent. We prove upper bounds on the generalization error
of the algorithms derived from this idea, that control both the optimization
and statistical errors with and without a strong convexity assumption of the
risk. Finally, we propose an efficient implementation of this approach in a new
python library called linlearn, and demonstrate through extensive numerical
experiments that our approach introduces a new interesting compromise between
robustness, statistical performance and numerical efficiency for this problem.
