Learning from MOM's principles: Le Cam's approach

Introduction

Consider the problem of estimating minimizers of the integrated square-loss over a convex class of functions : $f^{*}\in\operatorname*{argmin}_{f\in F}P(Y-f(X))^{2}$ based on a data set $(X_{i},Y_{i})_{i=1,\ldots,N}$. The labels $Y$ and $Y_{i}$’s are real-valued while the inputs $X$ and $X_{i}$’s take values in an abstract measurable space ${\cal X}$.

These estimators are optimal in i.i.d. subgaussian setups but suffer several drawbacks when data are heavy-tailed or corrupted by “outliers”, see Catoni (2012); Huber and Ronchetti (2009). These issues are critical in many modern applications such as high-frequency trading, where heavy-tailed data are quite common or in various areas of biology such as micro-array analysis or neuroscience where data are sometimes still nasty after being preprocessed. To overcome the problem, various methods have been proposed. The most common strategy is to replace the square-loss function to make it less sensitive to outliers. For example, Huber (1964) proposed a loss that interpolates between square and absolute loss to produce an estimator between the unbiased (but non robust) empirical mean and the (more robust but biased) empirical median. Huber’s estimators have been intensively studied asymptotically by Huber (1964); Huber and Ronchetti (2009), non-asymptotic results have also been obtained more recently by Chichignoud and Lederer (2014); Mendelson (2015b); Fan et al. (2017) for example. An alternative approach has been proposed by Catoni (2012) and used in learning frameworks such as least-squares regression by Audibert and Catoni (2011) and for more general loss functions by Brownlees et al. (2015).

Another line of research to build robust estimators and robust selection procedures was initiated by Le Cam (1973, 1986) and further developed by Birgé (2006), Baraud (2011) and Baraud et al. (2017). It is based on comparisons or tests between elements of $F$. More precisely, the approach builds on tests statistics $T_{N}(g,f)$ comparing $f$ and $g$. These tests define the sets ${\cal B}_{T_{N}}(f)$ of all $g$’s that have been preferred to $f$ and the final estimator $\hat{f}$ is a minimizer of the diameter of ${\cal B}_{T_{N}}(f)$. The measure of diameter is directly related to statistical performances one seeks for the estimator. These methods mostly focus on Hellinger loss and are generally considered difficult to compute, see however Baraud et al. (2014); Sart (2014).

In a related but different approach, Lugosi and Mendelson (2017) have recently introduced “median-of-means tournaments”. Median-of-means estimators of Alon et al. (1999); Jerrum et al. (1986); Nemirovsky and Yudin (1983) compare elements of $F$. A “champion” is an element $\hat{f}$ such that ${\cal B}_{T_{N}}(\hat{f})$ is smaller than a computable upper bound on the radius of ${\cal B}_{T_{N}}(f^{*})$. They prove that the risk of any champion is controlled by this upper bound. An important message of this paper is that Le Cam’s estimators are quite common in statistics, in particular in robust statistics. For example, Section 3 shows that any penalized empirical loss function can be obtained by Le Cam’s approach and that Le Cam’s estimators based on median-of-means tests are champions of median-of-means tournaments.

This paper studies estimators derived from Le Cam’s procedure based on regularized median-of-means (MOM) tests (see Section 4.1). Our estimators are therefore particular instances of champions of MOM’s tournaments and another motivation is to push further the analysis of this particular champion. The main advantage of MOM’s tests over Le Cam’s original ones is that they allow for more classical loss functions than Hellinger loss. This idea is illustrated on the square-loss. Compared to Huber or Catoni’s losses, this approach allows to control easily the risk of our estimators by using classical tools from empirical process theory, it also allows to tackle the problem of “aggressive” outliers.

The closest work is certainly that of Lugosi and Mendelson (2017), but we believe that our paper contains substantial improvements. We stress the intimate relationship between their estimator and Le Cam general construction and use this parallel to propose a much simpler estimator. Our risk bounds are always better and we extend their results to possibly corrupted data-sets.

To investigate robustness properties of median-of-means estimators, we partition the dataset into two parts. One is made of outliers data. They are indexed by ${\cal O}\subset[N]$ of cardinality $|{\cal O}|=K_{o}$. On those data, absolutely nothing is assumed : they may not be independent, have distributions $P_{i}$ totally different from $P$, with no moment at all, etc.. These are typically data polluting datasets like in the case of declarative data on internet or when something went wrong during the storage, compression or transfer which resulted in complete non sense data. They may also be observations met in biology as in the classical eQTL (Expression Quantitative Trait Loci and The Phenogen Database) from Saba et al. (2008). Many other examples of datasets containing outliers could be provided, this includes frauds detection and terrorist activity as examples. Of course, outliers are not flagged in advance and the statistician is given no a priori information on which data is an outlier or not. The other part of the dataset is made of data on which the MOM estimator rely on to estimate the oracle $f^{*}$. There should be enough information in those data so that the estimation of $f^{*}$ is possible, even in the presence of outliers provided they remain in a “decent proportion”. We therefore call the non-outliers, the informative data, those that bring information on $f^{*}$. We denote by ${\cal I}\subset[N]$ the set indexing these data. We therefore end up with a partition of $[N]$ as $[N]={\cal I}\cup{\cal O}$ which, again, is not known from the statistician.

The radii of the sets ${\cal B}_{T_{N}}(f)$ are computed for regularization and $L^{2}_{P}$ norms. The regularization norm is chosen in advance by the statistician to promote sparsity or smoothness. It can be used freely in our procedure, but it doesn’t ensure a small $L^{2}_{P}$ risk for the estimator. The $L^{2}_{P}$-norm is unknown in general since it depends on the distribution of $X$. Furthermore, the classical $L^{2}_{P_{N}}$-empirical metric fails to estimate the $L^{2}_{P}$ metric without subgaussian properties of the design vector $X$. Fortunately, it can be replaced by a median-of-means metric. To handle simultaneously both regularization and $L^{2}_{P}$ norms, we will also slightly extend Le Cam’s principle. Our first important result shows that the resulting estimator is well localized w.r.t. both regularization and $L^{2}_{P}$ norms.

