Localization methods with applications to robust learning and interpolation.

Summary This PhD thesis is focused on supervised learning. The main objective is the use of localization methods to obtain fast convergence speeds, i.e., speeds of the order O(1/n), where n is the number of observations. These speeds are not always achievable. It is necessary to impose constraints on the variance of the problem such as a Bernstein or margin condition. In particular, in this thesis we try to establish fast convergence speeds for robustness and interpolation problems. An estimator is said to be robust if it presents certain theoretical guarantees, under the least possible assumptions. This robustness problem is becoming more and more popular. The main reason is that in the current era of "big data", data are very often corrupted. Thus, building reliable estimators in this situation is essential. In this thesis we show that the famous (regularized) empirical risk minimizer associated with a Lipschitz loss function is robust to heavy-tailed noise and outliers in the labels. However, if the class of predictors is heavy-tailed, this estimator is not reliable. In this case, we build estimators called minmax-MOM estimator, optimal when the data are heavy-tailed and possibly corrupted.In statistical learning, we say that an estimator interpolates, when it predicts perfectly on a training set. In high dimension, some estimators interpolating the data can be good. In particular, in this thesis we study the linear Gaussian model in high dimension and show that the estimator interpolating the smallest norm data is consistent and even reaches fast speeds.