Introduction

This work is devoted to robust algorithms in the framework of statistical learning. A recent Forbes article [53] states that "Machine learning algorithms are very dependent on accurate, clean, and welllabeled training data to learn from so that they can produce accurate results" and "According to a recent report from AI research and advisory firm Cognilytica, over 80% of the time spent in AI projects are spent dealing with and wrangling data." While some abnormal elements of the sample, or outliers, can be detected and filtered during the preprocessing steps, others are more difficult to detect: for instance, a sophisticated adversary might try to "poison" data to force a desired outcome [42]. Other seemingly abnormal observations could be inherent to the underlying data-generating process. An "ideal" learning method should not discard informative samples, while limiting the effect of individual observation on the output of the learning algorithm at the same time. We are interested in robust methods that are modelfree, and require minimal assumptions on the underlying distribution. We study two types of robustness: robustness to heavy tails expressed in terms of the moment requirements, as well as robustness to (a variant of) adversarial contamination. Heavy tails can be used to model variation and randomness naturally occurring in the sample, while adversarial contamination is a convenient way to model outliers of unknown nature.

The statistical framework used throughout the paper is defined as follows. Let (S, S ) be a measurable space, and let X ∈ S be a random variable with distribution P. Suppose that X 1 , . . . , X N are i.i.d. copies of X. Moreover, assume that F is a class of measurable functions from S to R and : R → R + , where R + is a set of non-negative integers, is a loss function. Many problems in statistical learning theory can be formulated as risk minimization of the form

We will frequently write P ( f ) or simply L ( f ) in place of the expected loss E ( f (X)). Throughout the paper, we will also assume that the minimum above is attained for some (unique) f * ∈ F (however, f * does not necessarily coincide with the global minimizer of L ( f ) over all measurable functions that might not belong to F ). For example, in the context of regression, X = (Z,Y ) ∈ R d × R, f (Z,Y ) = Y -g(Z) for some g in a class G (such as the class of linear functions), (x) = x 2 , and f * (z, y) = y-g * (z), where g * = argmin g∈G E(Yg(Z)) 2 . As the true distribution P is usually unknown, a proxy of f * is obtained via empirical risk minimization (ERM), namely fN := argmin

where P N is the empirical distribution based on the sample X 1 , . . . , X N and

Performance of any f ∈ F (in particular, fN ) is measured via the excess risk E ( f ) := P ( f ) -P ( f * ) .

The excess risk of fN is a random variable defined as

General bounds for the excess risk have been extensively studied; a small subsample of the relevant works includes the papers [57,58,31,4,7,55] and references therein. However, until recently sharp estimates were known only in the situation when the functions in the class (F ) := { ( f ), f ∈ F } are uniformly bounded, or when the envelope F (x) := sup f ∈F | ( f (x))| of the class (F ) possesses finite exponential moments. Our focus is on the situation when marginal distributions of the process { ( f (X)), f ∈ F } indexed by F are allowed to be heavy-tailed, meaning that they possess finite moments of low order only (in this paper, "low order" usually means between 2 to 4). In such cases, the tail probabilities of the random variables

, f ∈ F decay polynomially, thus rendering many existing techniques ineffective. Moreover, we consider a challenging framework of adversarial contamination where the initial dataset of cardinality N is merged with a set of O < N outliers which are generated by an adversary who has an opportunity to inspect the data, and the combined dataset of cardinality N • = N + O is presented to an algorithm; in this paper, we assume that the proportion of contamination O N (or its upper bound) is known. The approach that we propose is based on replacing the sample mean at the core of ERM by a more "robust" estimator of E ( f (X)) that exhibits tight concentration under minimal moment assumptions.

Well known examples of such estimators include the median-of-means estimator [48,2,38] and Catoni's estimator [14]. Both the median-of-means and Catoni's estimators gain robustness at the cost of being biased. The ways that the bias of these estimators is controlled is based on different principles however.

Informally speaking, Catoni's estimator relies on delicate "truncation" of the data, while the median-ofmeans (MOM) estimator exploits the fact that the median and the mean of a symmetric distribution both coincide with its center of symmetry. In this paper, we will use "hybrid" estimators that take advantage of both symmetry and truncation. This family of estimators has been introduced and studied in [46,47], and we review the construction below.

Organization of the paper.

The main ideas behind the proposed estimators are explained in Section 1.3, followed by the high-level overview of the main theoretical results and comparison to existing literature in Section 1.4. The complete statements of the key results are given in Section 2, and in Section 3 we deduce the corollaries of these results for specific examples. Finally, the main ideas and key inequalities necessary for the proofs is explained in Section 4. The remaining technical arguments are contained in the Supplementary material [41]. Finally, in Section C of the Supplement we discuss practical implementation and numerical performance of our methods on synthetic and real data.

Notation.

For two sequences a j j 1 ⊂ R and b j j 1 ⊂ R for j ∈ N, the expression a j b j means that there exists a constant c > 0 such that a j cb j for all j ∈ N; a j b j means that a j b j and b j a j . Absolute constants will be denoted c, c 1 ,C,C , etc, and may take different values in different parts of the paper. For a function h : R d → R, we define argmin

and h ∞ := ess sup{|h(y)| : y ∈ R d }. Moreover, L(h) will stand for a Lipschitz constant of h. For f ∈ F , let σ 2 ( , f ) = Var ( ( f (X))) and for any subset

Additional notation and auxiliary results are introduced on demand.

Robust mean estimators.

Let k N be an integer, and assume that G 1 , . . . , G k are disjoint subsets of the index set {1, . . . , N} of cardinality