Median-of-means estimators rely on a data splitting into $K$ blocks and this parameter drives the resulting statistical performances (cf. Devroye et al. (2016)). To achieve optimal rates, $K$ should be ultimately chosen using parameters that depend on the oracle $f^{*}$ like its sparsity which is not in general available to the statistician. To bypass this problem, the strategy of Lepski (1991) is used as in Devroye et al. (2016) to select $K$ adaptively and get a fully data-driven procedure.

[Theorem 1.4 in Lecué and Mendelson (2016a)] Assume $t^{*}$ is $s$-sparse, $N\geq c_{0}s\log(ed/s)$, $X$ is isotropic and

$|{\cal I}|=N$ and $|{\cal O}|=0$ (no outliers in the dataset),

\zeta=Y-\bigl{<}X,t^{*}\bigr{>}\in L_{q_{0}} for some $q_{0}>2$

This paper shows that Theorem 1 holds for a MOM version of the LASSO estimator under much weaker assumptions, with a better probability estimate than (1). More precisely, the following theorem is proved.

Assume that $t^{*}$ is $s$-sparse, $N\geq c_{0}s\log(ed/s)$, $X$ is isotropic and

$|{\cal I}|\geq N/2$ and $|{\cal O}|\leq c_{1}s\log(ed/s)$ (the number of outliers may be proportional to the sparsity times $\log(ed/s)$),

\zeta=Y-\bigl{<}X,t^{*}\bigr{>}\in L_{q_{0}} for some $q_{0}>2$

There exists an estimator $\hat{t}$, called MOM-LASSO, satisfying for every $1\leq p\leq 2$,

Theoretical properties of MOM LASSO outperform those of LASSO in several ways.

Estimation rates achieved by MOM-LASSO are the actual minimax rates $s\log(ed/s)/N$, see Bellec et al. (2016), while classical LASSO estimators achieve the rate $s\log(ed)/N$. This improvement is possible thanks to the adaptation step in MOM-LASSO.

the probability deviation in (1) is polynomial – $1/N^{(q_{0}/2-1)}$ in (1) – it is exponentially small for MOM LASSO. Exponential rates for LASSO hold only if $\zeta$ is subgaussian ($\left\|\zeta\right\|_{L_{p}}\leq C\sqrt{p}\left\|\zeta\right\|_{L_{2}}$ for all $p\geq 2$).

MOM LASSO is insensitive to data corruption by up to $s$ times $\log(ed/s)$ outliers while only one outlier can be responsible of a dramatic breakdown of the performances of LASSO.

From a mathematical point of view, our results are based on a slight extension of the Small Ball Method (SBM) of Koltchinskii and Mendelson (2015); Mendelson (2014a) to handle non-i.d. data. SBM is also extended to bound both quadratic and multiplier parts of the quadratic loss. Otherwise, all arguments are standard, which makes the approach very attractive and easily reproducible in other frameworks of statistical learning.

The paper is organized as follows. Section 2 briefly presents the general setting and our main illustrative example. Section 3 presents Le Cam’s construction of estimators based on tests. We also show why many learning procedures may be obtained by this approach. The construction of estimators and the main assumptions are gathered in Section 4. Our main theorems are stated in Section 5 and proved in Section 6.

Let also $g+{\cal G}=g+1{\cal G}$. We also denote by $I(g\in{\cal C})$ the indicator function of the set ${\cal C}$ which equals to $1$ when $g\in{\cal C}$ and otherwise.

Setting

Let $\left\|\cdot\right\|$ denote a norm defined onto a linear subspace $E$ of $L^{2}_{P}$ containing $F$.

Let f^{*}=\bigl{<}\cdot,t^{*}\bigr{>}\in F, where

Learning from tests

This section details the ideas underlying the construction of a MOM estimator using an extension of Le Cam’s approach.

By definition of the oracle $f^{*}$, one has

As $T_{\text{id}}(g,f)=R(f)-R(g)$ depends on $P$, we estimate it by test statistics $T(g,f,(X_{i},Y_{i})_{i\in[N]})\equiv T_{N}(g,f)$ that is, real random variables such that

These statistics are used to compare $f$ to $g$, simply by saying that $g$ $T_{N}$-beats $f$ iff $T_{N}(g,f)\geq 0$. In this paper, the statistics $T_{N}(g,f)$ are median-of-means estimators of $R(f)-R(g)$ (cf. (12) in Section 4.1).

Le Cam’s construction

Let $(T_{N}(g,f))_{f,g\in F}$ denote a collection of test statistics and let $d(\cdot,\cdot)$ denote a pseudo-distance on $F$ measuring (or related to) the risk we want to control. Let for all $f\in F$,

be the set of all functions $g\in F$ that beat $f$. If $f$ is far from $f^{*}$, then $\mathcal{B}_{T_{N}}(f)$ is expected to have a large radius w.r.t. $d(\cdot,\cdot)$. We therefore introduce this radius as a criteria to minimize : for all $f\in F$, let $C_{T_{N}}(f)=\sup_{g\in{\cal B}_{T_{N}}(f)}d(f,g)$.

By (3), $f\in\mathcal{B}_{T_{N}}(g)$ or $g\in\mathcal{B}_{T_{N}}(f)$ (both happen if $T_{N}(f,g)=0$), hence $d(f,g)\leq C_{T_{N}}(f)\vee C_{T_{N}}(g)$. In particular, for all $f\in F$,

Risk bounds for $\hat{f}_{T_{N}}$ follow from (6) and upper bounds on the radii of $\mathcal{B}_{T_{N}}(f^{*})$.

More generally, one can compare only the elements of a subset $\mathcal{F}\subset F$, typically a maximal $\epsilon$-net by introducing for all $f\in\mathcal{F}$, the set

