# Robust machine learning by median-of-means : theory and practice

#####
*schedule*
le mardi 10 avril 2018 de 10h45 à 11h45

**Organisé par :**Castillo, Fischer, Giulini, Gribkova, Levrard, Roquain, Sangnier

**Intervenant :**Guillaume Lecué (CNRS, ENSAE)

**Lieu :**UPMC, salle 15-16.201

**Sujet :**Robust machine learning by median-of-means : theory and practice

**Résumé :**

We introduce new estimators of least-squares minimizers based on median-of-means (MOM) estimators of the mean of real valued random variables. These estimators achieve optimal rates of convergence under minimal assumptions on the dataset. The dataset may also have been corrupted by outliers on which no assumption is granted. We also analyze these new estimators with standard tools from robust statistics. In particular, we revisit the concept of breakdown point. We modify the original definition by studying the number of outliers that a dataset can contain without deteriorating the estimation properties of a given estimator. This new notion of breakdown number, that takes into account the statistical performances of the estimators, is non-asymptotic in nature and adapted for machine learning purposes. We proved that the breakdown number of our estimator is of the order of (number of observations) * (rate of convergence). For instance, the breakdown number of our estimators for the problem of estimation of a d-dimensional vector with a noise variance sigma^2 is sigma^2d and it becomes sigma^2 s \log(ed/s) when this vector has only s non-zero component. Beyond this breakdown point, we proved that the rate of convergence achieved by our estimator is (number of outliers divided by (number of observations).

Besides these theoretical guarantees, the major
improvement brought by these new estimators is that they are
easily computable in practice and are therefore well suited
for robust machine learning. In fact, basically any algorithm
used to approximate the standard Empirical Risk Minimizer (or
its regularized versions) has a robust version approximating
our estimators. On top of being robust to outliers, the ``MOM
version" of the algorithms are even faster than the original
ones, less demanding in memory resources in some situations
and well adapted for distributed datasets which makes it
particularly attractive for large dataset analysis. As a proof
of concept, we study many algorithms for the classical LASSO
estimator. It turns out that a first version of our algorithm
can be improved a lot in practice by randomizing the blocks on
which ``local means" are computed at each step of the descent
algorithm. A byproduct of this modification is that our
algorithms come with a measure of depth of data that can be
used to detect outliers, which is another major issue in
Machine learning.

Joint work with Matthieu Lerasle