be the empirical mean evaluated over the subsample indexed by G j . Given a convex, even function ρ : R → R + and ∆ > 0, set [48, 2, 19]. We will be interested in the situation when ρ is smooth and "shaped" like Huber's loss, in particular, that ρ is bounded and Lipschitz continuous (exact conditions imposed on ρ are specified in Assumption 1 below). Note that (1.2) defines a whole family of estimators for different values of k and n. It is instructive to consider two cases: first, when k = N (so that n = 1) and the scaling factor ∆ Var( ( f (X))) √ N, L (k) ( f ) is akin to Catoni's estimator [14], and when n is large (e.g.

is the "median-of-means type" estimator. Let us elaborate on these two cases further. Generally speaking, the estimator L (k) ( f ) is biased, and, as we already mentioned in the introduction, one way to understand the difference between Catoni's and median-of-means type estimators is via the difference in mechanisms used to control the bias. In the case of Catoni's estimator, this mechanism is based on truncating each observation at the level of order √ Nfoot_1 encoded in the choice of ∆ Var( ( f (X))) √ N, while in the case of the median-of-means estimator it relies on the approximate symmetry, implied by the Central Limit Theorem, of the distribution of the empirical averages L j ( f ), and in particular the fact that any reasonable estimator of location for this distribution will be close to the mean L ( f ) when |G j | is large. In Section 2.1, we formally introduce the key quantities that allow us to control the bias under various moment assumptions on the underlying classes. We also construct a permutation-invariant version of the estimator L (k) ( f ) that does not depend on the specific choice of the subgroups G 1 , . . . , G k . We conjecture that this estimator is more efficient than L (k) ( f ); see remark 1.1 below for more details. Next, let

Let h be a measurable, permutation-invariant function of n variables. Recall that a U-statistic of order n with kernel h based on an i.i.d. sample X 1 , . . . , X N is defined as [25] U N,n = 1

Then the permutation-invariant version of L (k) ( f ) is defined as

Finally, assuming that L (k) ( f ) provides good approximation of the expected loss

as well as its permutation-invariant analogue

of 62

as an alternative to standard empirical risk minimization (1.1). The main goal of this paper is to obtain general bounds for the excess risk of the estimators f N and f U N under minimal assumptions on the stochastic process { ( f (X)), f ∈ F }. More specifically, we are interested in scenarios when the excess risk converges to 0 at fast, or "optimistic" rates, referring to the rates faster than N -1/2 . Rate of order N -1/2 ("slow rates") are easier to establish: in particular, results of this type follow from bounds on the uniform deviations sup f ∈F L (k) ( f ) -L ( f ) that have been investigated in [47]. Proving fast rates is a more technically challenging task: to achieve the goal, we develop Bahadur-type representations [6] of the estimators L (k) ( f ) and L (k) U ( f ) that provide linear, in ( f ), approximations of these nonlinear statistics that are easier to study, and carefully analyze the remainder terms. Introduction of such representations in the framework of median-of-means estimation is one of the main technical novelties of the paper; the tools we develop could prove useful in other related problems, such as study of the asymptotic distributions of the robust estimators f N and f U N . REMARK 1.1 The main reason we introduce the permutation-invariant estimator f U N is our conjecture that it has superior, compared to f N , performance. We were able to confirm this fact numerically in our experiments; however, complete theoretical confirmation is not yet available, and requires new technical tools beyond those developed in the present work. Specifically, we conjecture that f U N is more efficient than f N : when F is finite dimensional, this means, informally, that the asymptotic distribution of √ N( f U Nf * ) has smaller variance than the asymptotic distribution of √ N( f Nf * ). In other words, the conjectured difference in performance is about the constant factors rather than the rates. Such improvements are too subtle to be captured by the non-asymptotic bounds for the excess risk that are being pursued in this work, nevertheless they are clearly noticeable in the simulations.

It should also be acknowledged that exact evaluation of the U-statistics-based estimators L (k) U ( f ) and f U N is not feasible due to the number of summands N n being very large even for small values of n. However, exact computation is typically not required, and throughout our detailed simulation studies, gradient descent methods proved to be very efficient for the problem (1.5) in scenarios like least-squares and logistic regression. These points, as well as comparison of the numerical performance of the estimators f U N and f N , are further discussed in Section C of the Supplementary material [41].

1.4 Overview of the main results and comparison to existing bounds.

Our main contribution is the proof of high-confidence bounds for the excess risk of the estimators f N and f U N . First, we show (see Theorem 2.1 and (2.4)) that the excess risk is bounded from above by the quantity of order N -1/2 (referred to as "slow rates") with exponentially high probability if

The latter is true if the class { ( f ), f ∈ F } is P-Donsker [24], in other words, if the empirical process

) converges weakly to a Gaussian limit. This result is analogous to its counterpart in the standard empirical risk minimization framework. Moreover, it is known [43,36] that in general, the N -1/2 rate for the excess risk of the empirical risk minimizers can not be improved. Our main contribution is the proof of the fact that that under additional assumption requiring that any f ∈ F with small excess risk is itself close to f * (that minimizes the expected loss), f N and f U N attain fast rates. This fact is well-known in the usual empirical risk minimization framework [10,31] but is new for the type of robust estimators considered here. We state the bounds below only for f N while the results for the U-statistics based f U N are similar, up to the change in absolute constants. In order to avoid excessive technical details at this stage, we will first illustrate our general results by stating corollaries for the popular frameworks of logistic regression and regression with quadratic loss, while the most general versions of the theorems and additional examples will be stated afterwards.