and then by minimizing the diameter of $\mathcal{B}_{T_{N}}(f,\mathcal{F})$ over ${\cal F}$. This usually improves the rates of convergence for constant deviation results when there is a gap in Sudakov’s inequality of the localized sets of $F$ (cf. Section 5 in Lecué and Mendelson (2013) for more details). These results are not presented because we are interested in exponentially large deviation results for which our results are optimal.

Dealing with regularization : the link function

Statistical performances of estimators and the radius of $\mathcal{B}_{T_{N}}(f^{*})$ can be measured by two norms: the regularization norm $\|\cdot\|$ and $\|.\|_{L^{2}_{P}}$. As (5) allows only for one distance $d$, we propose the following extension of Le Cam approach to handle two metrics.

To introduce this extension, assume first that $d(f,g)=\|f-g\|_{L^{2}_{P}}$ can be computed for all $f,g\in F$ (this is the case if the distribution of the design is known). The next paragraph explains how to deal with the more common framework where this distance is unknown. Remark that

The main point to extend Le Cam’s approach to simultaneously control two norms is to design a link function $r(\cdot)$. In a nutshell, the values $r(\rho)$ is the $L^{2}_{P}$-minimax rate of convergence in a ball of radius $\rho$ for the regularization norm (cf. (13) in Section 4.3 for a formal definition). Then one can define

Theorem 3 shows that while a minimizer $\hat{f}^{(1)}$ of $C_{T_{N}}$ has only a nice risk for $\left\|\cdot\right\|$, a minimizer $\hat{f}^{(2)}$ of $C_{T_{N}}^{(2)}$ has both $\left\|\hat{f}^{(2)}-f^{*}\right\|$ and $d(\hat{f}^{(2)},f^{*})$ properly controlled.

Dealing with unknown norms : the isometry property

In general, $L_{P}^{2}$-distances cannot be directly computed and have to be estimated. To deal with this issue, one considers usually the empirical $L^{2}_{P_{N}}$ distance and prove that empirical and actual distances are equivalent outside a $L^{2}_{P}$-ball centered in $f^{*}$ (cf. for instance, remark after Lemma 2.6 in Lecué and Mendelson (2013)). Unfortunately this approach only works under strong concentration property that we want to relax in this paper.

The unknown $L_{P}^{2}$-metric is instead estimated by a median-of-means approach, that is, we use MOM estimators $d_{N}(f,g)$ of all $d(f,g)$ (cf. Section 4.4). The final estimator is therefore defined as a minimizer of

2 Examples

Le Cam’s approach has been used by Birgé to define $T$-estimators (cf. Baraud and Birgé (2009); Birgé (2006, 2013)) and by Baraud, Birgé and Sart to define $\rho$-estimators (cf. Baraud and Birgé (2016); Baraud et al. (2017)). Baraud (2011); Baraud et al. (2014) also built efficient estimator selection procedures with this approach. It also extends many common procedures in statistical learning theory, as shown by the following examples.

is obtained by Le Cam’s construction with the tests

These examples encompass classical empirical risk minimizers of Vapnik (1998) but also their robust versions from Huber (1964); Audibert and Catoni (2011).

Example 2 : median-of-means estimators

Another, perhaps less obvious example is the median-of-means estimator Alon et al. (1999); Jerrum et al. (1986); Nemirovsky and Yudin (1983) of the expectation $PZ$ of a real valued random variable $Z$. Let $Z_{1},\ldots,Z_{N}$ denote a sample and let $B_{1},\ldots,B_{K}$ denote a partition of $[N]$ into bins of equal size $N/K$. The estimator $\text{MOM}_{K}(Z)$ is the (empirical) median of the vector of empirical means $\left(P_{B_{k}}Z=|B_{k}|^{-1}\sum_{i\in B_{k}}Z_{i}\right)_{k\in[K]}$. Recall that

Basic properties of the median (recalled in Eq (8) and (9) of Section 4.1) yield

Example 3 : “Champions” of a Tournament

Construction of the regularized MOM estimators

This section presents median-of-means (MOM) tests used in this work. Designing a family of tests $(T_{N}(g,f):f,g\in F)$ is one of the most important building blocks in Le Cam’s approach together with the right choice of the metric measuring the diameters ${\cal B}_{T_{N}}(f)$ for $f\in F$.

With some abuse of notations, we shall write these properties respectively

To compare/test functions $f$ and $g$ in $F$, median-of-means tests between $f$ and $g$ are now defined by

From (9), $T_{K,\lambda}$ satisfies (3) and is a tests statistic in the sense of Section 3.

2 Main assumptions

Recall that $[N]={\cal O}\cup{\cal I}$ and that $(X_{i},Y_{i})_{i\in{\cal O}}$ is a set of outliers on which we make no assumption so these may be aggressive in any sense one can imagine. The remaining informative data $(X_{i},Y_{i})_{i\in{\cal I}}$ need to bring enough information onto $f^{*}$. We therefore need some assumption on the sub-dataset $(X_{i},Y_{i})_{i\in{\cal I}}$ and, in particular, some connexion between the distributions $P_{i}$ for $i\in{\cal I}$ and $P$. These assumptions are pretty weaksince we only assume essentially that the $L^{2}_{P},L^{2}_{P_{i}}$ and $L^{1}_{P_{i}}$ geometries are comparable in the following sense.

There exists $\theta_{r}\geq 1$ such that, for all $i\in{\cal I}$ and $f\in F$,

There exists $\theta_{m}>0$ such that, for all $Q\in\{P,(P_{i})_{i\in{\cal I}}\}$ and $f\in F$,

