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

Introduction

Recent technological developments have allowed companies and state organizations to collect and store huge datasets. These yield amazing achievements in artificial intelligence such as self driving cars or softwares defeating humans in highly complex games such as chess or Go. In fact, most big organizations have realized that data will have a major role in the future economy. Most companies in banks, electric or oil companies, etc. have a digital branch developing new data-based services for customers and new companies even build all their business on data collected on Twitter, Facebook or Google.

Big datasets have also challenged scientists in statistics and computer science to develop new methods. In particular, Machine Learning has attracted a lot of attention over the past few years. As explained in , machine learning can be seen as a branch of statistical learning dealing with large datasets where any procedure besides presenting optimal statistical guarantees should be provided with at least a tractable algorithm for its practical implementation. This new constraint raised several interesting problems while revisiting the classical learning theory of Vapnik . In particular, to name just a few, algorithms minimizing convex relaxations of the classical empirical $0-1$-risk counting the number of misclassification have been proposed and studied over the last few years. More generally, optimization algorithms are now routinely used and analyzed by statisticians.

Our theoretical understanding of many classical procedures of machine learning such as LASSO heavily rely on two assumptions on the data, that should both be i.i.d. and have subgaussian behaviors. As noted in , “data from real-world experiments oftentimes tend to be corrupted with outliers and/or exhibit heavy tails”. For example, in finance, heavy-tailed processes are routinely used and, in biology or medical experiments datasets are regularly subject to some corruption by outliers. These outliers are even in some applications the data of actual interests, one can think of fraud detections for example. The need for robust procedures in data science can be appreciated, for instance, by the recently posted challenges on “kaggle”, the most popular data science competition platform. The 1.5 million dollars problem “Passenger Screening Algorithm Challenge” is about to find terrorist activity from 3D images. The “NIPS 2017: Defense Against Adversarial Attack” is about constructing algorithms robust to adversarial data.

LASSO is not an isolated example, most algorithms are actually designed to approximate minimizers of penalized empirical loss and empirical means of unbounded functions are highly sensitive to corrupted data. In statistics, building robust estimators has been an issue for a long time at least since the work of John Tukey, Frank Hampel and Peter Huber. It has yield interesting “robust” alternatives to the standard maximum likelihood estimator, one can refer to for an overview on robust statistics and to Baraud, Birgé and Sart or Baraud and Birgé see also for deep new developments in robust statistics.

1.2 Resist or detect outliers : a raising challenge in ML

There are mainly two types of outliers in practice : those corrupting a dataset which are not interesting (outliers can appear in datasets due to storage issues, they can also be adversarial data as fake news, false declarative data, etc.) and those that are rare but important observations like frauds, terrorist activities, tumors in medical images,… A famous example of the latter type of “outlier” discovered unexpectedly was the ozone hole [62, p.2]. In the former case, the challenge is to construct predictions as sharp as if the dataset was clean and in the latter, the main question is to detect outliers.

Of course, any dataset is preprocessed to be “cleaned” from outliers. This step, called “data jujitsu”, “data massage”, “data wrangling” or “data munging” usually takes $80\%$ of data scientists time. It requires an important quantity of expertise to guide data scientists . Some platforms like “Amazon mechanical turk” allow to preprocess collectively datasets with millions of lines. Even when done with maximal care, some contamination always affect modern datasets, because outliers are particularly hard to detect in high dimension and because the distinction between outliers and informative data is often delicate in practice.

2 Robustness : state of the art

The book traces back the origins of robust statistics to the fundamental works of John Tukey , Peter Huber and Frank Hampel . Tukey asked the following question for the location problem of a Gaussian distribution “what happens if the distribution slightly deviates from the normal distribution?”. Tukey’s 1960 example shows the dramatic lack of distributional robustness of some classical procedures like Maximum Likelihood Estimator (MLE) [42, Example 1.1]. A related question was asked by Hodges about “tolerance to extreme values”.

In fact, one doesn’t define one robustness property in general. Estimation, prediction or more generally any statistical properties like consistency, asymptotic normality, minimax optimality, etc. require assumptions (cf. the “no free lunch theorem” ). Such assumptions are naturally questionable on real databases. What properties of an estimator pertain when one or several assumptions are not satisfied? As there are several types of assumptions, one can define several types of robustness. For example, Tukey’s question is about robustness to a misspecification of the Gaussian model while Hodges question can be understood as robustness to contamination of the dataset by large outliers or robustness to heavy-tailed distributions in the model that may have caused the appearance of large data.

satisfies for all $f:{\cal X}\to\left\{-1,1\right\}$ (where ${\cal X}$ is the space where the $X_{i}$ take their values and the $Y_{i}\in\{-1,1\}$)

If the fraction $|{\cal O}|/N$ is small enough, the ERM over a class ${\cal F}$ of functions from ${\cal X}$ to $\{-1,1\}$

performs theoretically as well as the ERM based only on the “good” data $(X_{i},Y_{i})_{i\in{\cal I}}$

which is statistically optimal in some problems . In that case, the number of outliers $|{\cal O}|$ has to be less than $N$ times the rate of convergence of $\widehat{f}_{{\cal I}}$ – this is a condition we will meet later for our estimators.

2.2 Robustness to heavy-tailed data

The Gaussian assumption on the noise $Y_{1}-f^{*}(X_{1})$ in statistics is usually weakened in learning theory to a subgaussian assumption (the $L_{p}$-moments of the noise are bounded by those of a Gaussian variable). This subgaussian assumption is already much more flexible and essentially allows to extend the use of least-squares estimators and their penalized versions to a much broader class of possible distributions for the noise. Going beyond the subgaussian assumption is in general way more technical. One way to proceed is to assume a subexponential assumption – random variables whose $L_{p}$ moments are smaller than those of an exponential variable– as in the Bernstein’s condition in . More recently, the subexponential assumption has also been relaxed into $L_{p}$-moment assumptions. Least-squares estimators have been studied as well as some modifications less sensitive to large data for instance in . It appears that the statistical properties of least-squares estimators are deteriorated when the noise satisfies weaker assumptions . A modification of the ERM based on Le Cam’s estimation by tests principle has also been considered in .

3 Robustness in regression

Most of the robustness literature of the 1980s was on the regression problem , [42, Section 7.12]. These methods make a distinction between the problem of robustness with respect to the outputs $(Y_{i})_{i=1}^{N}$ on one side and with respect to the inputs $(X_{i})_{i=1}^{N}$ on the other side [42, Chapter 7]. Outliers in the inputs remain extremely difficult to handle while many solutions have been proposed to deal with outliers in the outputs.

Even if some solutions have been proposed in particular cases, see for example , the problem of robustness with respect to outliers in the inputs $X_{1},\ldots,X_{N}$ (also called leverage points), has not been solved in general neither in theory nor in practice. In the book , a three steps approach is suggested to solve the robustness problem in regression

find routine methods when there are only few leverage points,

find analytical methods for identifying leverage points and, if possible, leverage groups.