Binary classification and logistic regression. Assume that (Z,Y ) ∈ S × {±1} is a random couple where Z is an instance and Y is a binary label, and let g * (z) := E[Y |Z = z] be the regression function. It is well-known that the binary classifier b * (z) := sign(g * (z)) achieves smallest possible misclassification error defined as P (Y = g(Z)). Let F be a given convex class of functions mapping S to R, : R → R + a convex, nondecreasing, Lipschitz loss function, and let

The loss is classification-calibrated if sign(h * (z)) = b * (z) P-almost surely; we refer the reader to [9] for a detailed exposition. In the case of logistic regression considered below,

is the classification-calibrated loss and and

In this case, we will assume that f * ∈ F ; it is possible to avoid this assumption at the cost of additional technicalities and taking advantage of the deep results of S. Mendelson [45] on the multiplier inequalities.

In the statements below, we will assume that we are given an i.i.d. sample (Z 1 ,Y 1 ), . . . , (Z N ,Y N ) having the same distribution as (Z,Y ) where the marginal distribution of Z is supported on a compact set. Moreover, suppose that E|η| 8 < ∞ in the case of regression with quadratic loss; Section 3 contains other examples covering a wider class of distributions and classes F . THEOREM 1.1 (Informal) Assume the framework of either logistic regression or linear regression with quadratic loss. Then, for appropriately chosen k and ∆ ,

with probability at least 1e -s for all s k. Moreover, we construct a two-step estimator f N based on f N that is capable of achieving further improved rates. THEOREM 1.2 (Informal) Assume the framework of either logistic regression or linear regression with quadratic loss. There exists an estimator f N , defined later in the paper, such that

with probability at least 1e -s for all 1 s s max where s max := s max (N) → ∞ as N → ∞.

The estimator f N mentioned in Theorem 1.2 is based on a two-step procedure, where f N serves as an initial approximation that is refined on the second step via risk minimization restricted to a "small neighborhood" of f N . All of the bounds in this paper have the form

where 1 2 γ 1 and δ is the quantity (formally defined in (2.5)) that often coincides, up to log-factors, with the optimal rate for the excess risk [3,40] -for instance, δ d N in the examples above. In the standard empirical risk minimization, the excess risk bounds in the linear and logistic regression admit the bounds of order d N + s N , albeit under more restrictive assumptions and in the corruption-free framework. Therefore, the bound of Theorem 1.1 is suboptimal in these cases due to the "remainder terms" being of order N -3/4 , and the improvement achieved by the two-step estimator f N , as described in Theorem 1.2, becomes important.

Next, we provide a brief overview of the literature on the topic and compare our results to the state of the art. Robustness of statistical learning algorithms has been studied extensively in recent years. Existing research has mainly focused on addressing robustness to heavy tails as well as adversarial contamination. One line of work investigated robust versions of the gradient descent method for the optimization problem (1.1) based on variants of the multivariate median-of-means technique [51,16,59, 1], as well as Catoni's estimator [28]. The line works initiated in the theoretical computer science community [33,20,22, also see the survey paper [23]] tackled the problem of optimal mean estimation in the adversarial contamination framework by establishing deep connections between the mean and covariance estimation problems that culminated in the family of powerful filtering algorithms; these algorithms can also be used as subroutines in robust gradient descent-type methods [21,17]. While these algorithms admit strong theoretical guarantees, they require robustly estimating the gradient vector at every step (with the exception of [21] that offers a more efficient approach) hence are computationally demanding; moreover, results are weaker for losses that are not strongly convex (for instance, the hinge loss). The line of research that is closest in spirit to the approach of this paper includes the works that employ robust risk estimators based on Catoni's idea [5,13,27] and the median-of-means technique, such as "tournaments" and the "min-max median-of-means" [40,39,34,35,18], also see [17,29] for the computationally efficient algorithms related to the tournament-type procedures. As it was mentioned in the introduction, the core of our methods can be viewed as a "hybrid" between Catoni's and the medianof-means estimators. We provide a more detailed comparison to the results of the aforementioned papers:

1. We show that risk minimization based on a version of Catoni's estimator is capable of achieving fast rates, thus improving the results and weakening the assumptions stated in [13] that only allowed the slow rates to be established; 2. We develop new tools and techniques to analyze proposed estimators. In particular, we do not rely on the "small ball" method [32,44] and the standard "majority vote-based" analysis [34,40] of the median-of-means estimators. Instead, we provide accurate bounds for the bias and investigate the remainder terms for the Bahadur-type linear approximations of the estimators defined in (1.2). In particular, we demonstrate that the order of typical deviations of the estimator L (k) ( f ) around L ( f ) are significantly smaller than the deviations of the subsample averages L j ( f ), which is not easy to do using the majority vote-based proof techniques; consequently, this fact allows us to "decouple" the confidence parameter s that controls the deviation probabilities from parameters k and O responsible for the number of subsamples and the degree of contamination respectively. Unlike the tournaments-based estimators, in some regimes our algorithms admit a "universal" choice of k that is independent of the parameter δ controlling the optimal rate. In the previous works, parameter k was often overloaded as it controlled the deviation probabilities while depending on δ (or a closely related quantity) at the same time. Finally, our techniques allow us to establish bounds that are uniform over a certain range of confidence parameter s while the previously existing deviation results were only available for s k. 3. We are able to simultaneously treat the case of Lipschitz as well as non-Lipschitz (e.g., quadratic) loss functions . At the same time, in some situations (e.g. linear regression with quadratic loss), the required assumptions are stronger compared to the best results in the literature tailored specifically to the task, e.g. [34,40] that treat the case of regression with quadratic loss. 4. Existing approaches based on the median-of-means estimators are either computationally intractable [40], or outputs of practically efficient algorithms do not admit strong theoretical guarantees [34,35,18]. We design numerical algorithms specifically for the estimators f N and f U N defined via (1.4) and (1.5), and show that they enjoy good performance in numerical experiments as well as strong theoretical guarantees.