Let us give some examples where Assumption 2 holds. If the noise random variable $\zeta(Y,X)$ (resp. $\zeta(Y_{i},X_{i})$ for $i\in{\cal I}$) has a variance conditionally to $X$ (resp. $X_{i}$ for $i\in{\cal I}$) that is uniformly bounded then Assumption 2 holds. This is, for example, the case, when $\zeta(Y,X)$ (resp. $\zeta(Y_{i},X_{i})$ for $i\in{\cal I}$) is independent of $X$ (resp. $X_{i}$ for $i\in{\cal I}$) and has finite $L^{2}$-moment with $\theta_{m}=\max_{Q\in P,\{P_{i}\}_{i\in{\cal I}}}\left\|\zeta\right\|_{L^{2}_{Q}}$. It also holds without independence under higher moment conditions. For example, assume $\sigma=\max_{Q\in P,\{P_{i}\}_{i\in{\cal I}}}\left\|\zeta\right\|_{L^{4}_{Q}}<\infty$ and, for every $f\in F$, $\left\|f-f^{*}\right\|_{L^{4}_{Q}}\leq\theta_{1}\left\|f-f^{*}\right\|_{L^{2}_{P}}$ then by Cauchy-Schwarz inequality, $\sqrt{{\rm var}_{Q}(\zeta(f-f^{*}))}\leq\left\|\zeta(f-f^{*})\right\|_{L^{2}_{Q}}\leq\left\|\zeta\right\|_{L^{4}_{Q}}\left\|f-f^{*}\right\|_{L^{4}_{Q}}\leq\theta_{1}\sigma\left\|f-f^{*}\right\|_{L^{2}_{P}}$ and so Assumption 2 holds for $\theta_{m}=\theta_{1}\sigma$.

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

By Cauchy-Schwarz inequality, $\left\|f-f^{*}\right\|_{L^{1}_{P_{i}}}\leq\left\|f-f^{*}\right\|_{L^{2}_{P_{i}}}$ for all $f\in F$ and $i\in{\cal I}$. Therefore, Assumptions 1 and 3 together imply that all 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 related to the small ball property (cf. Koltchinskii and Mendelson (2015); Mendelson (2014a)) as shown by Proposition 1 bellow. The small ball property has been recently used in Learning theory and signal processing. We refer to Koltchinskii and Mendelson (2015); Lecué and Mendelson (2014); Mendelson (2015b, 2014b, a); Rudelson and Vershynin (2014) for examples of distributions satisfying this assumption.

Let $Z$ be a real-valued random variable.

As one can assume that $\left\|Z\right\|_{2}\neq 0$, $p\geq(\theta_{0}^{-1}-\kappa_{0})^{2}$.

3 Complexity parameters and the link function

This section defines the link function $r(\cdot)$ making the connections between norms that will be required in the extension of Le Cam’s approach to a simultaneous control of two norms (one of the two being unknown). For any $\rho\geq 0$ and any $f\in E$, let

Let $(\epsilon_{i})_{i\in{\cal I}}$ be independent Rademacher random variables, independent from $(X_{i},Y_{i})_{i\in{\cal I}}$ and let ${\cal J}=\{J\subset{\cal I},|J|\geq|{\cal I}|/2\}$. For any $\gamma_{Q},\gamma_{M}>0$ and $\rho>0$ let $F_{f^{\star},\rho,r}=\{f\in F\cap B(f^{\star},\rho):\left\|f-f^{\star}\right\|_{L^{2}_{P}}\leq r\}$,

Note that if the function $\rho\to\max(r_{Q}(\rho,\gamma_{Q}),r_{M}(\rho,\gamma_{M}))$ is itself continuous and non-decreasing then it can be taken equal to $r(\cdot)$. In the next paragraph, we provide an explicit computation of the functions $r_{Q}(\cdot)$, $r_{M}(\cdot)$ and $r(\cdot)$ in the “LASSO case”.

Under Assumption 4, if $\sigma=\left\|\zeta\right\|_{L^{q_{0}}}$, (Mendelson, 2016, Theorem 1.6) shows that, for every $\rho>0$,

Therefore, a link function is explicitly given by

4 The estimators

Let $(T_{K,\lambda}(g,f))_{f,g\in F}$ denote the family of tests defined in (12). For every function $f\in F$, let $\mathcal{B}_{K,\lambda}(f)=\{g\in F:T_{K,\lambda}(g,f)\geq 0\}$ denote the set of all functions $g\in F$ that beats $f$. As explained in Section 3, these sets will be measured by two metrics. First, let

Lemma 4 below proves that, with large probability, $\text{MOM}_{K}\left[|f-g|\right]$ and $\left\|f-g\right\|_{L^{2}_{P}}$ are isomorphic distances. The second criterion is then given by

where $r(\cdot)$ is a link function as defined in Definition 1. That is a continuous and non-decreasing function such that for all $\rho>0$, $r(\rho)\geq\max(r_{M}(\rho,\gamma_{M}),r_{Q}(\rho,\gamma_{Q}))$ where the choice of $\gamma_{Q}$ and $\gamma_{M}$ is given in Theorem 3 below. The associated estimator is then given by

5 The sparsity equation

By (6), estimation rates for $\hat{f}_{K,\lambda}^{(2)}$ will be derived from upper bounds on $C_{K,\lambda}^{(2)}(f^{*})$. To get these, our strategy is to show that $T_{K,\lambda}(f^{*},f)>0$ for all $f$ such that $\|f-f^{*}\|$ or $\|f-f^{*}\|_{L^{2}_{P}}$ is large.

Recall that the quadratic / multiplier decomposition of the excess quadratic risk:

Let $f\in F$ and $\rho=\left\|f-f^{*}\right\|$. When $\rho$ is large and $\left\|f-f^{*}\right\|_{L^{2}_{P}}$ is small, $T_{K,\lambda}(f^{*},f)>0$ thanks to the regularization term $\lambda(\|f\|-\|f^{*}\|)$ in (16) because the quadratic term $(f-f^{*})^{2}$ is likely to be small. We will therefore derive a lower bound on the regularization term when the subdifferential of $\left\|\cdot\right\|$ is “large” in the following sense.

First, we recall that the subdifferential of $\left\|\cdot\right\|$ in $f\in F$ is the set