In other words, suggest to make an important “datacleaning” step before any analysis for solving the leverage point problem. As already discussed, this may not be possible for nowadays large datasets. Therefore, designing procedures that can handle outliers such as leverage points is an important task that requires new ideas.

In statistics, an elegant solution to this issue (and many others) called $\rho$-estimators has recently been proposed. However, $\rho$-estimators do not provide a satisfying solution for learning issues since they require a statistical model (even if almost no assumption besides a controlled massiveness are required on this model), they are specifically built for the Hellinger loss (although they seem to work extremely well for other risk function in some special cases) and they remain far from being computable in general which is dead-end for Machine Learning.

3.2 Outliers in the outputs

Robust procedures can be analyzed under the assumption that “we can act as if the $x_{ij}$ are free of gross errors” [42, paragraph 3 in Section 7.3] ($x_{ij}$ being the $j$-th coordinate of $X_{i}$ for $i\in[N]$ and $j\in[d]$). In this approach, the square loss is replaced by a convex differentiable function $\rho$ and the estimator minimizes

If $\psi=\rho^{\prime}$, the estimator is also solution of the equation

Many alternative robust procedures can be found in the regression literature, among other, one can mention the least median of squared residual estimator and the least trimmed sum of squares estimator which minimizes the sum of the $N/2+1$ smallest squared residuals. Finally, introduced Least Median of Squares in regression which naturally extends the median estimator in the location problem :

Its computational complexity rises exponentially with $d$ [37, p.330], .

3.3 Other challenges

We discussed the problems of detecting outliers and resisting corruption of the inputs earlier. Besides these, robust statistic has left some interesting open questions that have to be addressed.

Most results in robust statistics are asymptotic but the asymptotic approach may be quite misleading : “ […] approaches based on asymptotics are treacherous, and it could be quite misleading to transfer insights gained from asymptotic variance theory or from infinitesimal approaches (gross error sensitivity and the like) by heuristics to leverage points with $h_{i}>0.2$” [42, p.189]. In other words, robustness issues ultimately have to be tackled from a non-asymptotic point of view. Again, $\rho$-estimators treat this issue from a statistical perspective but cannot be applied in our learning setting.

When designing robust strategies for ML, one should keep in mind that these should be computationally tractable. To the best of our knowledge, no estimator robust to outlier in the outputs nor any general learning procedure robust to heavy-tailed data can currently be used in a high dimensional learning problems. There is currently no available algorithm for high dimensional learning whose good statistical performance don’t break down in the presence of one outlier in the dataset.

4 Contributions

In this paper, we propose a new estimator of the learning function

This new estimator has minimax-optimal non-asymptotic risk bounds even when the dataset has been corrupted by outliers (that may have corrupted indifferently the inputs, the outputs or both of them) and when informative data (those that are not outliers) only satisfy somehow minimal assumptions relating their $L_{2}$ geometry on $F$ to that of $P$ (see Sections 1.4.1 and 3.1 for details). This estimator solves therefore all challenges related to outliers in the learning theory literature including “adversarial outliers” – which are data satisfying no assumptions – and “stochastic outliers” – which are informative data that may look like outliers because of some weak concentration properties due to heavy tail distributions.

We also show that our estimator can be used for ML purposes by providing several algorithms to compute proxies of our estimators and illustrate their performance in an extensive simulation study (see Section A). This opens several interesting conjectures for example, to study and compare theoretically convergence of these algorithms, and to automatically calibrate our estimators.

We propose the following setup that allows the presence of outliers and relax the standard i.i.d. setup. We assume that data are partitioned in two groups (unknown from the statistician), more precisely $\{1,\ldots,N\}={\cal O}\cup{\cal I}$, with ${\cal O}\cap{\cal I}=\emptyset$

data $(X_{i},Y_{i})_{i\in{\cal O}}$ (${\cal O}$ stands for “outliers”) are not assumed to be independent nor independent to the other ones $(X_{i},Y_{i})_{i\in{\cal I}}$, they may not be identically distributed, in fact nothing is required on these data; they can even be adversarial in the sense that may have been designed to make the learning task harder,

data $(X_{i},Y_{i})_{i\in{\cal I}}$ (called informative) are the only data on which we can rely on to solve our learning task. In what follows, we only need very weak assumptions on those data to make MOM estimators achieving optimal statistical properties. In particular, we will always assume that the informative data are independent.

As we allow the presence of outliers, our procedure will be in a sense robust to the i.d. (identically distributed) assumption. This robustness goes actually further, since even informative data won’t be assumed identically distributed. Instead, our procedure will be shown to work under the much weaker requirement that the distributions of $(X_{i},Y_{i})$ for all $i\in{\cal I}$ induce an equivalent $L_{2}$ metric over the class $F$ and equivalent covariance between functions in $F$ and the output. If various distributions have equivalent first and second moments for all functions $f\in F$, our estimators will exhibit the same optimal performance as if they were i.i.d. Gaussian with similar first and second moments on all $f\in F$. Our new assumption feels more natural than the usual i.i.d one as distributions inducing the same “risk geometry” on $F$ seem interesting to solve our learning task and any other higher moment assumption above $2$ seems unnatural. However, the standard ERM once again would fail to achieve this goal as the behavior of the supremum over subclasses of $F$ of the empirical process used to bound the risk of the ERM depends in general on higher moments of these distributions.

4.2 Quantifying robustness by breackdown point

The breakdown point of an estimator is the smallest proportion of corrupted observations necessary to push an estimator to infinity [28, p.1809], [42, p.279]. The notion has been introduced by Hampel in his 1968 Ph. D. thesis. In , the notion was revisited with the following non-asymptotic definition, see also . Let ${\cal D}_{{\cal I}}$ denote a dataset and let $T$ be an estimator. If there exists a strategic / malicious / adversarial choice of another dataset ${\cal D}_{{\cal O}}$ such that $T({\cal D}_{{\cal I}}\cup{\cal D}_{{\cal O}})-T({\cal D}_{{\cal I}})$ is arbitrarily large, the estimator is said to break down under the contamination fraction $|{\cal D}_{\cal O}|/(|{\cal D}_{\cal I}|+|{\cal D}_{\cal O}|)$. The Donoho-Hampel-Huber breakdown point $\epsilon^{*}(T,{\cal D}_{{\cal I}})$ is then defined as the smallest contamination fraction under which estimator $T$ breaks down:

For the estimation of the mean $\mu$ of a random variable from $N$ i.i.d. observations, the empirical mean can be made arbitrarily large by adding a single “bad” observation. The breakdown point of the empirical mean estimator is therefore $1/(N+1)$ and this is the worst possible value for an estimator. The empirical mean is not robust to outliers, it performs very poorly in corrupted environments. On the other hand, the empirical median has a breakdown value of $1/2$ for the location problem.

Among equivariant estimators, the common sense heuristic applies : “when more than half data are bad, one cannot learn from good ones” . In particular, among equivariant estimators, $1/2$ is the best possible breakdown point for an estimator and the empirical median is optimal from this perspective. When the parameter of interest belongs to a bounded set, one can adapt the definition of breakdown point as in the discussion papers of . Other generalization to quantile estimation can be found in .