Theoretical guarantees for the excess risk.

In this section, we give complete statements of the main results and explain the high-level ideas behind their proofs.

Preliminaries.

We start by introducing the main quantities that appear in our results, and state the key assumptions. Recall that σ 2 ( , F ) stands for sup f ∈F σ 2 ( , f ), where F ⊆ F . The loss functions ρ that will be of interest to us satisfy the following assumption.

Assumption 1 Suppose that the function ρ : R → R is convex, even, 5 times continuously differentiable and such that (i) ρ (z) = z for |z| 1 and ρ (z) = const for z 2, (ii) z -ρ (z) is nondecreasing.

An example of a function ρ satisfying required assumptions is given by "smoothed" Huber's loss defined as follows. Let

be the usual Huber's loss. Moreover, let φ be the "bump function"

where C is chosen so that R φ (x)dx = 1. Then ρ given by the convolution ρ(x) = (h * φ )(x) satisfies Assumption 1.

REMARK 2.1 (a)

The requirements that ρ is 5 times continuously differentiable is of the technical nature and is likely not necessary. It appears due to the fact that we need to control higher order terms in the Bahadur-Kiefer type representations of the estimator L (k) ( f ), as well as rely on the Lindeberg replacement-type arguments in our proofs. (b) The derivative ρ has a natural interpretation of being a smooth version of the truncation function.

Moreover, observe that ρ (2) -2 ρ (1) -1 = 0 by (ii), hence ρ ∞ 2. It is also easy to see that for any x > y, ρ (x) -ρ (y) = y -ρ (y) -(x -ρ (x)) + x -y x -y, hence ρ is Lipschitz continuous with Lipschitz constant L(ρ ) = 1.

In Section 1.3, we have briefly discussed the bias of robust mean estimators and various ways that it can be controlled. Now we will introduce the key quantities necessary to make the bounds precise. Everywhere below, Φ(•) stands for the cumulative distribution function of the standard normal random variable and W ( f ) denotes a random variable with distribution N 0,

where P f := E f (X). In other words, M f (t, n) controls the rate of convergence in the central limit theorem. It follows from the results of L. Chen and Q.-M. Shao (Theorem 2.2 in [15]) that

given that the absolute constant C is large enough. Note that, crucially, the control of the rate in terms of g f (t, n) is non-uniform, since g f (t, n) is a decreasing function of t. Moreover, let

The quantity

plays the key role in controlling the bias of the estimator L (k) ( f ): it decreases both as ∆ get large and as the subsample size n increases, referring to different bias-controlling mechanisms of Catoni's and the median-of-means type estimators, see discussion after (1.2). The following statement provides simple upper bounds for g f (t, n) and G f (n, ∆ ) that depend on the tail properties of f (X); its proof can be found in [47,Section 4.4]. LEMMA 2.1 Let X 1 , . . . , X n be i.i.d. copies of X, and assume that Var(

where C ,C > 0 are absolute constants.

We can rewrite the bound for sup

, where the numerator sup

is the quantity akin the kurtosis while the ratio M ∆ := ∆ σ ( ,F ) appearing in the denominator can be interpreted as a truncation level expressed in the "units" of σ ( , F ). This "truncation level," along with the subgroup size n, are the two main quantities controlling the bias of the estimators L (k) ( f ), f ∈ F .

Slow rates for the excess risk.

Let

be the excess risk of f N and its permutation-invariant analogue f U N which are the main objects of our interest. The following bound for the excess risk is well known in the empirical risk minimization literature [31], and it easily leads to control of the excess risk in terms of the uniform deviations of robust mean estimators.

The first result, Theorem 2.1 below, together with the inequality (2.2) immediately implies the "slow rate bound" (meaning rate not faster than N -1/2 ) for the excess risk. This result has been previously established in [47]. Define ∆ := max (∆ , σ ( , F )) .

THEOREM 2.1 There exist absolute constants c, C > 0 such that for all s > 0, n and k satisfying

the following inequality holds with probability at least 1 -2e -s :

Moreover, the same bounds hold for the permutation-invariant estimators L An immediate corollary is the bound for the excess risk

that holds under the assumptions of Theorem 2.1 with probability at least 1 -2e -s . When the class

3) holds for N large enough whenever s is not too big and ∆ and k are not too small, namely, s c k and ∆ √ k c σ (F ). The bound of Theorem 2.1 also suggests that the natural "unit" to measure the magnitude of the parameter ∆ is σ ( , F ).

To put these results in perspective, let us consider two examples. First, assume that n = 1, k = N and set ∆ = ∆ (s) := σ (F ) N s for s c N. Using Lemma 2.1 with δ = 0 to estimate G f (n, ∆ ), we deduce that

with probability at least 1-2e -s . This inequality improves upon excess risk bounds obtained for Catonitype estimators in [13], as it does not require functions in F to be uniformly bounded.

The second case we consider is when N n 2. For the choice of ∆ σ ( , F ), the estimator L (k) ( f ) most closely resembles the median-of-means estimator, as we have explained in Section 1.3. In this case, Theorem 2.1 yields the excess risk bound of the form

that holds with probability 1 -2e -s for all s c k. As sup f ∈F G f (n, ∆ ) is small for large n and [35] that provides bounds for the excess risk for robust classifiers based on the the median-of-means estimators.

Towards fast rates for the excess risk.