where $(E^{*},\left\|\cdot\right\|^{*})$ is the dual normed space of $(E,\left\|\cdot\right\|)$ (and $E$ is the linear space containing $F$ onto which $\left\|\cdot\right\|$ is defined). For all $\rho>0$, let $H_{\rho}$ denote the set

where $r(\cdot)$ is the link function from Definition 1. Let $\Gamma_{f^{*}}(\rho)$ denote the union of all subdifferentials of $\left\|\cdot\right\|$ at functions “close” to $f^{*}$

Intuitively, every norm is associated with a notion of “sparsity” if one agrees to say that a non-zero function $f^{**}$ is sparse w.r.t. the norm $\left\|\cdot\right\|$ when the subdifferential of this norm at $f^{**}$ is a “large subset” of the dual sphere (i.e. the sphere of $(E^{*},\left\|\cdot\right\|^{*})$). Sparse functions $f^{**}$ are useful in our context because a large lower bound on $\left\|f\right\|-\left\|f^{**}\right\|$ (and so for $\left\|f\right\|-\left\|f^{**}\right\|$ when $\left\|f^{**}-f^{*}\right\|$ is small enough) can be derived when the vector $f-f^{**}$ is in the right direction. This intuition are formalized in the sparsity equation. More precisely, let

$\Delta(\rho)$ is a uniform lower bound on $\|f\|-\|f^{**}\|$ if $f^{**}\in B(f^{*},\rho/20)$. Thus, $\|f\|-\|f^{*}\|\gtrsim\rho$, if $\sup_{f^{**}\in\Gamma_{f^{*}}(\rho)}(\|f\|-\|f^{**}\|)\gtrsim\rho$ or if the following sparsity equation of Lecué and Mendelson (2016a) holds.

A radius $\rho>0$ satisfies the sparsity equation if $\Delta(\rho)\geq 4\rho/5$.

If $\rho^{*}$ satisfies the sparsity equation, so do all $\rho\geq\rho^{*}$. Therefore, one can define

The equation has been solved in this example in (Lecué and Mendelson, 2016a, Lemma 4.2), recall this result.

If $N\gtrsim s\log(ed/s)$ and if there exists a $s$-sparse vector in $t^{*}+(\rho/20)B_{1}^{d}$, Lemma 1 and the choice of $r(\cdot)$ in (15) imply that for $\sigma=\left\|\zeta\right\|_{L^{q_{0}}}$,

then $\rho^{*}$ satisfies the sparsity equation and $r^{2}(\rho^{*})$ is the rate of convergence of the LASSO (cf. Lecué and Mendelson (2016a)).

Main results

Theorem 3 gathers estimation error bounds satisfied by the estimators ${\hat{f}}_{K,\lambda}^{(j)}$ for $j=1,2$ defined in Section 4.4.

Grant Assumptions 1, 2 and 3 and let $r_{Q}$, $r_{M}$ anr $r$ denote the functions introduced in Definition 1 for

Let $\rho^{*}$ be defined in (17) and let $K^{*}$ denote the smallest integer such that

For all $K\geq 1$, let $\rho_{K}$ be a solution of $r^{2}(\rho_{K})=[16\theta_{m}^{2}/(\epsilon^{2}\alpha)]\sqrt{K/N}$. Assume that for every $i\in{\cal I}$, $K\in[K^{*},N]$ and $f\in F\cap B(f^{*},\rho_{K})$,

when the regularization parameter satisfy

To the best of our knowledge, Theorem 3 provides the first statistical performance of an estimator operating in such a “nasty” environment: the dataset may be corrupted by complete outliers, the informative data may be heavy-tailed and their distribution $P_{i}$ for $i\in{\cal I}$ is only asked to have a $L^{2}$ and $L^{1}$ geometry over $F-f^{*}$ equivalent to that of $P$. The most surprising thing is that the rate we obtain for $K=K^{*}$ in Theorem 3, i.e. $r(\rho_{K^{*}})$ when the number of outliers $K_{o}$ is less than $Nr^{2}(\rho^{*})$ is the minimax rate we would have gotten in a very good i.i.d. subgaussian framework with independent noise. This means that the quality of a dataset does not have to be as good as it is classically assumed in the literature to make estimation possible: all we need is that a large fraction of the data should be independent (even though we believe that some “weak dependence” could also be introduced) and distributed according to distributions inducing $L^{1}$ and $L^{2}$ geometries equivalent to the $L^{2}_{P}$ one.

In Theorem 3, $K$ can be as small as the infimum between the number of outliers and $N$ times the minimax rate of convergence. Henceforth, if the optimal rate is known, as in Lugosi and Mendelson (2017), Theorem 3 shows that Le Cam’s champion of the median of means tournament with $K=K^{*}$ reaches the same performances as any champion in this paper. Theorem 3 is thus an extension of Lugosi and Mendelson (2017) to a non-i.d. corrupted setting for Le Cam’s champion. Moreover, our control improves theirs if the upper bound on the radius of $f^{*}$ used in Lugosi and Mendelson (2017) is pessimistic (cf. Example 3.2 in Section 3.2).

Assumption 1 is automatically satisfied in the i.i.d. case and so is Assumption (18). Theorem 3 goes beyond this i.i.d. setup, relaxing the i.d. assumptions into proximity assumptions between $L_{P_{i}}^{2}$ and $L^{2}_{P}$ geometries, for informative data.

for the $r(\cdot)$ function defined in (15). Therefore,

The regularization parameter depends on the “level of noise” $\sigma$, the $L^{q_{0}}$-norm of $\zeta$. This parameter is unknown in practice. Nevertheless, it can be estimated and replaced by this estimator in the regularization parameter as in (Giraud, 2015, Sections 5.4 and 5.6.2).

2 Adaptive choice of K𝐾K by Lepski’s method

The main drawback of Theorem 3 is that optimal rates are only achieved when $K\approx K^{*}$. Since $K^{*}$ is unknown, it cannot be used in general. This issue is tackled in this section by Lepski’s method.