4.3 A modified notion of breakdown point for ML

We introduce a new concept of breakdown point for Learning. The standard breakdown point (4) does not come with any estimation or prediction property. As already mentioned, this leads to consider restricted classes of estimators to study optimality from the breakdown point of view to avoid degenerate cases. Instead of imposing algebraic restrictions, our new definition focus on the risk of the procedures.

where $P_{X}$ denotes the marginal on ${\cal X}$ of $P$.

In words, the breakdown number is the minimal number of points one has to add to a dataset to break statistical performance of an estimator $T$. In this definition, the rate ${\cal R}$ one can achieve is of particular importance. Ultimately, we would like to take it as small as possible. To that end, recall the definition of a minimax rate of convergence.

The minimax accuracy ${\cal R}(\delta,F)$ is the smallest accuracy that can be achieved uniformly over $F$ with confidence $\delta$ by some estimator.

The minimax rate of convergence defined in Definition 2 is obtained in the “Gaussian model” (that is when the dataset is made of $N$ i.i.d. observations in the regression model with Gaussian design and Gaussian noise independent of the design) which is somehow the benchmark model in statistics in which one can derive minimax rates of convergence over $F$. We will therefore use the minimax rates obtained in this model as benchmark rates of convergence.

Using this new definition, one can be interested in various existence or optimality properties such as:

Given $0<\delta<1$, $C>0$, what is the largest set of sample distributions ${\cal P}_{\delta,C}$ where one can build estimators with accuracy $C{\cal R}(\delta,F)$ of the same order as in the Gaussian model ?

given $0<\delta<1$, ${\cal R}>{\cal R}(\delta,F)$ and ${\cal P}\subset{\cal P}_{\delta,C}$, is there some procedure $T$ such that $K^{*}_{\text{ML}}(T,N,{\cal R},\delta,{\cal P})>0$?

given $0<\delta<1$, ${\cal R}>{\cal R}(\delta,F)$ and ${\cal P}\subset{\cal P}_{\delta,C}$, how large can be $\sup_{T}K^{*}_{\text{ML}}(T,N,{\cal R},\delta,{\cal P})$? and is this maximum achievable by a computationally tractable estimator $T$?

Most recent theoretical works on robust learning approaches focus on the first question, showing that statistical optimality can actually be achieved over much broader classes of distributions than the Gaussian model, see for example. In this paper, we build on the approach introduced in where we proved that, for any $\delta$ smaller than $\exp(-CNr_{N}^{2})$, there exists estimators such that $K^{*}_{\text{ML}}(T,N,r_{N}^{2},\delta,{\cal P})\geqslant CNr_{N}^{2}$ where $r_{N}^{2}$ is the minimax rate of convergence in the Gaussian model for exponential deviation. It is for instance given by $r_{N}^{2}=\sigma^{2}d/N$ for the problem of estimation of a $d$-dimensional vector and $r_{N}^{2}=\sigma^{2}s\log(ed/s)/N$ when this vector has only $s$ non-zero coordinates. But we go further in this paper, showing that these performance can be achieved by a procedure that is computationally tractable, hence by a Machine Learning algorithm. This ultimate breakthrough is due to a new estimator that we shall now introduce.

4.4 Our estimators

The key equation to understand our procedure is that the target

can be obtained as the solution of the following minimaximization problem

This remark is obvious since the expectation operator is linear, it is fundamental though in our construction as we use non-linear estimators of the expectation. More precisely, unknown expectations are estimated by median-of-means (MOM) estimators : given a partition of the dataset into blocks of equal sizes, MOM is the median of the empirical means over each block, see Section 2.2 for details. MOM estimators are naturally more robust than the empirical mean thanks to the median step : if the number of blocks is at least twice that of the outliers, outliers can only affect less than half blocks so MOM remains an acceptable estimator of the mean. MOM’s estimators are non linear, therefore plugging a MOM estimator into the minimization problem doesn’t yield the same estimator as the plugging estimator on the minimaximization problem. More precisely, it is not so hard to see that MOM minimizers cannot achieve (fast) minimax rates ${\cal R}(\delta,F)$. This is why we focus in the following on the minimaximization problem

MOM estimators of the increments of criteria have already been used in . What is new here is that, instead of combining these estimators to build a “tournament” as in or using the approach of Le Cam as in , we simply plug these estimators in the minimaximization problem. Our construction is therefore extremely simplified compared to these previous papers, we’ll show that our new estimator achieves the same theoretical properties as these alternatives.

Then one can perform a descent/ascent algorithm over the block $B_{\text{med}}$ to get the next iteration $(f_{t+1},g_{t+1})$. In practice though, this basic idea can be substantially improved by shuffling the blocks at each time step, cf. Section A.8. The first advantage of this shuffling step is that the algorithm doesn’t converge to local minimaxima.

Furthermore, our algorithm defines a natural notion of depth of data : deep data are typically regularly chosen as member of the median block $B_{\text{med}}$ while “outliers” on the other hand are typically left aside. This notion of depth, based on the risk function, is natural in our learning framework and should probably be investigated more carefully in future works. It also suggests an empirical definition of outliers and therefore an outliers detection algorithm as a by-product.

The paper is organised as follow. Section 2 introduces formally the classical least-squares learning framework and presents our new estimator, Section 3 details our main theoretical results, that are proved in Section 4. An extended simulation study is provided in Section A, including the presentation of many robust versions of standard optimization algorithms. Theoretical abstract rates derived in the main results are particularized in Section B into important problems in Machine Learning to show the extent of our results. These main results focus on penalized version of the basic tests presented in this introduction that are well suited for high dimensional learning frameworks, we complete these results in Section C, providing results for the basic estimators without penalizations in small dimension. Finally, Section D provides some optimality results for our procedures.

Setting

For any $Q\in\{P,(P_{i})_{i\in[N]}\}$ and any $p\geqslant 1$, let $\left\|f\right\|_{L^{p}_{Q}}=(Q|f|^{p})^{1/p}$ the $L_{Q}^{p}$-norm of $f$ whenever it’s defined. Finally, let $\left\|\cdot\right\|$ be a norm defined on the span of $F$; $\left\|\cdot\right\|$ will be used as a regularization norm.

A key observation in our analysis is that $f^{*}$ is solution of a minimaximization problem:

The minimaximization point of view has been considered in and . These papers used bounded modification of the quadratic loss. As for classification, the impact of outliers on the empirical mean is negligible if the loss is bounded and the number of outliers controlled, which ensures robustness. The cost to pay is that the function to be minimized is not convex and is therefore hard to implement. The idea of estimation by aggregation of tests is due to Le Cam and was further developed by Birgé , Baraud , Baraud, Birgé and Sart . MOM estimators have been recently considered see and Section 2.2 for details. Nevertheless, to the best of our knowledge, this paper is the first to consider the estimators obtained by plugging MOM’s estimators in the minimaximization problem (6). This approach will proved to be efficient for designing algorithms.