It is well known that in regression and binary classification problems, the excess risk often converges to 0 at a rate faster than N -1/2 , and could be as fast as N -1 . Such rates are often referred to as "fast" or "optimistic" rates. In particular, this is the case when there exists a "link" between the excess risk and the variance of the loss class, namely, if for some convex nondecreasing and nonnegative function φ such that φ (0) = 0,

It is thus natural to ask if fast rates can be attained by estimators produced by the robust algorithms proposed above. Results presented in this section give an affirmative answer to this question. Let us introduce the main quantities that commonly appear in the excess risk bounds [31, 40]. For δ > 0, let

Moreover, define F ) .

The following condition, known as Bernstein's condition following [10], plays the crucial role in the analysis of excess risk bounds.

Assumption 2 There exist constants

Informally speaking, Assumption 2 postulates that any f ∈ F (more precisely, the loss ( f ) induced by it) with small excess risk is itself close to f * . If this is true, it turns out that one can avoid global bounds on the expected supremum of the empirical process used to obtain "slow" rates, and instead rely on the modulus of continuity ω(δ ) of the empirical process locally in the neighborhood of ( f * ) in order to get better upper bounds on the excess risk. The basics of this approach in the classical empirical risk minimization frameworks are clearly explained in [31, Chapter 1.2], and we rely on similar ideas below. Assumption 2 is known to hold in many concrete cases of prediction and classification tasks, and we provide examples and references in Section 3 below. More general versions of the Bernstein's condition are often considered in the literature: for instance, it can be replaced by assumption requiring that Var ( ( f (X)) -( f * (X))) D 2 (E ( f )) τ for some τ ∈ (0, 1], as was done in [10]; clearly, our assumption corresponds to τ = 1. Results of this paper admit straightforward extensions to the slightly less restrictive scenario when τ < 1; we omit the details to reduce the level of technical burden on the statements of our results.

Following [31, Chapter 4], we will say that the function ψ :

x is decreasing. Moreover, if for some γ ∈ (0, 1)