Let $K_{1}=K^{*}$ and $K_{2}=N/(84\theta_{0}^{2}\theta_{r}^{2})$ be defined as in Theorem 3. For any integer $K\in[K_{1},K_{2}]$, let $\rho_{K}$ and $\lambda$ be defined as in Theorem 3 and for $j=1,2$ denote by $\hat{f}_{K}^{(j)}={\hat{f}}_{K,\lambda}^{(j)}$ for this choice of $\lambda$. These estimators are the building blocks of the following confidence sets. For all $f\in F$, let

Finally, define adaptive (to $K$) estimators via Lepski’s method: for $j=1,2$, ${\hat{f}}_{LE}^{(j)}\in\bigcap_{J=\hat{K}^{(j)}}^{K_{2}}R_{J}^{(j)}$.

Grant assumptions and notations of Theorem 3. There exist absolute constants $(c_{i})_{1\leq i\leq 2}$ such that the estimators ${\hat{f}}_{LE}^{(j)}$ for $j=1,2$ satisfy for every $K\in[K^{*},N/(84\theta_{0}^{2}\theta_{r}^{2})]$, with probability at least $1-c_{1}\exp\left(-c_{2}K\right)$,

In particular, for $K=K^{*}$, if the following regularity assumption holds: there exists an absolute constant $c_{3}$ such that for all $\rho>0$, $r(2\rho)\leq c_{3}r(\rho)$ then with probability at least

Theorem 4 shows that $\hat{f}_{LE}$ achieves the same rate of convergence with the same exponentially high confidence as a minimax estimator does in the Gaussian regression model (with independent noise). These rates are achieved here under very weak stochastic assumptions allowing the presence of outliers, without assuming that the regression function lies in $F$ or that the data are i.i.d.. Compared to Lugosi and Mendelson (2017), using a Lepski method, we don’t have to choose the integer $K$ in advance, we let the data decide the best choice and automatically get an estimator with the correct minimax rate of convergence. Moreover, the regularization parameter is chosen adaptively, which yields to exact minimax rates and, since this minimax rate is not required to build the estimators, these are naturally adaptive.

The following result follows from Theorem 4 together with the computation of $\rho^{*}$, $r_{Q}$, $r_{M}$ and $r$ from the previous sections. This is a slight extension of Theorem 2 to the case where the oracle $t^{*}$ is not exactly sparse but close to a sparse vector.

$|{\cal I}|\geq N/2$ and $|{\cal O}|\leq c_{1}s\log(ed/s)$,

\zeta=Y-\bigl{<}X,t^{*}\bigr{>}\in L_{q_{0}} for some $q_{0}>2$

The MOM-LASSO estimator $\hat{t}_{LE}$ such that \hat{f}_{LE}=\bigl{<}\hat{t}_{LE},\cdot\bigr{>} satisfies, with probability at least $1-c_{2}\exp(-c_{3}s\log(ed/s))$, for every $1\leq p\leq 2$,

In particular, Theorem 5 shows that, for our estimator contrary to the one in Lugosi and Mendelson (2017), the sparsity parameter $s$ does not have to be known in advance in the LASSO case.

Proofs

We consider the set of indices of blocks $B_{k}$ containing only informative data:

Grant Assumptions 1 and 3. Fix $\eta\in(0,1)$, $\rho>0$ and let $\alpha,\gamma_{Q},\gamma,x\in(0,1)$ be such that $\gamma\left(1-\alpha-x-32\theta_{0}\gamma_{Q}\right)\geq 1-\eta$. Let $K\in[K_{o}/(1-\gamma),N\alpha/(2\theta_{0}\theta_{r})^{2}]$.

For all $f\in F-\{f^{*}\}$, let $n_{f}=(f-f^{*})/\left\|f-f^{*}\right\|_{L^{2}_{P}}$. For $i\in{\cal I}$, $P_{i}|n_{f}|\geq\theta_{0}^{-1}$ by Assumption 3 and $P_{i}n_{f}^{2}\leq\theta_{r}^{2}$ by Assumption 1. By Markov’s inequality, for all $k\in{\cal K}$,

Since $K\leq[\alpha/(2\theta_{0}\theta_{r})]^{2}N$ then $|B_{k}|=N/K\geq[\alpha/(2\theta_{0}\theta_{r})]^{2}$ and so we have

By the Giné-Zynn symmetrization argument (Boucheron et al., 2013, Lemma 11.4),

where $(\epsilon_{k})_{k\in{\cal K}}$ are independent Rademacher variables independent of the data. Moreover, $\phi$ is 1-Lipschitz and $\phi(0)=0$. By the contraction principle (cf. (Ledoux and Talagrand, 1991, Theorem 4.12) or (Boucheron et al., 2013, Theorem 11.6)),

Applying again the symmetrization and contraction principles, we get,

It follows from the convexity of $F$ that for all $f\in{\cal F}$, $r_{Q}(\rho,\gamma_{Q})n_{f}\in F-f^{*}$ and it also belongs to the $L^{2}_{P}$ sphere of radius $r_{Q}(\rho,\gamma_{Q})$. Therefore, by definition of $r_{Q}:=r_{Q}(\rho,\gamma_{Q})$ and for $J=\cup_{k\in{\cal K}}B_{k}$,

In conclusion, on $\Omega(x)$, all $f\in{\cal F}$ is such that

In other words, on $\Omega(x)$, for all $f\in{\cal F}$, there exist at least $(1-\eta)K$ blocks $B_{k}$ such that $P_{B_{k}}|n_{f}|\geq(4\theta_{0})^{-1}$. For any of these blocks $B_{k}$, $P_{B_{k}}n_{f}^{2}\geq(P_{B_{k}}|n_{f}|)^{2}$, hence, on $\Omega(x)$, $Q_{\eta,K}[|n_{f}|]\geq(4\theta_{0})^{-1}$ and $Q_{\eta,K}[n_{f}^{2}]\geq(4\theta_{0})^{-2}$.