2 MOM estimator

We will make an extensive use of empirical medians and quantiles in the following. We now precise some conventions used repeatedly hereafter. For all $\alpha\in(0,1)$ and real numbers $x_{1},\ldots,x_{K}$, we denote by

where in the last inequality we use the Minkowsky sum of two sets. More generally, inequalities involving empirical quantiles are always understood in the worst possible case. For example, one can check that, for all vectors $x$ and $y$

In the following, we will simply write with some abuse of notation that for all vectors $x$ and $y$:

Likewise, one can check that $Q_{1/2}(x-y)\leqslant Q_{3/4}(x)-Q_{1/4}(y)$ and $Q_{1/2}(x)\geqslant-Q_{1/2}(-x)$. Moreover, to prove that $Q_{\alpha}(x)\geqslant t$ it is enough to prove that $\exists J\subset[K],|J|\geqslant(1-\alpha)K,\forall k\in J,x_{k}\geqslant t$ and to prove that $Q_{\alpha}(x)\leqslant t$ it is enough to prove that $\exists J\subset[K],|J|\geqslant\alpha K,\forall k\in J,x_{k}\leqslant t$.

We conclude this section with the definition of MOM tests and their regularized versions.

and, for a given regularization parameter $\lambda\geqslant 0$, its regularized version is

3 Minimaximization of MOM tests

One can rewrite our estimators as cost minimization estimators

where for all $f\in F,$ {\cal C}_{K}\big{(}f\big{)}=\sup_{g\in F}T_{K}(g,f) and {\cal C}_{K,\lambda}\big{(}f\big{)}=\sup_{g\in F}T_{K,\lambda}(g,f). These cost functions play a central role in the theoretical analysis of $\hat{f}_{K}$ and $\hat{f}_{K,\lambda}$ (cf. Section 4).

Compared to the aggregation of tests by “tournaments” , or “Le Cam type” aggregation of tests , minimaximization estimators have several avantages. First they are very natural from Eq (6) and they do not require a proxy for the excess risk or for the $L^{2}(P)$-norm, which simplifies the presentation of this estimator. Finally, while building the estimators of or is totally impossible, these new estimators are minimaximization procedures of locally convex-concave functions that could be approximated by a numerical scheme. It is actually easy to “convert” most of the classical algorithms used for “cost minimization” into an algorithm for minimaximization solving (7) (see Section A below).

Assumptions and main results

Denote by ${\cal O}\cup{\cal I}$ a partition of $[N]$, where ${\cal O}$ has cardinality $|{\cal O}|$. Data $(X_{i},Y_{i})_{i\in{\cal O}}$ are considered as outliers, no assumptions on the joint distribution of these data or on their distribution conditionally on data $(X_{i},Y_{i})_{i\in{\cal I}}$ is made. These data may not be independent, nor independent from the remaining data. The remaining set $(X_{i},Y_{i})_{i\in{\cal I}}$ is the set of informative data, that is the ones one can use for estimation. These are hereafter assumed independent. Given the data $(X_{i},Y_{i})_{i\in[N]}$ no one knows in advance which data is informative or not.

All the assumptions we need to get the results involve only first and second moment of the distributions $P,(P_{i})_{i\in{\cal I}}$ on functions in $F$ and $Y$. In particular, this setting strongly relaxes usual strong concentration assumptions made on the informative data to study ERM estimators.

There exists $\theta_{r0}>0$ such that for all $f\in F$ and all $i\in{\cal I}$,

Of course, Assumption 1 holds in the i.i.d. framework, with $\theta_{r0}=1$ and ${\cal I}=[N]$. The second assumption bounds the correlation between the “noise” $\zeta_{i}=Y_{i}-f^{*}(X_{i})$ and the shifted class $F-f^{*}$.

There exists $\theta_{m}>0$ such that for all $i\in{\cal I}$ and all $f\in F$,

and so Assumption 2 holds for $\theta_{m}=\theta_{1}\theta_{2}$.

Now, let us introduce a norm equivalence assumption over $F-f^{*}$: we call it a $L^{2}/L^{1}$ assumption.

There exists $\theta_{0}\geqslant 1$ such that for all $f\in F$ and all $i\in{\cal I}$

Note that $\left\|f-f^{*}\right\|_{L^{1}_{P_{i}}}\leqslant\left\|f-f^{*}\right\|_{L^{2}_{P_{i}}}$ for all $f\in F$ and $i\in{\cal I}$. Therefore, Assumption 1 and Assumption 3 are together equivalent to assume that all the norms $L^{2}_{P},L_{P_{i}}^{2},L_{P_{i}}^{1},i\in{\cal I}$ are equivalent over $F-f^{*}$. Note also that Assumption 3 is equivalent to the small ball property (cf. ) which has been recently used in Learning theory and signal processing. We refer to for examples of distributions satisfying the small ball assumption.

Let $Z$ be a real-valued random variable. The following holds:

therefore, $p\geqslant(\theta_{0}^{-1}-\kappa_{0})^{2}$.

2 Complexity measures and minimax rates of convergence

Balls associated with the regularization norm $\left\|\cdot\right\|$ and the $L^{2}_{P}$ norm play a prominent role in learning theory . In particular, for all $\rho\geqslant 0$, the “sub-models”

where $B=\{f\in{\rm span}(F),\left\|f\right\|\leqslant\rho\}$ and their “localizations” at various level $r\geqslant 0$, i.e. intersection of $B(f^{*},\rho)$ with $L^{2}_{P}$-balls

are key sets because their Rademacher complexities, drives the minimax rates of convergence. Let us introduce these complexity measures.

Let $(\epsilon_{i})_{i\in[N]}$ be independent Rademacher random variables (i.e. uniformly distributed in $\{-1,1\}$), independent from $(X_{i},Y_{i})_{i=1}^{N}$. For all $f\in F$, $r>0$ and $\rho\in(0,+\infty]$, we denote the intersection of the $\left\|\cdot\right\|$-ball of radius $r$ and the $L^{2}_{P}$-norm of radius $\rho$ centered at $f$ by

Let $\zeta_{i}=Y_{i}-f^{*}(X_{i})$ for all $i\in{\cal I}$ and for $\gamma_{Q},\gamma_{M}>0$ define

and let $\rho\to r(\rho,\gamma_{Q},\gamma_{M})$ be a continuous and non decreasing function such that for every $\rho>0$,

It follows from Lemma 2.3 in that $r_{M}$ and $r_{Q}$ are continuous and non decreasing functions. Note that $r_{M}(\cdot),r_{Q}(\cdot)$ depend on $f^{*}$. According to , if one can choose $r(\rho)$ equal to the maximum of $r_{M}(\rho)$ and $r_{Q}(\rho)$ then $r(\rho)$ is the minimax rate of convergence over $B(f^{*},\rho)$. Note also that $r_{Q}$ and $r_{M}$ are well defined when ${\cal I}\geqslant N/2$, which implies that at least half data are informative.

3 The sparsity equation