x γ is decreasing, we will say that ψ is of strictly concave type with exponent γ. We will assume that ω(δ ) admits an upper bound ω(δ ) of strictly concave type (with some exponent γ), and that ν(δ ) admits an upper bound ν(δ ) of concave type. For instance, when Assumption 2 holds, ν(δ ) D √ δ for δ δ B , implying that ν(δ ) = D √ δ is an upper bound for ν(δ ) of strictly concave type with γ = 1 2 . 2 Moreover, the function ω(δ ) often admits an upper bound of the form ω(δ

where R 1 and R 2 do not depend on δ ; such an upper bound is also of concave type. Next, set

where C 1 (ρ) is a sufficiently large positive constant that depends only on ρ. The quantity δ often coincides with the optimal rates for the excess risk in the classical empirical risk minimization framework: for example, it is of order d N up to logarithmic factors in linear regression with quadratic loss and in logistic regression when Bernstein's condition is satisfied; in general, the order of δ ranges between the pessimistic N -1/2 in "hard" problems and "optimistic" N -1 where the rates between correspond to weaker versions of Assumptions 2, for instance, see [9]. The theorems below provide estimates for the excess risk of robust risk minimizers under various conditions on the tails of the random variables { f (X), f ∈ F }. All these bounds have the same structure that includes the term δ as well as the "remainder terms" that account for the bias of the robust risk estimators L (k) ( f ) as well as the outlier contamination proportion O N ; naturally, stricter moment conditions result in better remainder terms. THEOREM 2.2 Assume that conditions of Theorem 2.1 hold. Additionally, suppose that

with probability at least 1 -10e -s , where the constant C(ρ) depends on ρ only and D is a constant appearing in Assumption 2.

Under stronger moment assumptions, the excess risk bound can be strengthened and take the following form.

THEOREM 2.3 Assume that conditions of Theorem 2.1 hold. Additionally, suppose that

with probability at least 1 -10e -s , where the constant C(ρ) depends on ρ only and D is a constant appearing in Assumption 2.

The main ideas behind the proofs of Theorems 2.2 and 2.3 are explained in the beginning of Section 4.

REMARK 2.2 1. The bounds of Theorems 2.2 and 2.3 hold for the excess risk δ U N of the permutation-invariant estimator f U N , up to a change in absolute constants. 2. It is evident that whenever O = 0, the best possible rates implied by Theorem 2.2 are of order N -2/3 (indeed, this is the case whenever M ∆ √ n N 1/3 and δ N -2/3 ), while the best possible rates attained by Theorem 2.3 are of order N -3/4 (when M ∆ √ n N 1/4 and δ N -3/4 ); in particular, in this case the choice of M ∆ and n is independent of δ . In general, if O = εN for ε > 0, the best rates implied by Theorems 2.2 and 2.3 are δ +C(F , ρ, P)ε 2/3 and δ +C(F , ρ, P)ε 3/4 respectively. 3. Assumption requiring that M ∆ 1 is introduced for convenience: without it, extra powers of the ratio max(∆ ,σ ( ,F )) ∆ appear in the bounds.

Our next goal is to describe an estimator that is capable of achieving excess risk rates up to N -1 . The approach that we follow is similar in spirit to the "minmax" estimators studied in [5,38,34], among others, as well as the "median-of-means tournaments" introduced in [40]; all these methods focus on estimating the differences L ( f 1 ) -L ( f 2 ) for all f 1 , f 2 ∈ F . Recall that f * = argmin f ∈F P ( f ), and observe that for any fixed f ∈ F , f * can be equivalently defined via

A version of the robust empirical risk minimizer (1.4) corresponding to this problem can be defined as

for appropriately chosen ∆ > 0, and

Moreover, if f ∈ F is a priori known to be "close" to f * , then it suffices to search for the minimizer in a neighborhood F of f that contains f * instead of all f ∈ F :

The advantage gained by this procedure is expressed by the fact that sup f ∈F Var ( ( f (X)) -( f (X))) can be much smaller than σ ( , F ).

We will now formalize this argument and provide performance guarantees; we use the framework of Theorem 2.3 which leads to the bounds that are easier to state and interpret. However, similar reasoning applies to the setting of Theorem 2.2 as well. The presented algorithms also admit straightforward permutation-invariant modifications that we omit. Let

be the "empirical excess risk" of f . Indeed, this is a meaningful notion as f N is the minimizer of L (k) ( f ) over f ∈ F . Assume that the initial sample of size N is split into two disjoint parts S 1 and S 2 of cardinalities that differ by at most 1:

The algorithm proceeds in the following way:

N/2 , with the scale parameter ∆ 1 and the partition parameter k 1 corresponding the group size

be a known upper bound on the excess risk in Theorem 2.3 (while this condition is restrictive, it is similar to the requirements of existing approaches [13,40]; discussion of adaptation issues is beyond the scope of this paper and will be addressed elsewhere). Set

where

, a scale parameter ∆ 2 and the partition parameter k 2 corresponding the group size

It will be demonstrated in the course of the proofs that on an event of high probability, F (δ ) ⊆ F (cδ ) for an absolute constant c 7. Hence, on this event sup

1. Moreover, assume that for a suf-

c . Finally, we require that

with probability at least 1 -20e -s , where C(ρ) depends on ρ only and D is the constant appearing in Assumption 2.

The statement of Theorem 2.4 is technical, so let us try to distill the main ideas. The key difference between Theorem 2.3 and Theorem 2.4 is that the "remainder term"

, this term often becomes negligible. To be more specific, assume that δ = C(F ) √ N • h(N) where h(N) → 0 as N → ∞ (meaning that fast rates are achievable) and that O = ε N for ε

and the excess risk of f N admits the bound

that holds with probability at least 1 -Ce -s . A possible choice satisfying all the required conditions is k j N √ ε, j = 1, 2 (indeed, it this case it is straightforward to check that conditions (2.6) hold for sufficiently large N as k j √ N, j = 1, 2). Analysis of the case when O = 0 follows similar steps, with several simplifications.

Examples.

In this section, we consider two common prediction problems, regression and binary classification, and discuss the implications of our main results for these problems in detail.

Binary classification with convex surrogate loss.

The key elements of the binary classification framework were outlined in Section 1.4. Here, we recall few popular examples of classification-calibrated losses and present conditions that are sufficient for the Assumption 2 to hold.

Logistic loss (y f (z)) = log 1 + e -y f (z) . Consider two scenarios:

1. Uniformly bounded classes, meaning that for all f ∈ F , sup z∈S | f (z)| B. In this case, Assumption 2 holds with D = 2e B for all f ∈ F . See [8] and Proposition 6.1 in [3]. 2. Linear separators and Gaussian design: in this case, we assume that S = R d , Z ∼ N(0, I) is Gaussian, and F = { •, v : v 2 R} is a class of linear functions. In this case, according to the Proposition 6.2 in [3], Bernstein's assumption is satisfied with D = cR 3/2 for some absolute constant c > 0.

Hinge loss (y f (z)) = max (0, 1y f (z)). In this case, sufficient condition for Assumption 2 to hold is the following: there exists τ > 0 such that |g * (Z)| τ almost surely, where g

It follows from Theorem 7 in [8] (see also [55]) that Assumption 2 holds with D = 1 √ 2τ in this case.

Bound for δ . Let Π stand for the marginal distribution of Z and recall that ω(δ

Since is Lipschitz continuous by assumption (with Lipschitz constant denoted L( )), consequent application of symmetrization and Talagrand's contraction inequalities [37,56] yields that

where ε 1 , . . . , ε N are i.i.d. random signs independent from Y j 's and Z j 's. The latter quantity is the mod- ulus of continuity of a Rademacher process, and various upper bounds for it are well known. For instance, if F is a subset of a linear space of dimension d, then, according to Proposition 3.2 in [31],

More generally, assume that the class F has a measurable envelope F(z)

is the ψ 2 (Orlicz) norm. Moreover, suppose that the covering numbers N (F , Q, ε) of the class F with respect to the norm L 2 (Q) 3 satisfy the bound

and all probability measures Q. For instance, VC-subgraph classes are known to satisfy this bound with V being the VC dimension of F [58,31].

In this case, it is not difficult to show (see for example the proof of Lemma 3.1 in the Supplementary material [41]) that

hence it is easy to check that in this case

It immediately follows from the discussion following Theorem 2.4 that the excess risk of the estimator

with probability at least 1-20e -s . Note that we did not need to assume that h * := argmin

belongs to F . Similar results hold for regression problems with Lipschitz losses, such as Huber's loss or quantile loss [3].

Regression with quadratic loss.

Let X = (Z,Y ) ∈ S × R be a random couple with distribution P satisfying Y = f * (Z) + η where the noise variable η is independent of Z and f

Pr(|η| > t)dt, and observe that η 2,1 < ∞ as sup f ∈F E(Yf (Z)) 4 < ∞ by assumption. As 3 Definition: the covering number N (F , Q, ε) is the smallest integer k 1 such that there exist f 1 , . . . ,

before, Π will stand for the marginal distribution of Z. Let F be a given convex class of functions mapping S to R and such that the regression function f * belongs to F , so that

In this case, the natural choice for the loss function is the quadratic loss (x) = x 2 which is not Lipschitz continuous on unbounded domains. Assume that the class F has a measurable envelope

Moreover, suppose that the covering numbers N (F , Q, ε) of the class F with respect to the norm L 2 (Q) satisfy the bound

, and all probability measures Q (see remark about VC-subgraph classes following display (3.1)).

Verification of Bernstein's assumption. It follows from Lemma 5.1 in [31] that

2δ so D can be taken to be √ 2 in Assumption 2. Bound for δ . Required estimates follow from the following lemma: LEMMA 3.1 Under the assumptions made in this section and for ∆ σ ( , F ),

Moreover, if the functions if F are uniformly bounded, the log 2 (A 2 N) can be removed.

The proof is given in Section A.9 of the Supplementary material [41]. An immediate corollary of the lemma, according to the discussion following Theorem 2.4, is that the excess risk of the estimator f N satisfies the inequality

Proofs of the main results.

In the proofs of the main results, we will rely on the following convenient change of variables. Denote

In particular, when

) and e (k) ( f ) be defined by the equations

Comparing this to the definition of

Let us explain the main high-level ideas behind the proof. In the classical empirical risk minimization framework, L (k) ( f ) is replaced by the empirical mean

we would be able to write that

It would then suffice to find a good upper bound for the supremum on the right side of (4.1) and solve the resulting inequality to get an upper bound for δ N . However, this argument does not work directly due to the lack of linearity. Instead, we use Bahadur-type representation of the e (k) ( f ) to introduce linearity into the problem. Specifically, we will show that e (k)

where r N ( f ) is a small remainder term and ∂ z G k (0; f ) is the partial derivative of G k (z; f ) with respect to z evaluated in z = 0. The process G k (0; f ) is "almost" linear in ( f ), the only obstacle being the nonlinearity due to ρ . Mimicking (4.1), we can write that

can be tackled with the techniques commonly used to estimate suprema of the empirical processes; in particular, symmetrization and contraction inequalities for Rademacher sums [37] are used to remove the additional nonlinearity in the definition of G k (z, f ) introduced by ρ . At that point, one only needs to carefully estimate the remainder term r N .

Technical tools.

We summarize the key results that our proofs rely on. Var (Y ) .

Proof. See Lemma 5.3 in [47].

LEMMA 4.2 For any function h of with bounded third derivative and a sequence of i.i.d. random variables ξ 1 , . . . , ξ n such that Eξ 1 = 0 and

where C > 0 is an absolute constant and Z 1 , . . . , Z n are i.i.d. centered normal random variables such that Var(Z 1 ) = Var(ξ 1 ).

Proof. This bound follows from a standard application of Lindeberg's replacement method; see chapter 11 in [49].

, where γ 2 (F , L ∞ (Π N )) is Talagrand's generic chaining complexity [54]. LEMMA 4.4 Let σ 2 := sup f ∈G E f 2 (X). Then there exists a universal constant C > 0 such that

Proof. See Theorem 3.16 in [31].

The following form of Talagrand's concentration inequality is due to Klein and Rio (see Section 12.5 in [12]).

LEMMA 4.5 Let {Z j ( f ), f ∈ F }, j = 1, . . . , N be independent (not necessarily identically distributed) separable stochastic processes indexed by class F and such that |Z j ( f ) -EZ j ( f )| M a.s. for all 1 j N and f ∈ F . Then the following inequality holds with probability at least 1e -s :

where

with probability at least 1e -s .

4.2 Proof of Theorems 2.2 and 2.3.

We will provide detailed proofs for the estimator f N that is based on disjoint subsamples indexed by G 1 , . . . , G k . The bounds for its permutation-invariant version f U N follow exactly the same steps where all applications of the Talagrand's concentration inequality (Lemma 4.5) should be replaced by its version (B.3) for nondegenerate U-statistics stated in Section B of the Supplementary material [41].

Let J ⊂ {1, . . . , k} of cardinality |J| k -O be the set containing all j such that the subsample {X i , i ∈ G j } does not include outliers. Clearly, {X i : i ∈ G j , j ∈ J} are still conditionally i.i.d. as the partitioning scheme is independent of the data. Moreover, set N J := ∑ j∈J |G j |, and note that, since

Consider stochastic process R N ( f ) defined as

where

Whenever ∂ z G k (0; f ) = 0 (this assumption will be justified by Lemma 4.6 below), we can solve (4.3) for e (k) ( f ) to obtain

which can be viewed as a Bahadur-type representation of e (k) ( f ). Setting f := f N and recalling that e (k) ( f ) = L (k) ( f ) -L ( f ), we deduce that

Rearranging the terms, it is easy to see that

It follows from (4.5) that in order to estimate the excess risk of f N , it suffices to obtain the upper bounds for

Observe that

Since ρ is Lipschitz continuous by assumption,

The following two lemmas are required to proceed.

LEMMA 4.6 There exist C(ρ) > 0 such that for any f ∈ F ,

Proof. See Section A.1.

In particular, the bound of Lemma 4.6 implies that for n large enough, inf

It is also easy to deduce from the proof of Lemma 4.6 that for small n and

∆ for some positive c(ρ). LEMMA 4.7 For any f ∈ F ,

with probability at least 1 -2e -s , where C > 0 is an absolute constant.

Proof.

See Section A.2. Lemma 4.7 and (4.7) imply, together with (4.6), that

on event Θ 1 of probability at least 1 -2e -s . As ∆ σ ( , F ) by assumption, we deduce that

Define

where C 1 (ρ) is sufficiently large. It is easy to see that on event

for appropriately chosen C 1 (ρ).

Our next goal is to obtain an upper bound for

. To this end, we will need to control the local oscillations of the process G k (0; f ). Specifically, we are interested in the bounds on the random

The following technical lemma is important for the analysis.

LEMMA 4.8 Let (ξ 1 , η 1 ), . . . , (ξ n , η n ) be a sequence of independent identically distributed random cou- ples such that Eξ 1 = 0, Eη 1 = 0, and

Let F be an odd, smooth function with bounded derivatives up to fourth order. Then

Moreover, if ω(δ ) and ν(δ ) are upper bounds for ω(δ ) and ν(δ ) and are of concave type, then

where c(γ) > 0 depends only on γ, is also an upper bound for U(δ , s) of strictly concave type. Moreover, define

where ν 4 (δ ) upper bounds ν 4 (δ ) and is of concave type. Below, we will use a crude bound ν 4 (δ ) 2R 4 ( , F ), but additional improvements are possible if better estimates of ν 4 (δ ) are available. LEMMA 4.9 With probability at least 1e -2s , sup

where C(ρ) > 0 is constant that depends only on ρ.

Proof. See Section A.4. Next, we state the "uniform version" of Lemma 4.9.

LEMMA 4.10 With probability at least 1e -s , for all δ δ min simultaneously, sup

where C(ρ) > 0 is constant that depends only on ρ.

Proof. See Section A.5. It follows from Lemma 4.10 and inequality (4.7) that on event Θ 2 of probability at least 1 -e -s , for all δ δ min simultaneously,

where C 2 (ρ), C 3 (ρ) are sufficiently large constants. Then, on event

for appropriately chosen C 2 (ρ),C 3 (ρ). Finally, we provide an upper bound for the process R N ( f ) defined via

LEMMA 4.11 Assume that conditions of Theorem 2.1 hold, and let δ min > 0 be fixed. Then for all s > 0, δ δ min , positive integers n and k such that

the following inequality holds with probability at least 1 -7e -s , uniformly over all δ satisfying (4.12):

Moreover, the bound of Theorem 2.1 holds on the same event.

Proof. See Section A.6. Recall that

where C 2 (ρ) is a large enough constant. Let Θ 3 be the event of probability at least 1 -7e -s on which Lemma 4.11 holds with δ min = δ 2 , and consider the event Θ 3 ∩ { δ N > δ 2 }. We will now show that on this event, Lemma 4.11 applies with δ = δ N . Indeed, the bound of Theorem 2.1 is valid on Θ 3 , hence the inequality (2.4) implies that on Θ 3 , δ N C(ρ) ∆ √ n , and it is straightforward to check that condition (4.12) of Lemma 4.11 holds with δ min = δ 2 and δ = δ N . It follows from inequality (4.7) that on event

Consider the expression

and observe that whenever Theorem 2.1 holds, n 1/2 δ N ∆ c(ρ), hence the latter is bounded from above by

Combining the inequalities obtained above, we deduce on event

where C 4 (ρ) is sufficiently large. Then on event Θ 3 ∩ δ N max δ 2 , 7δ 4 ,

Note that the expression above takes care of the term 4 ∆ √ n O N that appeared in (4.11). Combining (4.9), (4.11), (4.13), we deduce that on event Θ 1 ∩Θ 2 ∩Θ 3 ∩ δ N max δ 1 , δ 2 , δ 3 , 7 δ 4 ,

leading to a contradiction, hence on event Θ 1 ∩Θ 2 ∩Θ 3 of probability at least 1 -10e -s , δ N max δ 1 , δ 2 , δ 3 , 7δ 4 . (4.14)

Recall the definition (4.8) of δ 1 . If condition 2 ("Bernstein condition") holds, then ν(δ ) D √ δ for small enough δ , in which case

where we used the fact that s k c by assumption. Together with the bound (2.1) for G f * (n, ∆ ), we deduce that, under the assumption that R 4 ( , F ) < ∞,

, where

.15)