2 Upper Bound on the multiplier process

For all $k\in[K]$ and $f\in F$, define $W_{k}(f)=2(P_{B_{k}}-\overline{P}_{B_{k}})\left(\zeta(f-f^{*})\right)$ and

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

Denote $J=\cup_{k\in\mathcal{K}}B_{k}$ and remark that $J\in{\cal J}$ as defined in Definition 1. Let $r_{M}:=r_{M}(\rho,\gamma_{M})$ for simplicity. We have

where in the last but one inequality we used that $F$ is convex and the same argument as in the proof of Lemma 2. Moreover, since the random variables $((\zeta_{i}(f-f^{*})(X_{i})-P_{i}\zeta(f-f^{*})):i\in{\cal I})$ are centered and independent, the symmetrization argument applies and, by definition of $r_{M}$,

Now, let $\psi(t)=(2t-1)I(1/2\leq t\leq 1)+I(t\geq 1)$ for all $t\geq 0$ and note that $\psi$ is $2$-Lipschitz, $\psi(0)=0$ and satisfies $I(t\geq 1)\leq\psi(t)\leq I(t\geq 1/2)$ for all $t\geq 0$. Therefore, all $f\in B(f^{*},\rho)$ satisfies

Furthermore, it follows from the symmetrization argument that

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

In conclusion, on $\Omega(x)$, for all $f\in B(f^{*},\rho)$,

Besides the controls of the quadratic and multiplier MOM processes presented in Lemmas 2 and 3 respectively, the estimation error bounds for the MOM estimators rely on the following isometry property of the MOM processus $f\in F\to\text{MOM}_{K}\left[|f-f^{*}|\right]$.

and if $\left\|f-f^{*}\right\|_{L^{2}_{P}}\geq r_{Q}(\rho,\gamma_{Q})$ then $Q_{\eta,K}{|f-f^{*}|}\geq(1/(4\theta_{0}))\left\|f-f^{*}\right\|_{L^{2}_{P}}$.

In particular, for $\eta=1/2$, on the event $\Omega_{iso}(K,\rho)$, for all $f\in B(f^{*},\rho)$, if $\left\|f-f^{*}\right\|_{L^{2}_{P}}\geq r_{Q}(\rho,\gamma_{Q})$, then