To control the risk of our estimator, we bound from above $T_{K,\lambda}(f,f^{*})$ for all functions $f$ far from $f^{*}$ either in $L^{2}_{P}$-norm or for the regularization norm $\left\|\cdot\right\|$. Recall that

The multiplier term “$2\zeta(f-f^{*})$” is the one containing the noise and is therefore the term we will try to control from above using either the quadratic process “$(f-f^{*})^{2}$” or the regularization term “$\lambda(\left\|f^{*}\right\|-\left\|f\right\|)$”. To that end we will need both to control from below the quadratic process and the regularization term.

Let $f\in F$ and denote $\rho=\left\|f-f^{*}\right\|$. When $\|f-f^{*}\|_{L^{2}_{P}}$ is small, the quadratic term $(f-f^{*})^{2}$ will not help to bound from above $T_{K,\lambda}(f,f^{*})$, one shall only rely on the penalization term $\lambda(\left\|f^{*}\right\|-\left\|f\right\|)$. One can bound from below $\left\|f^{*}\right\|-\left\|f\right\|\gtrsim\rho$ for all $f$ close to $f^{*}$ in $L_{P}^{2}$ using the sparsity equation of . First, introduce the subdifferentials of $\left\|\cdot\right\|$ : for all $f\in F$,

where $(E^{*},\left\|\cdot\right\|^{*})$ is the dual normed space of $(E,\left\|\cdot\right\|)$.

For any $\rho>0$, let $H_{\rho}$ denote the set of functions “close” to $f^{*}$ in $L_{P}^{2}$ and at distance $\rho$ from $f^{*}$ in regularization norm and let $\Gamma_{f^{*}}(\rho)$ denote the set of subdifferentials of all vectors close to $f^{*}$:

If there exists a “sparse” $f^{**}$ in $\{f\in F:\left\|f^{*}-f\right\|\leqslant\rho/20\}$, that is $(\partial\left\|\cdot\right\|)_{f^{**}}$ is almost all the unit dual sphere, then $\left\|f\right\|-\left\|f^{**}\right\|$ is large for any $f\in H_{\rho}$ so $\left\|f\right\|-\left\|f^{*}\right\|\geqslant\left\|f\right\|-\left\|f^{**}\right\|-\left\|f^{*}-f^{**}\right\|$ is large as well. More precisely, let us introduce, for all $\rho>0$,

The sparsity equation, introduced in , quantifies these notions of “large”.

A radius $\rho>0$ is said to satisfy the sparsity equation when $\Delta(\rho)\geqslant 4\rho/5$.

One can check that, if $\rho^{*}$ satisfies the sparsity equation, so do all $\rho\geqslant\rho^{*}$. Therefore, one can define

Note that if $\rho\geqslant 20\left\|f^{*}\right\|$ then $0\in\Gamma_{f^{*}}(\rho)$. Moreover, $(\partial\left\|\cdot\right\|)_{0}$ equals to the dual ball (i.e. the unit ball of $(E^{*},\left\|\cdot\right\|^{*})$) and so $\Delta(\rho)=\rho$. This implies that any $\rho\geqslant 20\left\|f^{*}\right\|$ satisfies the sparsity equation. This simple observation will be used to get “complexity-dependent rates of convergence” as in .

4 Main results

Our first results study the performance of the estimators $\widehat{f}_{K,\lambda}$ for a fixed value of $K$. The other ones will provide an adaptive way to select $K$.

Grant Assumptions 1, 2 and 3 and let $r_{Q}$, $r_{M}$ denote the functions introduced in Definition 5. Assume that $N\geqslant 384(\theta_{0}\theta_{r0})^{2}$ and $|{\cal O}|\leqslant N/(768\theta_{0}^{2})$. Let $\rho^{*}$ be solution to the sparsity equation from Definition 6. Let $K^{*}$ denote the smallest integer such that

where $\epsilon=1/(833\theta_{0}^{2})$ and $r^{2}(\cdot)$ is defined in Definition 5 for $\gamma_{Q}=(384\theta_{0})^{-1}$ and $\gamma_{M}=\epsilon/192$. For any $K\geqslant K^{*}$, define the radius $\rho_{K}$ and the regularization parameter as

Assume that for every $i\in{\cal I}$, $K\in[\max(K^{*},|{\cal O}|),N]$ and $f\in F$ such that $\left\|f-f^{*}\right\|\leqslant\rho$ for $\rho\in[\rho_{K},2\rho_{K}]$, one has

Then, for all $K\in[\max(K^{*},8|{\cal O}|),N/(96(\theta_{0}\theta_{r0})^{2})]$, with probability larger than $1-4\exp(-7K/9216)$, the estimator ${\hat{f}}_{K,\lambda}$ defined in Section 2.3 satisfies

Assumption (8) holds for instance when for every $i\in{\cal I}$ and $f\in F$ one has

These assumptions involve second moments associated with $P$ and $(P_{i})_{i\in{\cal I}}$. As a consequence, if the metrics $L^{2}_{P_{i}}$ for $i\in{\cal I}$ and $L^{2}_{P}$ coincide on the functions $x\to(f-f^{*})(x)$ and $(x,y)\to y-f(x)$ and the $P_{i}$ satisfies Assumption 2 and 3 then Theorem 1 holds. This means that we only need informative data to induce the same $L^{2}$ metric as $P$ to estimate the oracle $f^{*}$ even if we do not have any observation coming from $P$ itself. This setup relaxes the classical i.i.d. where all data are generated from $P$. In this setting, our estimators achieve the same results as the ERM would if data were all i.i.d. with a noise $\zeta$ independent of $X$ and both $X$ and $\zeta$ had a Gaussian distribution (see Section D).

The function $r(\cdot)$ is used to define the regularization parameter, so it cannot depend on $f^{*}$. When $r_{M}(\cdot),r_{Q}(\cdot)$ depend on $f^{*}$, $r$ should be a computable upper bound independent from $f^{*}$.

In Theorem 1, all rates depend on the choice of the tuning parameter $K$. The following construction inspired from Lepski’s method provides an adaptive choice of this parameter. Let us first recall the definition of empirical criterion introduced in Section 2.3 and the associated confidence regions: for all $J\in[K]$, $\lambda>0$, $f\in F$ and absolute constant $c_{ad}>0$,

The following theorem shows the performance of these estimators.

Grant the assumptions of Theorem 1 and assume moreover that and $|{\cal O}|\leqslant N/(768\theta_{0}^{2}\theta_{r0}^{2})$. For any $K\in[\max(K^{*},8|{\cal O}|),N/(96(\theta_{0}\theta_{r0})^{2})]$, with probability larger than

where $c_{ad}=18/833$ and $\epsilon=(833\theta_{0}^{2})^{-1}$. In particular, for $K=K^{*}$, we have $r(2\rho_{K^{*}})=\max\left(r(2\rho^{*}),\sqrt{|{\cal O}|/N}\right)$. Therefore, if $r(2\rho^{*})\leqslant c_{1}r(\rho^{*})$ holds for some absolute constant $c_{1}$, then the breakdown number of $\widehat{f}_{c_{ad}}$ is larger than $Nr(\rho^{*})^{2}$.