At the same time, if only σ ( , F ) < ∞, we similarly obtain that

.16)

Next we will estimate δ 3 . Recall that, when R 4 ( , F ) < ∞,

For sufficiently small δ (namely, for which condition 2 holds) and ∆ σ ( , F ), , and it is easy to deduce that in this case, Recall that E N ( f * ) := L (k) ( f * ) -L (k) ( f N ) is the "empirical excess risk" of f * , and let δ N := E ( f N ). It follows from Remark 4.1 that (using the notation used in the proof of Theorems 2.2 and 2.3)

On the event of Theorem 2.3 of probability at least 1 -10e -s ,

hence on this event

where the last inequality again follows from main steps in the proof of Theorem 2.3; note that similar result holds if δ is replaced by its analogue from Theorem 2.3. Consider the set F (δ ) = f ∈ F : E N ( f ) δ .

First, observe that on the event of Theorem 2.3, f * ∈ F (δ ) as implied by the previous display. We will next show that F (δ ) ⊆ F (7δ ) on the event E 1 of Theorem 2.3, meaning that for any f ∈ F (δ ), E ( f ) 7δ . Indeed, let f ∈ F (δ ) be such that E ( f ) = σ . Then (4.4) implies that

Again, it follows from the arguments used in proof of Theorem 2.3 that on event E 1 of probability at least 1 -10e -s , sup

max δ , σ .

Consequently, σ δ + 6 7 max (δ , σ ) on this event, implying that σ 7δ . Next, Assumption 2 yields that

To this end, we need to verify the assumption of Theorem 2.1 that translates into the requirement

As δ > δ and |S 2 | N/2 , we have the inequality

hence it suffices to check that

that holds by assumption. Result now follows easily as we assumed that the subsamples S 1 and S 2 used to construct f N and f N are disjoint.