It follows from Lemma 2 that on the event $\Omega_{Q}(K,\rho)$ for all $f\in B(f^{*},\rho)$, if $\left\|f-f^{*}\right\|_{L^{2}_{P}}\geq r_{Q}(\rho,\gamma_{Q})$ then $Q_{\eta,K}{|f-f^{*}|}\geq(1/(4\theta_{0})\left\|f-f^{*}\right\|_{L^{2}_{P}}$. This yields the “lower bound” result in (25).

For the upper bound of the isomorphic result, we essentially repeat the proof of Lemma 3. Let us just highlight the main differences. We will use the same notation as in the proof of Lemma 3 except that for all $f\in F$, we define

It follows from Chebyshev’s inequality and Assumption 1 that

Moreover, by convexity of $F$, we have, for $r_{Q}:=r_{Q}(\rho,\gamma_{Q})$,

and then using a symmetrization argument, we obtain that

In particular, on the event $\Omega(x)$, for all $f\in B(f^{*},\rho)$ there are more than $(1-\eta)K$ blocks $B_{k}$ for which, $P_{B_{k}}|f-f^{*}|\leq\overline{P}_{B_{k}}|f-f^{*}|+\gamma_{k}(f)$. Now, the result follows from Assumption 1 since $\overline{P}_{B_{k}}|f-f^{*}|\leq\theta_{r}\left\|f-f^{*}\right\|_{L^{2}_{P}}$.

4 Conclusion to the proof of Theorem 3

The proof relies on the following proposition.

Grant conditions of Theorem 3. Let $\gamma_{Q}=1/(661\theta_{0})$, $\gamma_{M}=\epsilon/168$ for some $\epsilon<7/(662\theta_{0}^{2})$ and the regularization parameter be such that

Using (8), (9) and (11) together with the quadratic / multiplier decomposition of the excess quadratic loss yields that for all $f\in F$,

Note that $\gamma(1-\alpha-x-32\theta_{0}\gamma_{Q})\geq 1-\eta$ when one chooses

For this choice of constants, Lemma 2 applies and for $\rho=\rho_{K}$ we get that there exists an event $\Omega_{Q}(K,\rho_{K})$ with probability larger than $1-\exp(-K/1008)$ and on that event, for all $f\in B(f^{*},\rho_{K})$, if $\left\|f-f^{*}\right\|_{L^{2}_{P}}\geq r_{Q}(\rho_{K},\gamma_{Q})$ then

Moreover, for the choice of parameters as in (27), we also have $\gamma(1-\alpha-x-8\gamma_{M}/\epsilon)\geq 1-\eta$, hence Lemma 3 applies and for $\rho=\rho_{K}$ we get that there exists an event $\Omega_{M}(K,\rho_{K})$ with probability larger than $1-\exp(-K/1008)$ and on that event, for all $f\in B(f^{*},\rho_{K})$ there are more than $3K/4$ blocks $B_{k}$ with $k\in{\cal K}$ such that

Combining the last result with Assumpion (18), it follows that on the event $\Omega_{M}(K,\rho_{K})$, for all $f\in B(f^{*},\rho_{K})$,

Let us now prove that on the event $\Omega_{M}(K,\rho_{K})\cap\Omega_{Q}(K,\rho_{K})$, one has for all $f\in B(f^{*},\rho_{K})$,

Assume that $\Omega_{M}(K,\rho_{K})\cap\Omega_{Q}(K,\rho_{K})$ holds and let $f\in B(f^{*},\rho_{K})$. First assume that $\left\|f-f^{*}\right\|_{L^{2}_{P}}\geq r^{2}(\rho_{K})$. Then, it follows from (6.4), (28) and (29), the choice of $\epsilon$ in (27) and the definition of $\rho_{K}$ that

Now, if $\left\|f-f^{*}\right\|_{L^{2}_{P}}\leq r^{2}(\rho_{K})$ then it follows from (6.4), (29) and the definition of $\rho_{K}$ that

Let $f\in F$ be such that $\|f-f^{*}\|\leq\rho_{K}$ and $\left\|f-f^{*}\right\|_{L_{P}^{2}}\geq r(\rho_{K})$. It follows from the triangular inequality that $\|f\|-\|f^{*}\|\geq-\|f-f^{*}\|\geq-\rho_{K}$. Combining this together with (31), it follows that

when $\lambda<r^{2}(\rho_{K})/(32\theta_{0}^{2}\rho_{K})$.

For all $f\in F$ such that $\|f-f^{*}\|\geq\rho_{K}$

For every $f^{**}\in F^{*}+(\rho_{K}/20)B$ and every $z^{*}\in(\partial\left\|\cdot\right\|)_{f^{**}}$,

Assume that, for all $f\in F\cap S(f^{*},\rho_{K})$,

Then (32) holds for all $f\in F$ such that $\left\|f-f^{*}\right\|\geq\rho_{K}$.

Let $f\in F$ be such that $\left\|f-f^{*}\right\|\geq\rho_{K}$. Define $g=f^{*}+\rho_{K}\frac{f-f^{*}}{\|f-f^{*}\|}$ and remark that $\left\|g-f^{*}\right\|_{L^{2}_{P}}=\rho_{K}$ and that, by convexity of $F$, $g\in F$. It follows from (32) that for $\kappa=\|f-f^{*}\|/\rho_{K}\geq 1$, one has

Let $f\in F$ be such that $\left\|f-f^{*}\right\|\geq\rho_{K}$. By Lemma 5,

Therefore, it will follow from Lemma 6 that

if we can prove that for all $g\in F$ such that $\|g-f^{*}\|=\rho_{K}$ one has

Let us now prove that (33) holds. Let $g\in F$ be such that $\|g-f^{*}\|=\rho_{K}$. First assume that $\left\|g-f^{*}\right\|_{L^{2}_{P}}\leq r(\rho_{K})$ so that $g\in H_{\rho_{K}}$. By definition $\sup_{z^{*}\in\Gamma_{f^{*}}(\rho_{K})}z^{*}(g-f^{*})\geq\Delta(\rho_{K})$ and, since $\rho_{K}\geq\rho^{*}$, $\rho_{K}$ satisfies the sparsity equation and thus, $\sup_{z^{*}\in\Gamma_{f^{*}}(\rho_{K})}z^{*}(g-f^{*})\geq 4\rho_{K}/5$. Therefore, thanks to (30), when $\lambda>20\epsilon r^{2}(\rho_{K})/(7\rho_{K})$, one has

Finally assume that $\|g-f^{*}\|_{L^{2}_{P}}\geq r(\rho_{K})$. Since $\sup_{z^{*}\in\Gamma_{f^{*}}(\rho_{K})}z^{*}(f-f^{*})\geq-\|f-f^{*}\|=-\rho_{K}$, it follows from (31) that

when $\lambda<10r^{2}(\rho_{K})/(331\theta_{0}^{2}\rho_{K})$.

End of the proof of Theorem 3

On the event $\Omega_{0}(K)$ of Proposition 2, ${\cal B}_{K,\lambda}(f^{*})$ is included in the ball $B(f^{*},\rho_{K})$, therefore, by definition of ${\hat{f}}_{K,\lambda}^{(1)}$ (cf. (6)),

Again, by Proposition 2, on the same event $\Omega_{0}(K)$, ${\cal B}_{K,\lambda}(f^{*})\subset B(f^{*},\rho_{K})\cap B_{2}(f^{*},r(\rho_{K}))$, hence, on $\Omega_{0}(K)\cap\Omega_{iso}(K)$, where $\Omega_{iso}(K)$ is an event defined in Lemma 4, for all $f\in{\cal B}_{K,\lambda}(f^{*})$,

where $\alpha=1/21$ according to (27). Therefore, $C_{K,\lambda}^{(2)}(f^{*})\leq\rho_{K}$, which implies that $\left\|{\hat{f}}_{K,\lambda}^{(2)}-f^{*}\right\|\leq\rho_{K}$ (cf. (6)) and that $C_{K,\lambda}^{(2)}({\hat{f}}_{K,\lambda}^{(2)})\leq\rho_{K}$ and therefore, by Lemma 4, on $\Omega_{0}(K)\cap\Omega_{iso}(K)$, either $\left\|{\hat{f}}_{K,\lambda}^{(2)}-f^{*}\right\|_{L^{2}_{P}}\leq r_{Q}(\rho_{K},\gamma_{K})$ and so $\left\|{\hat{f}}_{K,\lambda}^{(2)}-f^{*}\right\|_{L^{2}_{P}}\leq 340\theta_{0}\theta_{r}r(\rho_{K})$ or $\left\|{\hat{f}}_{K,\lambda}^{(2)}-f^{*}\right\|_{L^{2}_{P}}\geq r_{Q}(\rho_{K},\gamma_{K})$ and so

5 Conclusion to the proof of Theorem 4

First, it follows from Theorem 3 that for all $K\in[K_{1},K_{2}]$, with probability at least $1-c_{0}\exp(-c_{1}K)$, for both $j=1,2$, $f^{*}\in\cap_{J=K}^{K_{2}}R^{(j)}_{K}$, so $\widehat{K}^{(j)}\leq K$, which implies that both $f^{*}$ and $\widehat{f}_{\text{LE}}^{(j)}$ belong to $B(\widehat{f}_{K,\lambda}^{(j)},\rho_{K})$, therefore, $\left\|f^{*}-\widehat{f}_{\text{LE}}^{(j)}\right\|\leq 2\rho_{K}$.