Note that $r(\cdot)$ is any continuous, non decreasing function such that for all $\rho>0$, $r(\rho)\geqslant\max\left(r_{Q}(\rho,\gamma_{Q}),r_{M}(\rho,\gamma_{M})\right)$. In particular, if $r_{*}:\rho\to\max\left(r_{Q}(\rho,\gamma_{Q}),r_{M}(\rho,\gamma_{M})\right)$ is itself a continuous function (it is clearly non decreasing) then for every $x>0$, $r(\rho)=\max\left(r_{Q}(\rho,\gamma_{Q}),r_{M}(\rho,\gamma_{M})\right)+x/N$ is another non decreasing upper bound. Therefore, one can derive results similar to those in Theorem 2 but with an extra confidence parameter : for all $x>0$, with probability at least $1-4\exp(-c_{0}Nr_{*}^{2}(\rho_{K^{*}})+c_{0}x)$,

Note however that $\widehat{f}_{c_{ad}}$ depends on $x$ through the regularization parameter $\lambda=16\epsilon(r_{*}(\rho_{K})+x/N)/\rho_{K}$.

Proofs

Upper and lower bounds on $T_{K}(\cdot,\cdot)$ follow from a study of “quadratic” and “multiplier” quantiles of means processes. As no assumption is granted on the outliers, any block of data containing one or more of these outliers is “lost” from our perspective meaning that empirical means over these blocks cannot be controlled. Let ${\cal K}$ denote the set of blocks which have not been corrupted by outliers:

If $k\in{\cal K}$, all data indexed by $B_{k}$ are informative. We will show that controls on the blocks indexed by ${\cal K}$ are sufficient to insure statistical performance of MOM estimators.

The first result is a lower bound on the quantiles of means quadratic processes.

In particular, $Q_{\eta,K}((f-f^{*})^{2})\geqslant(4\theta_{0})^{-2}\left\|f-f^{*}\right\|^{2}_{L^{2}_{P}}$.

Define $F^{*}_{\rho}=B(f^{*},\rho)=\{f\in F:\left\|f-f^{*}\right\|\leqslant\rho\}$. For all $f\in F^{*}_{\rho}$, let $n_{f}=(f-f^{*})/\left\|f-f^{*}\right\|_{L^{2}_{P}}$ and note that for all $i\in{\cal I}$, $P_{i}|n_{f}|\geqslant\theta_{0}^{-1}$ by Assumption 3 and $P_{i}n_{f}^{2}\leqslant\theta_{r0}^{2}$ by Assumption 1. It follows from Markov’s inequality that, for all $k\in{\cal K}$ (${\cal K}$ is defined in (10)),

Since $K\leqslant N\alpha/(2\theta_{0}\theta_{r0})^{2}$, $|B_{k}|=N/K\geqslant(2\theta_{0}\theta_{r0})^{2}/\alpha$ and so

Denote ${\cal F}=\{f\in F:\left\|f-f^{*}\right\|\leqslant\rho,\;\left\|f-f^{*}\right\|_{L^{2}_{P}}\geqslant r_{Q}(\rho,\gamma_{Q})\}$. By the bounded difference inequality (see, for instance [17, Theorem 6.2]), there exists an event $\Omega_{Q}(K)$ with probability larger than $1-\exp(-x^{2}|{\cal K}|/2)$, on which, for all $f\in{\cal F}$,

Since the function $\phi$ is 1-Lipschitz and $\phi(0)=0$, by the contraction principle (see, for example [57, Chapter 4] or [17, Theorem 11.6]), we have

The family $(\epsilon_{[i]}|n_{f}(X_{i})|:i\in\cup_{k\in{\cal K}}B_{k})$, where $[i]=\lceil i/K\rceil$ for all $i\in{\cal I}$, is a collection of centered random variables. Therefore, if $(\epsilon^{\prime}_{k})_{k\in{\cal K}}$ and $(X_{i}^{\prime})_{i\in{\cal I}}$ denote independent copies of $(\epsilon_{k})_{k\in{\cal K}}$ and $(X_{i})_{i\in{\cal I}}$ then

Then, as $(X_{i})_{i\in{\cal I}}$ and $(X_{i}^{\prime})_{i\in{\cal I}}$ are two independent families of independent variables therefore, if $(\epsilon_{i}^{\prime\prime})_{i\in{\cal I}}$ denote a family of i.i.d. Rademacher variables independent of $(\epsilon_{i}),(\epsilon_{i}^{\prime}),(X_{i})_{i\in{\cal I}},(X_{i}^{\prime})_{i\in{\cal I}}$ then $(\epsilon_{k}|n_{f}(X_{i})|-\epsilon_{k}^{\prime}|n_{f}(X_{i}^{\prime})|)$ and $\left(\epsilon_{i}^{\prime\prime}\left(\epsilon_{k}|n_{f}(X_{i})|-\epsilon_{k}^{\prime}|n_{f}(X_{i}^{\prime})|\right)\right)$ have the same distribution. Therefore,

By the contraction principle, on $\Omega_{Q}(K)$,

For any $f\in{\cal F}$, $r_{Q}(\rho,\gamma_{Q})n_{f}+f^{*}\in F$ because $F$ is convex. Moreover, $\left\|r_{Q}(\rho,\gamma_{Q})n_{f}\right\|_{L^{2}_{P}}=r_{Q}(\rho,\gamma_{Q})$ and $\left\|r_{Q}(\rho,\gamma_{Q})n_{f}\right\|=[r_{Q}(\rho,\gamma_{Q})/\left\|f-f^{*}\right\|_{L^{2}_{P}}]\left\|f-f^{*}\right\|\leqslant\rho$. Therefore, $r_{Q}(\rho,\gamma_{Q})n_{f}+f^{*}\in{\cal F}$. Therefore, by definition of $r_{Q}(\rho,\gamma_{Q})$,

Using the last inequality together with (12) and the assumption $K\geqslant|{\cal O}|/(1-\gamma)$ (so that $|{\cal K}|\geqslant K-|{\cal O}|\geqslant\gamma K$), we get that, on the event $\Omega_{Q}(K)$, for any $f\in{\cal F}$,

Hence, on $\Omega_{Q}(K)$, for any $f\in{\cal F}$, there exists at least $(1-\eta)K$ blocks $B_{k}$ for which $P_{B_{k}}|n_{f}|\geqslant(4\theta_{0})^{-1}$. On these blocks, $P_{B_{k}}n_{f}^{2}\geqslant(P_{B_{k}}|n_{f}|)^{2}\geqslant(4\theta_{0})^{-2}$, therefore, on $\Omega_{Q}(K)$, $Q_{\eta,K}[n_{f}^{2}]\geqslant(4\theta_{0})^{-2}$.

Now, let us turn to a control of the multiplier process.

For all $k\in[K]$ and $f\in F$, set $W_{k}=((X_{i},Y_{i}))_{i\in B_{k}}$ and define

Let $f\in F$ and $k\in\mathcal{K}$. It follows from Markov’s inequality that

Let $J=\cup_{k\in\mathcal{K}}B_{k}$ and let $r_{M}(\rho)=r_{M}(\rho,\gamma_{M})$. We have

where in the last but one inequality, we used that the class $F$ is convex and the same argument as in the proof of Lemma 1. Since $(\epsilon_{[i]}(\zeta_{i}(f-f^{*})(X_{i})-P_{i}\zeta_{i}(f-f^{*})):i\in{\cal I})$ is a family of centered random variables, one can use the symmetrization argument to get

where the definition of $r_{M}(\rho)$ has been used in the last but one inequality.

where we used (4.1) in the last inequality.

Furthermore, it follows from by the symmetrization argument that

and, from the contraction principle and (4.1), that

In conclusion, on $\Omega_{M}(K)$, for all $f\in B(f^{*},\rho)$,

Let us first introduce the event on which the statement of Theorem 1 holds. Denote by $\Omega(K)$ the intersection of the events $\Omega_{Q}(K)$, $\Omega_{M}(K)$ defined respectively in Lemmas 1 and 2 for $\rho\in\{\kappa\rho_{K}:\kappa\in\{1,2\}\}$ and

for some absolute constants $c>0$ to be specified later. For these values, conditions in both Lemmas 1 and 2 are satisfied:

if $\left\|f-f^{*}\right\|_{L^{2}_{P}}\geqslant r_{Q}(\rho,\gamma_{Q})$ then

there exists $3K/4$ block $B_{k}$ with $k\in{\cal K}$, for which

Moreover, on the blocks $B_{k}$ where (17) holds, it follows from assumption in (8) that all $f\in F$ such that $\left\|f-f^{*}\right\|\leqslant\rho$ satisfies

It follows from the convexity of $F$ and the nearest point theorem that $P[2\zeta(f-f^{*})]\leqslant 0$ for all $f\in F$, therefore, for all $f\in F$ such that $\left\|f-f^{*}\right\|\leqslant\rho$,

Moreover, still on the blocks $B_{k}$ where (17) holds, one also has, thanks to assumption (8), that for all $f\in F$ such that $\left\|f-f^{*}\right\|\leqslant\rho$,

It follows that, for all $f\in F$ such that $\left\|f-f^{*}\right\|\leqslant\rho$,

The main result of this section is Lemma 3. It will be used to bound from above the criterion {\cal C}_{K,\lambda}\big{(}f^{*}\big{)}=\sup_{g\in F}T_{K,\lambda}(g,f^{*}). Recall that $\rho_{K}$ and $\lambda$ are defined as

where $\epsilon=(c\theta_{0}^{2})^{-1}$ and $c,c^{\prime}\geqslant$ are absolute constants. We also need to consider a partition of the space $F$ according to the distance between $g$ and $f^{*}$ w.r.t. $\left\|\cdot\right\|$ and $\left\|\cdot\right\|_{L_{P}^{2}}$ as in Figure 2: define for all $\kappa\geqslant 1$,

On the event $\Omega(K)$, it holds for all $\kappa\in\{1,2\}$,

when $c\geqslant 32$ and $10\epsilon/4\leqslant c^{\prime}\epsilon\leqslant((4\theta_{0})^{-2}-2\epsilon)$.

Let $g\in F_{1}^{(\kappa)}$. Since the quadratic process is non negative,

Therefore, applying (18) for $\rho=\kappa\rho_{K}$ and the choice of $\rho_{K}$ and $\lambda$ as in (20), we get

Let $g\in F_{2}^{(\kappa)}$. Given that $Q_{1/2}(x-y)\leqslant Q_{3/4}(x)-Q_{1/4}(y)$ for any vector $x$ and $y$, we have

Moreover $2\epsilon\leqslant(4\theta_{0})^{-2}$ when $c\geqslant 32$, so it follows from (16) and (18) for $\rho=\kappa\rho_{K}$ that

Putting both inequalities together and using that $\lambda\kappa\rho_{K}=c^{\prime}\kappa\epsilon r^{2}(\rho_{K})$, we get

Let $\rho\geqslant 0$, $\Gamma_{f^{*}}(\rho)=\cup_{f\in f^{*}+(\rho/20)B}(\partial\left\|\cdot\right\|)_{f}$ (cf.) section 3.3). For all $g\in F$,

Let $g\in F$, $f^{**}\in f^{*}+(\rho/20)B$ and $z^{*}\in(\partial\left\|\cdot\right\|)_{f^{**}}$. We have

where the last inequality follows from $z^{*}(f^{**}-f^{*})\leqslant\|f^{**}-f^{*}\|$. The result follows by taking supremum over $z^{*}\in\Gamma_{f^{*}}(\rho)$.

Let $\rho\geqslant 0$. Let $g\in F$ be such that $\left\|g-f^{*}\right\|\geqslant\rho$. Define $f=f^{*}+\rho(g-f^{*})/\left\|g-f^{*}\right\|$. Then $f\in F$, $\left\|f-f^{*}\right\|=\rho$ and,

The first conclusion holds by convexity of $F$, the second statement is obvious. For the last one, let $\Upsilon=\|g-f^{*}\|/\rho$ and note that $\Upsilon\geqslant 1$ and $g-f^{*}=\Upsilon(f-f^{*})$, so we have

Now, let us bound $\sup_{g\in F_{3}^{(\kappa)}}T_{K,\lambda}(g,f^{*})$. Let $g\in F_{3}^{(\kappa)}$. Apply Lemma 4 and Lemma 5 to $\rho=\rho_{K}$: there exists $f\in F$ such that $\left\|f-f^{*}\right\|=\rho_{K}$ and

First assume that $\left\|f-f^{*}\right\|_{L_{P}^{2}}\leqslant r(\rho_{K})$. In that case, $\left\|f-f^{*}\right\|=\rho_{K}$ and $\left\|f-f^{*}\right\|_{L_{P}^{2}}\leqslant r(\rho_{K})$ therefore, $f\in H_{\rho_{K}}$. Moreover, by definition of $K^{*}$ and since $K\geqslant K^{*}$, we have $\rho_{K}\geqslant\rho^{*}$ which implies that $\rho_{K}$ satisfies the sparsity equation from Definition 6. Therefore, $\sup_{z^{*}\in\Gamma_{f^{*}}(\rho_{K})}z^{*}(f-f^{*})\geqslant\Delta(\rho_{K})\geqslant 4\rho_{K}/5$. Now, it follows from the definition of $\lambda$ in (20) that

Moreover, since the quadratic process is non-negative, by (18) applied to $\rho=\rho_{K}$,

Finally, noting that $2\epsilon-4c^{\prime}\epsilon/5\leqslant 0$ when $c^{\prime}\geqslant 10/4$, binding all the pieces together in (4.2) yields

Second, assume that $\left\|f-f^{*}\right\|_{L_{P}^{2}}\geqslant r(\rho_{K})$. Since $\left\|f-f^{*}\right\|=\rho_{K}$, it follows from (16) and (17) for $\rho=\rho_{K}$ that

where we used that $2\epsilon\leqslant(16\theta_{0})^{-2}$ when $c\geqslant 32$ in the last inequality. Plugging the last result in (4.2) we get

when $16(2+c^{\prime})\epsilon\leqslant\theta_{0}^{-2}$.

The proof follows essentially the one of [56, Theorem 3.2] or [50, Lemma 2].

Let $\hat{f}\in F$ be such that, on $\Omega(K)$, {\cal C}_{K,\lambda}\big{(}\hat{f}\big{)}\leqslant(2+c^{\prime})\epsilon r^{2}(\rho_{K}). Then, on $\Omega(K)$, $\hat{f}$ satisfies

Thus, on $\Omega(K)$, $\hat{f}\in\left\{g\in F:T_{K,\lambda}(g,f^{*})\geqslant-(2+c^{\prime})\epsilon r^{2}(\rho_{K})\right\}$. When $c^{\prime}=16$ and $c>832$,

therefore, $\hat{f}\in F_{1}^{(2)}$ on $\Omega(K)$. This yields the results for both the regularization and the $L^{2}_{P}$-norm.

Finally, let us turn to the control on the excess risk. It follows from (19) for $\rho=\kappa\rho_{K}$ that

4 End of the proof of Theorem 1

By definition of $\widehat{f}_{K,\lambda}$,

where $\{F^{(1)}_{1},F^{(1)}_{2},F^{(1)}_{3}\}$ is the decomposition of $F$ as in Figure 2. It follows from Lemma 3 (for $\kappa=1$) that on the event $\Omega(K)$,

Therefore, for $c^{\prime}=16$ and $c=833$ the conclusion of the proof of Theorem 1 follows from Lemma 6.

5 Proof of Theorem 2

Let $K\in[K_{1},K_{2}]$ and let $\Omega_{K,c_{ad}}=\{f^{*}\in\cap_{J=K}^{K_{2}}\hat{R}_{J,c_{ad}}\}$ where we recall that $\hat{R}_{J,c_{ad}}=\{f\in F:{\cal C}_{J,\lambda}(f)\leqslant(c_{ad}/\theta_{0}^{2})r^{2}(\rho_{J})\}$. Lemma 3 (for $\kappa=1$) shows that, for $c_{ad}=(2+c^{\prime})/c$, $\Omega_{K,c_{ad}}\supset\cap_{J=K}^{K_{2}}\Omega(J)$. Therefore, on $\cap_{J=K}^{K_{2}}\Omega(J)$, $\hat{K}_{c_{ad}}\leqslant K$ which implies that $\widehat{f}_{c_{ad}}\in\hat{R}_{K,c_{ad}}$. By Lemma 6 (for $c^{\prime}=16$ and $c=833$), this implies that

Appendix A Simulation study

The aim of this section is to show that the min-max procedure introduced in this work can be computed using alternating descent-ascent algorithms. It appears that all the following algorithms can be recast as block gradient descent (BGD) but the major difference with the classical BGD is that blocks are chosen according to their “centrality” via the median operator instead of iterating over all the blocks (resp. at random) in the classical (resp. stochastic) BGD approach.

We study the performance of all the algorithms on a dataset corrupted by outliers of various forms. The “basic” set of “informative data” is called ${\cal D}_{1}$. This set is corrupted by various datasets of outliers, named ${\cal D}_{2},{\cal D}_{3}$, ${\cal D}_{4}$ and ${\cal D}_{5}$. Good and bad data have been merged and shuffled in the dataset ${\cal D}={\cal D}_{1}\cup{\cal D}_{2}\cup{\cal D}_{3}\cup{\cal D}_{4}$ given to the statistician. Let us now detail the construction of these datasets.

The set ${\cal D}_{1}$ of “informative data” is a set of $N_{good}$ i.i.d. data $(X_{i},Y_{i})$ with common distribution

${\cal D}_{2}$ is a dataset of $N_{bad-1}$ “bad data” $(X_{i},Y_{i})$ such that $Y_{i}=1$ and $X_{i}=(1)_{j=1}^{d}$

${\cal D}_{3}$ is a dataset of $N_{bad-2}$ “bad data” $(X_{i},Y_{i})$ such that $Y_{i}=10000$ and $X_{i}=(1)_{j=1}^{d}$

${\cal D}_{4}$ is a dataset of $N_{bad-3}$ “bad data” $(X_{i},Y_{i})$ where $Y_{i}$ is a $0-1$-Bernoulli random variable and $X_{i}$ is uniformly distributed over $^{d}$,

${\cal D}_{5}$ is also a set of “outliers” that have been generated according to a linear model as in (22) (i.e. with the same target vector $t^{*}$) but for a different choice of design $X$ and noise $\zeta$. Here, we take $X\sim{\cal N}(0,\Sigma)$ where $\Sigma=(\rho^{|i-j|})_{1\leqslant i,j\leqslant d}$ and $\zeta$ is a heavy-tailed noise distributed according to a Student distribution with various degrees of freedom.

These different types of “outliers” ${\cal D}_{j},j=2,3,4,5$ have been chosen to illustrate that the theory allows for outliers that may have absolutely nothing to do with the oracle $t^{*}$ that can be neither independent nor random as illustrated by datasets ${\cal D}_{2}$ and ${\cal D}_{3}$.

A.2 From algorithms for the LASSO to their “MOM versions”

There is a huge literature presenting many algorithms to implement the LASSO procedure. We explore several of them to investigate their performance regarding robustness.

Each algorithm designed for the LASSO can be transformed into an algorithm for the min-max estimator we have been studying in this work. Let us now explain how this can be done. Recall that MOM version of the LASSO estimator is

Moreover, our algorithms particularly fits the “big data” framework which is our original motivation for the introduction of robust procedures in machine learning. In this framework, the map-reduce paradigm has emerged as a leading idea to design procedures. In this situation, the data are spread out in a cluster of servers and are therefore naturally split into blocks. Then our procedures simply uses for mapper a mean function and for reducer a median function. This makes our algorithms easily scalable into the big data framework even when some servers have crashed down (making outliers data). MOM algorithm could therefore reduced the maintenance of big clusters.

In the sequel, we use this strategy to transform several algorithms implemented for the LASSO into algorithms for the min-max estimator (23). We first start with the subgradient descent algorithm.

A.3 Subgradient descent algorithm

The key insight in Algorithm 1 are step 2 and step 4 where the blocks number have been chosen according to their centrality among the other blocks via the median operator. Those steps are expected 1) to remove outliers from the descent / ascent directions 2) to improve the accuracy of the latter directions.

for some given $\rho\in(0,1)$, $\delta=10^{-4}$ and initial point $\gamma_{0}=1$.

A.4 Proximal gradient descent algorithms

Note that the step sizes sequences $(\eta_{p})_{p}$ and $(\beta_{p})_{p}$ may be chosen according to the remarks below Algorithm 1.