Timothée Mathieu
email: timothee.mathieu@u-psud.fr

Stanislav Minsker
email: minsker@usc.edu

Excess risk bounds in robust empirical risk minimization

Keywords: robust estimation, excess risk, median-of-means, regression, classification. 1

This paper investigates robust versions of the general empirical risk minimization algorithm, one of the core techniques underlying modern statistical methods. Success of the empirical risk minimization is based on the fact that for a "well-behaved" stochastic process tf pXq, f P F u indexed by a class of functions f P F , averages 1 N ř N j"1 f pX j q evaluated over a sample X 1 , . . . , X N of i.i.d. copies of X provide good approximation to the expectations Ef pXq uniformly over large classes f P F . However, this might no longer be true if the marginal distributions of the process are heavy-tailed or if the sample contains outliers. We propose a version of empirical risk minimization based on the idea of replacing sample averages by robust proxies of the expectation, and obtain high-confidence bounds for the excess risk of resulting estimators. In particular, we show that the excess risk of robust estimators can converge to 0 at fast rates with respect to the sample size. We discuss implications of the main results to the linear and logistic regression problems, and evaluate the numerical performance of proposed methods on simulated and real data.

Introduction

This work is devoted to robust algorithms in the framework of statistical learning. A recent Forbes article [START_REF] Schmelzer | The Achilles' Heel Of AI[END_REF] 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 samples, 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 [START_REF] Mayzlin | Promotional reviews: An empirical investigation of online review manipulation[END_REF]. 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 model-free, 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 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 pS, Sq be a measurable space, and let X P 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 `is a loss function. Many problems in statistical learning theory can be formulated as risk minimization of the form E pf pXqq Ñ min f PF .

We will frequently write P pf q or simply Lpf q in place of the expected loss E pf pXqq. Throughout the paper, we will also assume that the minimum is attained for some (unique) f ˚P F. For example, in the context of regression, X " pZ, Y q P R d ˆR, f pZ, Y q " Y ´gpZq for some g in a class G (such as the class of linear functions), pxq " x 2 , and f ˚pz, yq " y ´g˚p zq, where g ˚pzq " E rY |Z " zs is the conditional expectation. As the true distribution P is usually unknown, a proxy of f ˚is obtained via empirical risk minimization (ERM), namely fN :" argmin

f PF L N pf q, (1.1)
where P N is the empirical distribution based on the sample X 1 , . . . , X N and L N pf q :" P N f " 1 N N ÿ j"1 pf pX j qq .

Performance of any f P F (in particular, fN ) is measured via the excess risk Epf q :" P pf q ´P pf ˚q .

The excess risk of fN is a random variable Ep fN q :" P `f N ˘´P pf ˚q " E " `f pXq ˘|X 1 , . . . , X N ı ´E pf ˚pX qq .

General bounds for the excess risk have been extensively studied; a small subsample of the relevant works includes the papers [START_REF] Van De Geer | Empirical Processes in M-estimation 6[END_REF][START_REF] Wellner | Weak convergence and empirical processes: with applications to statistics[END_REF][START_REF] Koltchinskii | Oracle inequalities in empirical risk minimization and sparse recovery problems[END_REF][START_REF] Anthony | Neural network learning: Theoretical foundations[END_REF][START_REF] Bartlett | Local rademacher complexities[END_REF][START_REF] Tsybakov | Optimal aggregation of classifiers in statistical learning[END_REF] and references therein. However, until recently sharp estimates were known only in the situation when the functions in the class pFq :" t pf q, f P Fu are uniformly bounded, or when the envelope F pxq :" sup f PF | pf pxqq| of the class pFq possesses finite exponential moments. Our focus is on the situation when marginal distributions of the process t pf pXqq, f P Fu 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

! 1 ? N
ř N j"1 pf pX j qq ´E pf pXqq, f P 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 that is at the core of ERM by a more "robust" estimator of E pf pXqq that exhibits tight concentration under minimal moment assumptions. Well known examples of such estimators include the median-of-means estimator [START_REF] Nemirovski | Problem complexity and method efficiency in optimization[END_REF][START_REF] Alon | The space complexity of approximating the frequency moments[END_REF][START_REF] Lerasle | Robust empirical mean estimators[END_REF]] and Catoni's estimator [START_REF] Catoni | Challenging the empirical mean and empirical variance: a deviation study[END_REF]. 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-of-means (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 [START_REF] Minsker | Distributed statistical estimation and rates of convergence in normal approximation[END_REF][START_REF] Minsker | Uniform bounds for robust mean estimators[END_REF], 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. [START_REF] Anthony | Neural network learning: Theoretical foundations[END_REF]. In Section 2, we discuss practical implementation and numerical performance of our methods for two problems, linear regression and binary classification. The complete statements of the key results are given in Section 3, and in Section 4 we deduce the corollaries of these results for specific examples. Finally, the architecture of the proofs is explained in Section 5, while the remaining technical arguments and additional numerical results are contained in the appendix.

Notation.

For two sequences ta j u jě1 Ă R and tb j u jě1 Ă R for j P N, the expression a j À b j means that there exists a constant c ą 0 such that a j ď cb j for all j P 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 1 , etc, and may take different values in different parts of the paper. For a function h : R d Þ Ñ R, we define argmin yPR d hpyq " ty P R d : hpyq ď hpxq for all x P R d u, and }h} 8 :" ess supt|hpyq| : y P R d u. Moreover, Lphq will stand for a Lipschitz constant of h. For f P F, let σ 2 p , f q " Var p pf pXqqq and for any subset F 1 Ď F, denote σ 2 p , F 1 q " sup f PF 1 σ 2 p , f q. 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 t1, . . . , N u of cardinality |G j | " n ě tN {ku each. Given f P F, let s L j pf q :" 1 n ÿ iPGj pf pX i qq be the empirical mean evaluated over the subsample indexed by G j . Given a convex, even function ρ : R Þ Ñ R `and ∆ ą 0, set p L pkq pf q :" argmin yPR k ÿ j"1 ρ ˆ?n s L j pf q ´y ∆ ˙.

(1.2)

Clearly, if ρpxq " x 2 , p L pkq pf q is equal to the sample mean. If ρpxq " |x|, then p L pkq pf q is the medianof-means estimator [START_REF] Nemirovski | Problem complexity and method efficiency in optimization[END_REF][START_REF] Alon | The space complexity of approximating the frequency moments[END_REF][START_REF] Devroye | Sub-Gaussian mean estimators[END_REF]. We will be interested in the situation when ρ is similar to Huber's loss, whence ρ1 is bounded and Lipchitz continuous (exact conditions imposed on ρ are specified in Assumption 1 below). It is instructive to consider two cases: first, when k " N (so that n " 1) and ∆ -a Varp pf pXqqq ? N , p L pkq pf q is akin to Catoni's estimator [START_REF] Catoni | Challenging the empirical mean and empirical variance: a deviation study[END_REF], and when n is large and ∆ -a Varp pf pXqqq, we recover the "median-of-means type" estimator. 1 We also construct a permutation-invariant version of the estimator p L pkq pf q that does not depend on the specific choice of the subgroups G 1 , . . . , G k . Define A pnq N :" tJ : J Ď t1, . . . , N u, CardpJq " nu .

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 [START_REF] Hoeffding | A class of statistics with asymptotically normal distribution[END_REF] U N,n " 1 `N n ˘ÿ JPA pnq N h ptX j u jPJ q .

(1. Then the permutation-invariant version of p L pkq pf q is naturally defined as p L pkq U pf q :" argmin zPR U N,n pz; f q.

(1.4)

Finally, assuming that p L pkq pf q provides good approximation of the expected loss Lpf q of each individual f P F, it is natural to consider

p f N :" argmin f PF p L pkq pf q, (1.5)
as well as its permutation-invariant analogue

p f U N :" argmin f PF p L pkq U pf q (1.6)
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 p f N and p f U N under minimal assumptions on the stochastic process t pf pXqq, f P Fu. 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 PF ˇˇp L pkq pf q ´Lpf q ˇˇthat have been investigated in [START_REF] Minsker | Uniform bounds for robust mean estimators[END_REF]. Proving fast rates is a more technically challenging task: to achieve the goal, we study remainder terms in Bahadur-type representations of the estimators p L pkq pf q and p L pkq U pf q that provide linear (in pf q) approximations of these nonlinear statistics and are easier to study.

Let us remark that exact evaluation of the U-statistics based estimators p L pkq U pf q and p 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.6) in scenarios like least-squares and logistic regression. Moreover, numerical performance of the permutation-invariant estimator p f U N is never worse than p f N , and often is significantly better; these points are further discussed in Section 2.

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 p f N and p f U N . First, we show that rates of order N ´1{2 are achieved with exponentially high probability if σp , Fq " sup f PF σ 2 p , f q ă 8 and E sup f PF 1 ? N ř N j"1 p pf pX j qq ´E pf pXqqq ă 8. The latter is true if the class t pf q, f P Fu is P-Donsker [START_REF] Dudley | Uniform central limit theorems 142[END_REF], in other words, if the empirical process f Þ Ñ

p f N q ď s δ `CpF, P q ˜s N 3{4 `ˆO N ˙3{4 ¸,
again with probability at least 1 ´e´s for all s À k simultaneously.

Here, s δ is the quantity (formally defined in (3.5) below) that often coincides with the optimal rate for the excess risk [START_REF] Alquier | Estimation bounds and sharp oracle inequalities of regularized procedures with Lipschitz loss functions[END_REF][START_REF] Lugosi | Risk minimization by median-of-means tournaments[END_REF]. Moreover, we design a two-step estimator based on p f N that is capable of achieving faster rates whenever s δ ! N ´3{4 .

Theorem 1.2 (Informal). Assume that sup f PF E 1{4 p pf pXqq ´E pf pXqqq 4 ă 8. There exists an esti-

mator p f 2 N such that E ´p f 2 N ¯ď s δ `CpF, P, ρq ˆO N `s N ẇith
probability at least 1 ´e´s for all 1 ď s ď s max where s max Ñ 8 as N Ñ 8.

Estimator p f 2 N is based on a two-step procedure, where p f N serves as an initial approximation that is refined on the second step via the risk minimization restricted to a "small neighborhood" of p f N . 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 for the optimization problem (1.1) based on variants of the multivariate median-of-means technique [START_REF] Prasad | Robust estimation via robust gradient estimation[END_REF][START_REF] Chen | Distributed statistical machine learning in adversarial settings: Byzantine gradient descent[END_REF][START_REF] Yin | Byzantine-robust distributed learning: Towards optimal statistical rates[END_REF][START_REF] Alistarh | Byzantine stochastic gradient descent[END_REF], as well as Catoni's estimator [START_REF] Holland | Efficient learning with robust gradient descent[END_REF]. While these algorithms admits strong theoretical guarantees, they require robustly estimating the gradient vector at every step hence are computationally demanding; moreover, results are weaker for losses that are not strongly convex (for instance, the hinge loss).

The line of work that is closest in spirit to the approach of this paper has includes the works that employ robust risk estimators based on Catoni's approach [START_REF] Audibert | Robust linear least squares regression[END_REF][START_REF] Brownlees | Empirical risk minimization for heavy-tailed losses[END_REF][START_REF] Holland | Robust regression using biased objectives[END_REF] and the median-of-means technique, such as "tournaments" and the "min-max median-of-means" [START_REF] Lugosi | Risk minimization by median-of-means tournaments[END_REF][START_REF] Lugosi | Regularization, sparse recovery, and median-of-means tournaments[END_REF][START_REF] Lecué | Robust machine learning by median-of-means: theory and practice[END_REF][START_REF] Lecué | Robust classification via MOM minimization[END_REF][START_REF] Chinot | Statistical learning with Lipschitz and convex loss functions[END_REF]. As it was mentioned in the introduction, the core of our methods can be viewed as a "hybrid" between Catoni's and the median-of-means estimators. We provide a more detailed comparison to the results of the aforementioned papers:

1. We show that risk minimization based on Catoni's estimator is capable of achieving fast rates, thus improving the results and weakening the assumptions stated in [START_REF] Brownlees | Empirical risk minimization for heavy-tailed losses[END_REF]; 2. Existing approaches based on the median-of-means estimators are either computationally intractable [START_REF] Lugosi | Risk minimization by median-of-means tournaments[END_REF], or outputs of practically efficient algorithms do not admit strong theoretical guarantees [START_REF] Lecué | Robust machine learning by median-of-means: theory and practice[END_REF][START_REF] Lecué | Robust classification via MOM minimization[END_REF][START_REF] Chinot | Statistical learning with Lipschitz and convex loss functions[END_REF]. Our algorithms are designed specifically for the estimators p f N and p f U N , and enjoy good performance in numerical experiments along with strong theoretical guarantees simultaneously. 3. We develop new tools and techniques to analyze proposed estimators. In particular, we do not rely on the "small ball" method [START_REF] Koltchinskii | Bounding the smallest singular value of a random matrix without concentration[END_REF][START_REF] Mendelson | Learning without concentration[END_REF] and the standard "majority vote-based" analysis 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 (1.2). In particular, we demonstrate that the typical deviations of the estimator p L pkq pf q around Lpf q are significantly smaller than the deviations of the subsample averages s L j pf q; consequently, this fact allows us to "decouple" the parameter k responsible for the cardinality of subsamples from the confidence parameter s that controls the deviation probabilities, and establish bounds that are uniform over a certain range of s instead of a fixed level sk. Moreover, in cases when adversarial contamination is insignificant (e.g. O " Op1q), our algorithms, unlike existing results, admit a "universal" choice of k that is independent of the parameter s δ controlling the optimal rate. We are able to 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), our required assumptions are slightly stronger compared to the best results in the literature tailored specifically to the task [e.g. 31, 27].

Numerical algorithms and examples.

The main goal of this section is to discuss numerical algorithms used to approximate estimators p f N and p f U N , as well as assess the quality of resulting solutions. We will also compare our methods with the ones known previously, specifically, the median-of-means based approach proposed in [START_REF] Lecué | Robust classification via MOM minimization[END_REF]. Finally, we perform the numerical study of dependence of the solutions on the parameters ∆ and k. All evaluations are performed for logistic regression in the framework of binary classification as well as linear regression with quadratic loss using simulated data, while applications to real data are shown in the appendix. Let us mention that the numerical methods for closely related approach in the special case of linear regression have been investigated in a recent work [START_REF] Holland | Robust regression using biased objectives[END_REF]. Here, we focus on general algorithms that can easily be adapted to other predictions tasks and loss functions. Let us first briefly recall the formulations of both the binary classification and the linear regression problems. Binary classification and logistic regression. Assume that pZ, Y q P S ˆt˘1u is a random couple where Z is an instance and Y is a binary label, and let g ˚pzq :" ErY |Z " zs be the regression function. It is well-known that the binary classifier b ˚pzq :" signpg ˚pzqq achieves smallest possible misclassification error defined as P pY ‰ gpZqq. Let F be a given convex class of functions mapping S to R, : R Þ Ñ R - a convex, nondecreasing, Lipschitz loss function, and let

ρ ˚" argmin all measurable f E pY f pZqq.
The loss is classification-calibrated if signpρ ˚pzqq " b ˚pzq P-almost surely; we refer the reader to [START_REF] Bartlett | Convexity, classification, and risk bounds[END_REF] for a detailed exposition. In the case of logistic regression considered below, S " R d , py, f pzqq " pyf pzqq :" log ´1 `e´yfpzq īs a classification-calibrated loss and F " f β p¨q " x¨, βy , β P R d ( (as usual, the intercept term can be included if the vector Z is replaced by Z " pZ, 1q).

Regression with quadratic loss. Let pZ, Y q P S ˆR be a random couple satisfying Y " f ˚pZ q `η where the noise variable η is independent of Z and f ˚pzq " ErY |Z " zs is the regression function. Linear regression with quadratic loss corresponds to S " R d , py, f pzqq " py ´f pzqq :" py ´f pzqq 2 and F " f β p¨q " x¨, βy , β P R d ( . In both examples, we will assume that we are given an i.i.d. sample pZ 1 , Y 1 q, . . . , pZ N , Y N q having the same distribution as pZ, Y q.

2.1. Gradient descent algorithms.

Optimization problems (1.5) and (1.6) are not convex, so we will focus our attention of the variants of the gradient descent method employed to find local minima. We will first derive the expression for ∇ β p L pkq pβq, the gradient of p L pkq pβq :" p L pkq pf β q, for the problems corresponding to logistic regression and regression with quadratic loss. It follows from (1.2) that p L pkq pβq satisfies the equation

k ÿ j"1 ρ 1 ˜?n s L j pβq ´p L pkq pβq ∆ ¸" 0. (2.1)
Taking the derivative in (2.1) with respect to β, we retrieve ∇ β p L pkq pβq:

∇ β p L pkq pβq " ř k j"1 ´1 n ř iPGj Z i 1 pY i , f β pZ i qq ¯ρ2 ´?n s Lj pβq´p L pkq pβq ∆ řk j"1 ρ 2 ´?n s Lj pβq´p L pkq pβq ∆ ¯, (2.2)
where 1 pY i , f β pZ i qq stands for the partial derivative B py,tq Bt with respect to the second argument t, so that

1 pY i , f β pZ i qq " ´Yi e ´Yi xβ,Z i y
1`e ´Yi xβ,Z i y in the case of logistic regression and 1 pY i , f β pZ i qq " 2 pxβ, Z i y ´Yi q for regression with quadratic loss. In most of our numerical experiments, we choose ρ to be Huber's loss, ρpyq " y 2 2 I t|y| ď 1u `ˆ|y| ´1 2 ˙I t|y| ą 1u .

In this case, ρ 2 pyq " It|y| ď 1u for all y P R, hence the expression for the gradient can be simplified to

∇ β p L pkq pβq " ř k j"1 ´1 n ř iPGj Z i 1 pY i , f β pZ i qq ¯I !ˇˇˇs L j pβq ´p L pkq pβq ˇˇď ∆ ? n ) # ! j : ˇˇs L j pβq ´p L pkq pβq ˇˇď ∆ ? n ) , (2.3)
where we implicitly assume that ∆ is chosen large enough so that the denominator is not equal to 0. To evaluate p L pkq pβq, we use the "modified weights" algorithm due to Huber and Ronchetti [23, Similarly to the way that we derived the expression for ∇ β p L pkq pβq from (1.2), it follows from (2.4), with ρ again being the Huber's loss, that

ÿ JPA pnq N ρ 1 ˜?n s Lpf β ; Jq ´p L pkq U pβq ∆
¸" 0 and

∇ β p L pkq U pβq " ř JPA pnq N `1 n ř iPJ Z i 1 pY i , f β pZ i qq ˘I !ˇˇˇs Lpβ; Jq ´p L pkq pβq ˇˇď ∆ ? n ) # ! J P A pnq N : ˇˇs Lpβ; Jq ´p L pkq pβq ˇˇď ∆ ? n ) . (2.5)
Expressions in (2.5) are closely related to U-statistics, and it will be convenient to write them in a slightly different form. To this end, let π N be the collection of all permutations i : t1, . . . , N u Þ Ñ t1, . . . , N u. Given τ " pi 1 , . . . , i N q P π N and an arbitrary U-statistic U N,n defined in (1.3), let

T i1,...,i N :" 1 k `h pX i1 , . . . , X in q `h `Xin`1 , . . . , X i2n ˘`. . . `h `Xi pk´1qn`1 , . . . , X i kn ˘˘.
Equivalently, for τ " pi 1 , . . . , i N q P π N , let G j pτ q " `ipj´1qn`1 , . . . , i jn ˘, j " 1, . . . , k " tN {nu,

which gives a compact form

T τ " 1 k k ÿ j"1 h pX i , i P G j pτ qq .
It is well known (section 5 in [START_REF] Hoeffding | Probability inequalities for sums of bounded random variables[END_REF]) that the following representation of the U-statistic holds:

U N,n " 1 N ! ÿ τ Pπ N T τ . ( 2
ř k j"1 ´1 n ř iPGj pτ q Z i 1 pY i , f β pZ i qq ¯I !ˇˇˇs Lpβ; G j pτ qq ´p L pkq pβq ˇˇď ∆ ? n ) ř k j"1 I !ˇˇˇs Lpβ; G j pτ qq ´p L pkq pβq ˇˇď ∆ ? n ) (2.9)
is similar to the expression for the gradient of p L pkq pβq defined for a fixed partition G 1 pτ q, . . . , G k pτ q, see equation (2.3). Representations in (2.8) and (2.9) can be simplified even further noting that permutations that do not alter the subgroups G 1 , . . . , G k also do not change the values of R τ pβ, zq, ω τ and r Γ τ pβq. To this end, let us say that τ 1 , τ 2 P π N are equivalent if G j pτ 1 q " G j pτ 2 q for all j " 1, . . . , k. It is easy to see that there are N ! pn!q k ¨pN ´nkq! equivalence classes, and let π N,n,k be the set of permutations containing exactly one permutation from each equivalence class. We can thus write

p L pkq U pβq " argmin zPR Qpβ, zq :" argmin zPR ÿ τ Pπ N,n,k R τ pβ, zq, ∇ β p L pkq U pβq " ÿ τ Pπ N,n,k r ω τ ¨r Γ τ pβq, (2.10)
where r ω τ " pn!q k pN ´nkq! ¨ωτ . Representation (2.10) suggests that in order to obtain an unbiased estimator of ∇ z Qpβ, zq, one can sample a permutation τ P π N,n,k uniformly at random, compute ∇ z R τ pβ, zq and use it as a descent direction. This yields a version of the stochastic gradient descent for evaluating p L pkq U pβq presented in Figure 2 leads to an algorithm for finding p f U N . Indeed, using representation (2.10), it is easy to see that an unbiased estimator of ∇ β p L pkq U pβq can be obtained by first sampling a permutation τ P π N,n,k according to the probability distribution given by the weights tr ω τ , τ P π N,n,k u, then evaluating r Γ τ pβq using formula (2.9), and using r Γ τ pβq as a direction of descent. In most typical cases, the number M of the gradient descent iterations is much smaller than N ! pn!q k ¨pN ´nkq! , whence it is unlikely that the same permutation will be repeated twice in the sampling process. This reasoning suggests the idea of replacing the weights r ω τ by the uniform distribution over π N,n,k that leads to a much faster practical implementation which is detailed in Figure 3. It is easy to see that presented gradient descent algorithms for evaluating p f N and p f U N have Input: the dataset pZ i , Y i q 1ďiďN , number of blocks k P N, step size parameter η ą 0, maximum number of iterations M , initial guess β 0 P R d , tuning parameter ∆ P R. for all t " 0, . . . , M do Sample permutation τ uniformly at random from π N,n,k , construct blocks G 1 pτ q, . . . , G k pτ q according to (2.6);

Compute p L pkq U pβtq using Algorithm 2 in Figure 2; Compute r Γτ pβtq via equation 2.9; Update β t`1 " βt ´ηr Γτ pβtq.

end for Output: β M `1.

the same numerical complexity. The following subsections provide several "proof-of-concept" examples illustrating the performance of proposed methods, as well as comparison to the existing techniques.

Logistic regression.

The dataset consists of pairs pZ j , Y j q P R 2 ˆt˘1u, where the marginal distribution of the labels is uniform and conditional distributions of Z are normal, namely, Law pZ | Y " 1q " N `p´1, ´1q T , 1.4I 2 ˘, Law pZ | Y " ´1q " N pp1, 1q, 1.4I 2 q, and PrpY " 1q " PrpY " ´1q " 1{2. The dataset includes outliers for which Y " 1 and Z " N pp24, 8q, 0.1I 2 q, where I 2 stands for the 2 ˆ2 identity matrix. We generated 600 "informative" observations along with 30 outliers, and compared performance or our robust method (based on evaluating p β U N ) with the standard logistic regression that is known to be sensitive to outliers in the sample (we used implementation available in the Scikit-learn package [START_REF] Pedregosa | Scikit-learn: Machine learning in Python[END_REF]). Results of the experiment are presented in Figure 4. Parameters k and ∆ in our implementation were tuned via cross-validation. the color of the points correspond to their labels and the background color -to the predicted labels (brown region corresponds to "yellow" labels and blue -to "purple").

Linear regression.

In this section, we compare performance of our method (again based on evaluating p β U N ) with standard linear regression as well as with robust Huber's regression estimator [23, section 7]; linear regression and Huber's regression were implemented using 'LinearRregression' and 'HuberRegressor' functions in the Scikit-learn package [START_REF] Pedregosa | Scikit-learn: Machine learning in Python[END_REF]. As in the previous example, the dataset consists of informative observations and outliers. Informative data pZ j , Y j q, j " 1, . . . , 570 are i.i.d. and satisfy the linear model Y j " 10Z j `εj where Z j " Unifr´3, 3s and ε j " N p0, 1q. We consider two types of outliers: (a) outliers in the response variable Y only, and (b) outliers in the predictor Z. It is well-known that standard linear regression is not robust in any of these scenarios, Huber's regression estimator is robust to outliers in response Y only, while our approach is shown to be robust to corruption of both types. In both test scenarios, we generated 30 outliers. Given Z j , the outliers Y j of type (a) are sampled from a N p100, 0.01q distribution, while the outliers of type (b) are Z j " N `p24, 24q T , 0.01 I 2 ˘. Results are presented in Figure 5, and confirm the expected outcomes.

Choice of k and ∆.

In this subsection, we evaluate the effect of different choices of k and ∆ in the linear regression setting of Section 2.3, again with 570 informative observations and 30 outliers of type (b) as described in section 2.3 above. Figure 6a shows the plot of the resulting mean square error (MSE) against the number of subgroups k. As expected, the error decreases significantly when k exceeds 60, twice the number of outliers. At the same time, the MSE remains stable as k grows up to k » 100, which is a desirable property for practical applications. In this experiment, ∆ was set using the "median absolute deviation" (MAD) estimator defined as follows. We start with ∆ 0 being a small number (e.g., ∆ 0 " 0.1q. Given a current approximate solution β t , a permutation τ and the corresponding subgroups G 1 pτ q, . . . , G k pτ q, set x M pβ t q :" median ´p L pkq pβ t ; G 1 pτ q, . . . , p L pkq pβ t ; G k pτ q ¯, and Finally, define p ∆ t`1 :" MADpβtq Φ ´1p3{4q , where Φ is the distribution function of the standard normal law. After a small number m (e.g. m " 10) of "burn-in" iterations of Algorithm 3, ∆ is fixed at the level p ∆ m for all the remaining iterations.

MADpβ t q " median ´ˇˇp L pkq pβ t ; G 1 pτ q ´x M pβ t q ˇˇ, . . . , ˇˇp L pkq pβ t ; G k pτ q ´x M pβ t q ˇˇ¯.
Next, we study the effect of varying ∆ for different but fixed values of k. To this end, we set k P t61, 91, 151u, and evaluated the MSE as a function of ∆. Resulting plot is presented in Figure 6b. The MSE achieves its minimum for ∆ -10 2 ; for larger values of ∆, the effect of outliers becomes significant as the algorithm starts to resemble regression with quadratic loss (indeed, outliers in this specific example are at a distance « 100 from the bulk of the data).

Comparison with existing methods.

In this section, we compare performance of Algorithm 3 with a median-of-means-based robust gradient descent algorithm studied in [START_REF] Lecué | Robust classification via MOM minimization[END_REF]. The main difference of this method is in the way the descent direction is computed at every step. Specifically, r Γ τ pβq employed in Algorithm 3 is replaced by ∇ β L ˛pβq where L ˛pβq :" median `s Lpβ; G 1 pτ q, . . . , s Lpβ; G k pτ q ˘, see Figure 7 and [START_REF] Lecué | Robust classification via MOM minimization[END_REF] for the detailed description. Experiments were performed for the logistic regression problem based on the "two moons" pattern, one of the standard datasets in the Scikit-learn package [START_REF] Pedregosa | Scikit-learn: Machine learning in Python[END_REF] presented in Figure 8a. We performed two sets of experiments, one on the outlier-free dataset and one on the dataset consisting of 90% of informative observations and 10% of outliers, depicted as a yellow dot with coordinates p0, 5q on the plot. In both Input: the dataset pZ i , Y i q 1ďiďN , number of blocks k P N, step size parameter η ą 0, maximum number of iterations M , initial guess β 0 P R d . for all t " 0, . . . , M do Sample permutation τ uniformly at random from π N,n,k , construct blocks G 1 pτ q, . . . , G k pτ q according to (2.6);

Compute ∇ β L ˛pβq; Update β t`1 " βt ´η∇ β L ˛pβq.
end for Output: β M `1.

scenarios, we tested the "small" (N " 100) and "moderate" (N " 1000) sample size regimes. We used standard logistic regression trained on an outlier-free sample as a benchmark; its accuracy is shown as a dotted red line on the plots. In all the cases, parameter ∆ was tuned via cross-validation. In the outlierfree setting, our method (based on Algorithm 3) performed nearly as good as logistic regression; notably, performance of the method was strong even for large values of k, while classification accuracy decreased noticeably for Algorithm 4 for large k. In the presence of outliers, our method performed similar to Algorithm 4, while both methods outperformed standard logistic regression; for large values of k, our method was again slightly better. At the same time, Algorithm 4 was consistently faster than Algorithm 3 across the experiments. 3. Theoretical guarantees for the excess risk.

Preliminaries.

In this section, we introduce the main quantities that appear in our results, and state the key assumptions. σ 2 p , F 1 q " sup f PF 1 σ 2 p , f q. 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, continuously differentiable 5 times and such that (i) ρ 1 pzq " z for |z| ď 1 and ρ 1 pzq " const for z ě 2.

(ii) z ´ρ1 pzq is nondecreasing;

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

Hpyq " y 2 2 It|y| ď 3{2u `3 2 ˆ|y| ´3 4 ˙It|y| ą 3{2u
be the usual Huber's loss. Moreover, let φ be the "bump function" φpxq " C exp ´´4

1´4x 2 ¯ |x| ď 1 2 (
where C is chosen so that ş R φpxqdx " 1. Then ρ given by the convolution ρpxq " ph ˚φqpxq satisfies assumption 1.

Remark 3.1. The derivative ρ 1 has a natural interpretation of being a smooth version of the truncation function. Moreover, observe that ρ 1 p2q ´2 ď ρ 1 p1q ´1 " 0 by (ii), hence }ρ 1 } 8 ď 2. It is also easy to see that for any x ą y, ρ 1 pxq ´ρ1 pyq " y ´ρ1 pyq ´px ´ρ1 pxqq `x ´y ď x ´y, hence ρ 1 is Lipschitz continuous with Lipschitz constant Lpρ 1 q " 1.

Everywhere below, Φp¨q stands for the cumulative distribution function of the standard normal random variable and W pf q denotes a random variable with distribution N `0, σ 2 pf q ˘. For f P F such that σpf q ą 0, n P N and t ą 0, define

R f pt, nq :" ˇˇˇˇP r ˜řn j"1 pf pX j q ´P f q σpf q ? n ď t ¸´Φptq ˇˇˇˇ,
where P f :" Ef pXq. In other words, g f pt, nq 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 14] that

R f pt, nq ď g f pt, nq :" C ˜Epf pXq ´Ef pXqq 2 I ! |f pXq´Ef pXq| σpf q ? n ą 1 `ˇˇt σpf q ˇˇ) σ 2 pf q ´1 `ˇˇt σpf q ˇˇ¯2 `1 ? n E|f pXq ´Ef pXq| 3 I ! |f pXq´Ef pXq| σpf q ? n ď 1 `ˇˇt σpf q ˇˇ) σ 3 pf q ´1 `ˇˇt σpf q ˇˇ¯3
ģiven that the absolute constant C is large enough. Moreover, let G f pn, ∆q :"

ż 8 0 g f ˆ∆ ˆ1 2 `t˙, n ˙dt.
This quantity (more specifically, its scaled version

G f pn,∆q ? n
plays the key role in controlling the bias of the estimator p L pkq pf q. The following statement provides simple upper bounds for g f pt, nq and G f pn, ∆q.

Lemma 3.1. Let X 1 , . . . , X n be i.i.d. copies of X, and assume that Varpf pXqq ă 8. Then g f pt, nq Ñ 0 as |t| Ñ 8 and g f pt, nq Ñ 0 as n Ñ 8, with convergence being monotone. Moreover, if E|f pXq Éf pXq| 2`δ ă 8 for some δ P r0, 1s, then for all t ą 0

g f pt, nq ď C 1 E ˇˇf pXq ´Ef pXq ˇˇ2`δ n δ{2 pσpf q `|t|q 2`δ ď C 1 E ˇˇf pXq ´Ef pXq ˇˇ2`δ n δ{2 |t| 2`δ , (3.1)
G f pn, ∆q ď C 2 E ˇˇf pXq ´Ef pXq ˇˇ2`δ ∆ 2`δ n δ{2 ,
where C 1 , C 2 ą 0 are absolute constants.

3.2. Slow rates for the excess risk.

Let p δ N :" Ep p f N q " L `p f N ˘´Lpf ˚q, p δ U N :" Ep p f U N q " L `p f U N ˘´Lpf
˚q be the excess risk of p f N and its permutation-invariant analogue p f U N which are the main objects of our interest. The following bound for the excess risk is well known:

E `p f N ˘" L `p f N ˘´Lpf ˚q " L `p f N ˘`p L pkq p p f N q ´p L pkq p p f N q `p L pkq pf ˚q ´p L pkq pf ˚q ´Lpf ˚q " ´L`p f N ˘´p L pkq p p f N q ¯´´L pf ˚q ´p L pkq pf ˚q¯`p L pkq p p f N q ´p L pkq pf ˚q looooooooooomooooooooooon ď0 ď 2 sup f PF ˇˇp L pkq pf q ´Lpf q ˇˇ. (3.2)
The first result, Theorem 3.1 below, together with the inequality (3.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 [START_REF] Minsker | Uniform bounds for robust mean estimators[END_REF]. Define r ∆ :" max p∆, σp , Fqq . Theorem 3.1. There exist absolute constants c, C ą 0 such that for all s ą 0, n and k satisfying

1 ∆ ˜1 ? k E sup f PF 1 ? N N ÿ j"1 p pf pX j qq ´P pf qq `σp , Fq c s k ¸`sup f PF G f pn, ∆q `s k `O k ď c, (3.3)
the following inequality holds with probability at least 1 ´2e ´s:

sup f PF ˇˇp L pkq pf q ´Lpf q ˇˇď C « r ∆ ∆ ˜E sup f PF 1 N N ÿ j"1 p pf pX j qq ´P pf qq `σp , Fq c s N ŗ ∆ ˆ?n s N `sup f PF G f pn, ∆q ? n `O k ? n ˙ff.
Moreover, same bounds hold for the permutation-invariant estimators p L pkq U pf q, up to the change in absolute constants.

An immediate corollary is the bound for the excess risk

Ep p f N q ď C « r ∆ ∆ ˜E sup f PF 1 N N ÿ j"1 p pf pX j qq ´P pf qq `σp , Fq c s N ŗ ∆ ? n ˆs N `sup f PF G f pn, ∆q n `O N ˙ff (3.4)
that holds under the assumptions of Theorem 3.1 with probability at least 1 ´2e ´s. When the class t pf q, f P Fu is P-Donsker [START_REF] Dudley | Uniform central limit theorems 142[END_REF], lim sup

N Ñ8 ˇˇE sup f PF 1 ? N
ř N j"1 p pf pX j qq ´P pf qq ˇˇis bounded, hence condition (3.3) holds for N large enough whenever s is not too big and ∆ and k are not too small, namely, s ď c 1 k and ∆ ? k ě c 2 σpFq. The bound of Theorem 3.1 also suggests that the natural "unit" to measure the magnitude of parameter ∆ is σp , Fq. We will often use the ratio M ∆ :" ∆ σp ,F q that can be interpreted as a level of truncation expressed in the units of σp , Fq, and is one of the two main quantities controlling the bias of the estimator p L pkq pf q, the second one being the subgroup size n.

To put these results in perspective, let us consider two examples. First, assume that n " 1, k " N and set ∆ " ∆psq :" σpFq b N s for s ď c 1 N . Using Lemma 3.1 with δ " 0 to estimate G f pn, ∆q, we deduce that

Ep p f N q ď C « E sup f PF 1 N N ÿ j"1
p pf pX j qq ´P pf qq `σp , Fq ˆc s N `O ? N ˙ff with probability at least 1 ´2e ´s. This inequality improves upon excess risk bounds obtained for Catonitype estimators in [START_REF] Brownlees | Empirical risk minimization for heavy-tailed losses[END_REF], 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 ∆ -σp , Fq, the estimator p L pkq pf q most closely resembles the median-of-means estimator. In this case, Theorem 3.1 yields the excess risk bound of the form

Ep p f N q ď C « E sup f PF 1 N N ÿ j"1 p pf pX j qq ´P pf qq `σp , Fq ˜c s N `c k N sup f PF G f pn, σpFqq `O k c k N
¸ff that holds with probability ě 1 ´2e ´s for all s ď c 1 k. As sup f PF G f pn, ∆q is small for large n and [START_REF] Lecué | Robust classification via MOM minimization[END_REF] that provides bounds for the excess risk for robust classifiers based on the the median-of-means estimators.

O k b k N ď b O N whenever O ď k, this bound is improves upon Theorem 2 in

Towards fast rates for the excess risk.

It is well known that in regression and binary classification problems, 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 φp0q " 0, Epf q " P pf q ´P pf ˚q ě φ ´aVar p pf pXqq ´ pf ˚pX qqq ¯.

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 appear in the excess risk bounds. For δ ą 0, let Fpδq :" t pf q : f P F, Epf q ď δu , νpδq :" sup ´p pf q ´ pf ˚qqpX j q ´P p pf q ´ pf ˚qq ¯ˇˇˇˇ.

Moreover, define

Bp , Fq :" sup f PF E 1{4 p pf pXqq ´E pf pXqqq 4 σp , Fq .

The following condition, known as Bernstein's condition following [START_REF] Bartlett | Empirical minimization[END_REF], plays the crucial role in the analysis of excess risk bounds.

Assumption 2. There exist constants D ą 0, δ B ą 0 such that Var p pf pXqq ´ pf ˚pX qqq ď D 2 Epf q whenever Epf q ď δ B .

Assumption 2 is known to hold in many concrete cases of prediction and classification tasks, and we provide examples and references in Section 4 below. Informally speaking, it postulates that any f with small excess risk must be "close" to f ˚. More general versions of the Bernstein's condition are often considered in the literature: for instance, it can be replaced by assumption [START_REF] Bartlett | Empirical minimization[END_REF] requiring that Var p pf pXqq ´ pf ˚pX qqq ď D2 pEpf qq τ for some τ P p0, 1s (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 [24, Chapter 4], we will say the the function ψ : R `Þ Ñ R `is of concave type if it is nondecreasing and x Þ Ñ ψpxq x is decreasing. Moreover, if for some γ P p0, 1q x Þ Ñ ψpxq x γ is decreasing, we will say that ψ is of strictly concave type with exponent γ. We will assume that ωpδq admits an upper bound r ωpδq of strictly concave type (with some exponent γ), and that νpδq admits an upper bound r νpδq of concave type. For instance, when assumption 2 holds, νpδq ď D ? δ for δ ď δ B , implying that r νpδq " D ? δ is an upper bound for νpδq of strictly concave type with γ " 1 2 . 2 Moreover, the function ωpδq often admits an upper bound of the form r ωpδq " R 1 `?δR 2 where R 1 and R 2 do not depend on δ; such an upper bound is also of concave type. Next, set

s δ :" min # δ ą 0 : C 1 pρq 1 ? N r ∆ ∆ r ωpδq δ ď 1 7 + , (3.5)
where C 1 pρq is a sufficiently large positive constant that depends only on ρ. This quantity plays an important role in controlling the excess risk, as shown by the following theorems.

Theorem 3.2. Assume that conditions of Theorem 3.1 hold. Additionally, suppose that M ∆ :" ∆ σp ,F q ě 1. Then

p δ N ď s δ `Cpρq ˆD2 ˆ1 M 2 ∆ n `s `O N ˙`σp , Fq ? nM ∆ ˆ1 M 4 ∆ n `s `O N ˙˙.
with probability at least 1 ´10e ´s, where the constant Cpρq depends on ρ only and D is a constant appearing in Assumption 2. Moreover, same bound holds for p δ U N , up to a change in absolute constants. Under stronger moment assumptions, the excess risk bound can be strengthened and take the following form. and that M ∆ :" ∆ σp ,F q ě 1. Then

p δ N ď s δ `Cpρq `D2 `σp , Fq ? nM ∆ ˘ˆB 6 p , Fq M 4 ∆ n 2 `s `O N ˙.
with probability at least 1 ´10e ´s, where the constant Cpρq depends on ρ only and D is a constant appearing in Assumption 2. Moreover, same bound holds for p δ U N , up to a change in absolute constants. Remark 3.2. 1. It is evident that whenever O " 0, the best possible rates implied by Theorem 3.2 are of order N ´2{3 (indeed, this is the case whenever M ∆ ? n -N 1{3 and s δ À N ´2{3 ), while the best possible rates attained by Theorem 3.3 are of order N ´3{4 (when M ∆ ? n -N 1{4 and s δ À N ´3{4 ); in particular, in this case the choice of M ∆ and n is independent of s δ. In general, if O " εN for ε ą 0, the best rates implied by Theorems 3.2 and 3.3 are s δ `CpF, ρ, P qε ´2{3 and s δ `CpF, ρ, P qε ´3{4 respectively. 2. Assumption requiring that M ∆ ě 1 is introduced for convenience: without it, extra powers of the ratio maxp∆,σp ,F qq ∆ 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, 30, 27, among others], as well as the "median-of-means tournaments" introduced in [START_REF] Lugosi | Risk minimization by median-of-means tournaments[END_REF]; all these methods focus on estimating the differences Lpf 1 q ´Lpf 2 q for all f 1 , f 2 P F. Recall that f ˚" argmin f PF P pf q, and observe that for any fixed f 1 P F, f ˚can be equivalently defined via

f ˚" argmin f PF P ` pf q ´ pf 1 q ˘.
A version of the robust empirical risk minimizer (1.5) corresponding to this problem can be defined as p L pkq pf ´f 1 q :" argmin

yPR 1 ? N k ÿ j"1 ρ ˜?n `s L j pf q ´s L j pf 1 q ˘´y ∆ ¸(3.6)
for appropriately chose ∆ ą 0, and

p f 1 N :" argmin f PF p L pkq pf ´f 1 q.
Moreover, if f 1 P F is a priori known to be "close" to f ˚, then it suffices to search for the minimizer in a neighborhood F 1 of f 1 that contains f ˚instead of all f P F:

p f 2 N :" argmin f PF 1 p L pkq pf ´f 1 q.
The advantage gained by this procedure is expressed by the fact that sup f PF 1 Var p pf pXqq ´ pf 1 pXqqq can be much smaller than σp , Fq.

We will now formalize this argument and provide performance guarantees; we use the framework of Theorem 3.3 which leads to the bounds that are easier to state and interpret. However, similar reasoning applies to the setting of Theorem 3.2 as well. Presented algorithms also admit straightforward permutation-invariant modifications that we omit. Let p E N pf q :" p L pkq pf q ´p L pkq p p f N q be the "empirical excess risk" of f . Indeed, this is a meaningful notion as p f N is the minimizer of p L pkq pf q over f P F. Assume that the initial sample of size N is split into two disjoint parts S 1 and S 2 of cardinalities that differ at most by 1: pX 1 , Y 1 q, . . . , pX N , Y N q " S 1 Y S 2 . The algorithm proceeds in the following way:

1. Let p f |S1| be the estimator (1.5) evaluated over subsample S 1 of cardinality |S 1 | ě tN {2u, with the scale parameter ∆ 1 and the partition parameter k 1 corresponding the group size n 1 " t|S 1 |{k 1 u;

2. Let δ 1 " s δ `Cpρq `D2 `σp , Fq ? nM ∆1 ˘ˆB 6 p ,F q M 4 ∆ 1 n 2 1
`s`O N ˙be a known upper bound on the excess risk in Theorem 3.3 (while this condition is restrictive, it is similar to the requirements of existing approaches [START_REF] Brownlees | Empirical risk minimization for heavy-tailed losses[END_REF][START_REF] Lugosi | Risk minimization by median-of-means tournaments[END_REF]; discussion of adaptation issues is beyond the scope of this paper and will be addressed elsewhere). Set

p Fpδ 1 q :" ! f P F : p E N pf q ď δ 1
) .

3. Define p f 2 N :" argmin f P p

F pδ 1 q p L pkq pf ´p f |S1| q where p L pkq ´f ´p f |S1| ¯" argmin yPR k2 ÿ j"1 ρ ¨?n ´s L j pf q ´s L j p p f |S1| q ¯´y ∆ 2 ' (3.7)
is based on the subsample S 2 of cardinality |S 2 | ě tN {2u, a scale parameter ∆ 2 and the partition parameter k 2 corresponding the group size n 2 " t|S 2 |{k 2 u.

It will be demonstrated in the course of the proofs that on event of high probability, p Fpδ 1 q Ď Fpcδ 1 q for an absolute constant c ď 7. Hence, on this event sup f P p F pδ 1 q Var p pf pXqq ´ pf ˚pX qqq ď ν 2 pcδ 1 q ď cD 2 δ 1 by the definition of νpδq and Assumption 2, thus ∆ 2 " D M ∆2 ? cδ 1 with M ∆2 ě 1 often leads to an estimator with improved performance. and that ∆ 1 , ∆ 2 satisfy M ∆1 :" ∆1 σp ,F q ě 1 and M ∆2 :" ∆2 D ?

7δ 1 ě 1. Moreover, assume that for a sufficiently small absolute constant c 1 ą 0, sup f PF max pG f pn 1 , ∆ 1 q, G f pn 2 , ∆ 2 qq ď c 1 and

s`O minpk1,k2q ď c 1 .
Finally, we require that

a k 1 M ∆1 ě c 1 σp , Fq E sup f PF 1 a |S 1 | |S1| ÿ j"1
p pf pX j qq ´P pf qq and (3.8)

a k 2 M ∆2 ě c 1 ? N δ 1 D .
Then

E ´p f 2 N ¯ď s δ `Cpρq ´D2 `D? δ 1 ? nM ∆2 ¯ˆB 6 p , Fq M 4 ∆2 n 2
`s `O N ẇith probability at least 1 ´20e ´s, where Cpρq depends on ρ only and D is the constant appearing in Assumption 2.

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

σp , Fq ? nM ∆ ˆB6 p , Fq M 4 ∆ n 2 `s `O N is
replaced by a potentially much smaller quantity ?

δ 1 ? nM ∆ ´B6 p ,F q M 4 ∆ n 2 `s`O N ¯. In particular, if δ 1 ! `nM 2 ∆
˘´1 , this term often becomes negligible. To be more specific, assume that δ " CpF q ? N ¨hpN q where hpN q Ñ 0 as N Ñ 8 (meaning that fast rates are achievable) and that O " ε N for ε ě 1 N . Moreover, suppose that Bp , Fq is bounded above by a constant. If ∆ 1 is chosen such that ∆ 1 -σp , Fq, then

δ 1 " C ´s δ `σp , Fq ´`k N ˘3{2 `s`O ? kN ¯¯. Hence, if max `hpN q ? N , N ε 2{3 ˘! k j ď CN ? ε for j " 1, 2 and ∆ 2 - ? δ 1 , then δ 1 ¨nM 2 ∆2 " Op1q,
and the excess risk of p f 2 N admits the bound

E ´p f 2 N ¯ď s δ `Cpρ, Dq ´ε `s N 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 (3.8) 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.

We consider two common prediction problems, regression and binary classification, and discuss the implications of our main results for these problems.

Binary classification with convex surrogate loss.

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

Logistic loss pyf pzqq " log `1 `e´yfpzq ˘. Consider two scenarios:

1. Uniformly bounded classes, meaning that for all f P F, sup zPS |f pzq| ď B. In this case, Assumption 2 holds with D " 2e B for all f P F. See [START_REF] Bartlett | Large margin classifiers: convex loss, low noise, and convergence rates[END_REF] and Proposition 6.1 in [START_REF] Alquier | Estimation bounds and sharp oracle inequalities of regularized procedures with Lipschitz loss functions[END_REF].

2. Linear separators and Gaussian design: in this case, we assume that S " R d , Z " N p0, Iq is Gaussian, and F " tx¨, vy : }v} 2 ď Ru 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 pyf pzqq " max p0, 1 ´yf pzqq. In this case, sufficient condition for Assumption 2 to hold is the following: there exists τ ą 0 such that |g ˚pZ q| ě τ almost surely. It follows from Proposition 1 in [START_REF] Lecué | Optimal rates of aggregation in classification under low noise assumption[END_REF] (see also [START_REF] Tsybakov | Optimal aggregation of classifiers in statistical learning[END_REF]) that Assumption 2 holds with D " 1 ? 2τ in this case. Bound for s δ. Let Π stand for the marginal distribution of Z and recall that ωpδq :" E sup pf qPF pδq ˇˇˇˇ1 ?

N N ÿ j"1
´p pY j f pZ j qq ´ pY j f ˚pZ j qqq ´Ep pY f pZqq ´ pY f ˚pZ qqq ¯ˇˇˇˇ.

Since is Lipchitz continuous by assumption (with Lipschitz constant denoted Lp q), consequent application of symmetrization and Talagrand's contraction inequalities [START_REF] Ledoux | Probability in Banach Spaces: isoperimetry and processes[END_REF][START_REF] Van De Geer | Estimation and testing under sparsity[END_REF] yields that

ωpδq ď 4Lp q E sup }f ´f˚}L 2 pΠq ďD ? δ ˇˇˇˇ1 ? N N ÿ j"1
ε j pf ´f˚q pZ j q ˇˇˇw here ε 1 , . . . , ε N are i.i.d. random signs independent from Y j 's and Z j 's. The latter quantity is the modulus 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 [START_REF] Koltchinskii | Oracle inequalities in empirical risk minimization and sparse recovery problems[END_REF],

E sup }f ´f˚}L 2 pΠq ďD ? δ ˇˇ1 ? N ř N j"1 ε j pf ´f˚q pZ j q ˇˇď D ? δ ? d, whence r ωpδq :" 4D Lp q ?
δd is an upper bound for ωpδq and is of concave type, implying that

s δ ď Cpρ, qD 2 d N .
More generally, assume that the class F has a measurable envelope F pzq :" sup f PF |f pzq| that satisfies }F pZq} ψ2 ă 8, where }ξ} ψ2 :" inf C ą 0 : E exp `|ξ{C| 2 ˘ď 2 ( is the ψ 2 (Orlicz) norm. Moreover, suppose that the covering numbers N pF, Q, εq of the class F with respect to the norm L 2 pQq satisfy the bound

N pF, Q, εq ď ˆA}F } L2pQq ε ˙V (4.1)
for some constants A ě 1, V ě 1, all 0 ă ε ď 2}F } L2pQq and all probability measures Q. For instance, VC-subgraph classes are known to satisfy this bound with V being the VC dimension of F [START_REF] Wellner | Weak convergence and empirical processes: with applications to statistics[END_REF][START_REF] Koltchinskii | Oracle inequalities in empirical risk minimization and sparse recovery problems[END_REF]. In this case, it is not difficult to show (see for example the proof of Lemma 4.1 in the appendix) that

E sup }f ´f˚}L 2 pΠq ďD ? δ ˇˇˇˇ1 ? N N ÿ j"1 ε j pf ´f˚q pZ j q ˇˇˇď r ωpδq :" C a V logpe 2 A 2 N q ˜?δ `c V N logpA 2 N q}F } ψ2 ¸,
hence it is easy to check that in this case

s δ ď Cpρq V log 3{2 pe 2 A 2 N q}F } ψ2 N .
It immediately follows from the discussion following Theorem 3.4 that the excess risk of the estimator

p f 2 N satisfies E ´p f 2 N ¯ď Cpρ, Dq ˜O N `V log 3{2 pe 2 A 2 N q}F } ψ2
`s N with probability at least 1 ´20e ´s. Similar results hold for regression problems with Lipschitz losses, such as Huber's loss or quantile loss [START_REF] Alquier | Estimation bounds and sharp oracle inequalities of regularized procedures with Lipschitz loss functions[END_REF].

Regression with quadratic loss.

Let X " pZ, Y q P S ˆR be a random couple with distribution P satisfying Y " f ˚pZ q `η where the noise variable η is independent of Z and f ˚pzq " ErY |Z " zs is the regression function. Let }η} 2,1 :" ş 8 0 a Prp|η| ą tqdt, and observe that }η} 2,1 ă 8 as sup f PF EpY ´f pZqq 4 ă 8 by assumption. As 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

f ˚" argmin f PF E pY ´f pZqq 2 .
In this case, the natural choice for the loss function is the quadratic loss pxq " x 2 which is not Lipschitz continuous on unbounded domains. Assume that the class F has a measurable envelope F pzq :" sup f PF |f pzq| that satisfies }F pZq} ψ2 ă 8. Moreover, suppose that the covering numbers3 N pF, Q, εq of the class F with respect to the norm L 2 pQq satisfy the bound

N pF, Q, εq ď ˆA}F } L2pQq ε ˙V (4.2) for some constants A ě 1, V ě 1, all 0 ă ε ď 2}F } L2pQq ,
δ ď Cpρq V log 2 pA 2 N qp}F } 2 ψ2 `}η} 2 2,1 q N .
The proof is given in the appendix. An immediate corollary of the lemma, according to the discussion following Theorem 3.4, is that the excess risk of the estimator p f 2 N satisfies the inequality

E ´p f 2 N ¯ď Cpρ, Dq ˜O N `V log 2 pA 2 N qp}F } 2 ψ2 `}η} 2
2,1 q `s N with probability at least 1 ´20e ´s, for 0 ă s ď cN 1{4 .

Proofs of the main results.

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

p G k pz; f q " 1 ? k k ÿ j"1 ρ 1 ˆ?n p s L j pf q ´Lpf qq ´z ∆ ˙, G k pz; f q " ? k Eρ 1 ˆ?n p s L j pf q ´Lpf qq ´z ∆ ˙.
In particular, when O " 0, G k pz; f q " E p G k pz; f q. Let p e pkq pf q and e pkq pf q be defined by the equations p G k ´p e pkq pf q; f ¯" 0, (5.1)

G k ´epkq pf q; f ¯" 0.
Comparing this to the definition of p L pkq pf q (1.2), it is easy to see that p e pkq pf q " p L pkq pf q ´Lpf q. Hence e pkq pf q, the "population version" of p e pkq pf q, is a natural measure of bias of the estimator p L pkq pf q.

5.1. Technical tools.

We summarize the key results that our proofs rely on.

Lemma 5.1. Let ρ satisfy Assumption 1. Then for any random variable Y with EY 2 ă 8,

Var `ρ1 pY q ˘ď Var pY q .

Proof. See Lemma 5.3 in [START_REF] Minsker | Uniform bounds for robust mean estimators[END_REF].

Lemma 5.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 E|ξ 1 | 3 ă 8,

ˇˇˇˇE h ˜n ÿ j"1 ξ j ¸´Eh ˜n ÿ j"1 Z j ¸ˇˇˇˇď Cn }h 3 } 8 E|ξ 1 | 3 ,
where C ą 0 is an absolute constant and Z 1 , . . . , Z n are i.i.d. centered normal random variables such that VarpZ 1 q " Varpξ 1 q.

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

Lemma 5.3. Assume that E|f pXq ´Ef pXq| 2 ă 8 for all f P F and that ρ satisfies Assumption 1. Then for all f P F and z P R satisfying |z| ď

∆ ? n 1 2 , ˇˇˇE ρ 1 ˆ?n p θj pf q ´P f q ´z ∆ ˙´Eρ 1 ˆW pf q ´?nz ∆ ˙ˇˇˇď 2 G f pn, ∆q.
Proof. See Lemma 4.2 in [START_REF] Minsker | Uniform bounds for robust mean estimators[END_REF].

Given N i.i.d. random variables X 1 , . . . , X N P S, let }f ´g} L8pΠ N q :" max 1ďjďN |f pX j q ´gpX j q|. Moreover, define Γ n,8 pFq :" Eγ 2 2 pF; L 8 pΠ N qq, where γ 2 pF, L 8 pΠ N qq is Talagrand's generic chaining complexity [START_REF] Talagrand | Upper and lower bounds for stochastic processes: modern methods and classical problems 60[END_REF].

Lemma 5.4. Let σ 2 :" sup f PG Ef 2 pXq. Then there exists a universal constant C ą 0 such that

E sup f PF ˇˇˇˇ1 N N ÿ j"1 f 2 pX j q ´Ef 2 pXq ˇˇˇˇď C ˜σc Γ N,8 pFq N ł Γ N,8 pFq N ¸.
Proof. See Theorem 3.16 in [START_REF] Koltchinskii | Oracle inequalities in empirical risk minimization and sparse recovery problems[END_REF].

The following form of Talagrand's concentration inequality is due to Klein and Rio (see section 12.5 in [START_REF] Boucheron | Concentration inequalities: A nonasymptotic theory of independence[END_REF]).

Lemma 5.5. Let tZ j pf q, f P Fu, j " 1, . . . , N be independent (not necessarily identically distributed) separable stochastic processes indexed by class F and such that |Z j pf q ´EZ j pf q| ď M a.s. for all 1 ď j ď N and f P F. Then the following inequality holds with probability at least 1 ´e´s :

sup f PF ˜N ÿ j"1 pZ j pf q ´EZ j pf qq ¸ď 2E sup f PF ˜N ÿ j"1 pZ j pf q ´EZ j pf qq ¸`V pFq ? 2s `4M s 3 , (5.2)
where V 2 pFq " sup f PF ř N j"1 Var pZ j pf qq. It is easy to see, applying (5.2) to processes t´Z j pf q, f P Fu, that inf

f PF ˜N ÿ j"1 pZ j pf q ´EZ j pf qq ¸ě ´2E sup f PF ˜N ÿ j"1 pEZ j pf q ´Zj pf

˜N ÿ

j"1 pZ j pf q ´EZ j pf qq ¸¸(5.4)

that holds for all λ ą 0. We use this fact to demonstrate a straightforward extension of Lemma 5.5 to the case of U-statistics. Let π N be the collection of all permutations π : t1, . . . , N u Þ Ñ t1, . . . , N u. Given pi 1 , . . . , i N q P π N and a U-statistic U N,n with kernel h defined in (1.3), let T i1,...,i N :" 1 k `h pX i1 , . . . , X in q `h `Xin`1 , . . . , X i2n ˘`. . . `h `Xi pk´1qn`1 , . . . , X i kn ˘˘.

It is well known (e.g., see section 5 in [START_REF] Hoeffding | Probability inequalities for sums of bounded random variables[END_REF]) that the following representation holds: We will provide detailed proofs for the estimator p f N that is based on disjoint groups G 1 , . . . , G k . The bounds for its permutation-invariant version p f U N follow exactly the same steps where all applications of the Talagrand's concentration inequality (Lemma 5.5) are replaced by its version for nondegenerate U-statistics (5.6).

U N,n " 1 N ! ÿ pi1,...,i N qPπ N T i1,...,i N . (5.5) Let U 1 N,n pz; f q " 1 p N n q ř JPA pnq N ρ 1 ´?n p s Lpf ;Jq´E pf pXqqq´z ∆ ¯. Applied to U 1 N,n pz; f q, relation (5.5) yields that U 1 N,n pz; f q " 1 N ! ÿ pi1,...,i N qPπ N T i1
Let J Ă t1, . . . , ku of cardinality |J| ě k ´O be the set containing all j such that the subsample tX i , i P G j u does not include outliers. Clearly, tX i : i P G j , j P Ju are still i.i.d. as the partitioning scheme is independent of the data. Moreover, set N J :" ř jPJ |G j |, and note that, since O ă k{2,

N J ě n|J| ě N 2 .
Consider stochastic process R N pf q defined as R N pf q " p G k p0; f q `Bz G k p0; f q ¨p e pkq pf q, (5.7)

where B z G k p0; f q :" B z G k pz; f q |z"0 . Whenever B z G k p0; f q ‰ 0 (this assumption will be justified by Lemma 5.6 below), we can solve (5.7) for p e pkq pf q to obtain p e pkq pf q " ´p G k p0;

f q B z G k p0; f q `RN pf q B z G k p0; f q , ( 5.8)
which can be viewed as a Bahadur-type representation of p e pkq pf q. Setting f :" p f N and recalling that p e pkq pf q " p L pkq pf q ´Lpf q, we deduce that

p L pkq p p f N q " Lp p f N q ´p G k ´0; p f N Bz G k ´0; p f N ¯`R N p p f N q B z G k ´0; p f N ¯.
By the definition (1.5) of p f N , p L pkq p p f N q ď p L pkq pf ˚q, hence

Lp p f N q ´p G k ´0; p f N Bz G k ´0; p f N ¯`R N p p f N q B z G k ´0; p f N ¯ď Lpf ˚q ´p G k p0; f ˚q B z G k p0; f ˚q `RN pf ˚q B z G k p0; f ˚q .
Rearranging the terms, it is easy to see that

p δ N " Lp p f N q ´Lpf ˚q ď ˇˇˇˇˇp G k ´0; p f N Bz G ´0; p f N ¯´p G k p0; f ˚q B z G p0; f ˚q ˇˇˇˇˇ`2 sup f PF p p δ N q ˇˇˇR N pf q B z G k p0; f q ˇˇˇ.
(5.9)

Remark 5.1. Similar argument also implies, in view of the inequality

Lpf ˚q ď Lp p f N q, that p L pkq pf ˚q `p G k p0; f ˚q B z G k p0; f ˚q ´RN pf ˚q B z G k p0; f ˚q ď p L pkq p p f N q `p G k ´0; p f N Bz G k ´0; p f N ¯´R N p p f N q B z G k ´0; p f N ¯, hence p L pkq pf ˚q ´p L pkq p p f N q ď ˇˇˇˇˇp G k ´0; p f N Bz G ´0; p f N ¯´p G k p0; f ˚q B z G p0; f ˚q ˇˇˇˇˇ`2 sup f PF p p δ N q ˇˇˇR N pf q B z G k p0; f q ˇˇˇ.
It follows from (5.9) that in order to estimate the excess risk of p f N , it suffices to obtain the upper bounds for

A 1 :" ˇˇˇˇˇp G k ´0; p f N Bz G k ´0; p f N ¯´p G k p0; f ˚q B z G k p0; f ˚q ˇˇˇˇˇ(

5.10)

and

A 2 :" sup f PF p p δ N q ˇˇˇR N pf q B z G k p0; f q ˇˇˇ. (5.11) Observe that p G k ´0; p f N Bz G k ´0; p f N ¯´p G k p0; f ˚q B z G k p0; f ˚q " p G k ´0; p f N ¯´p G k p0; f ˚q B z G k ´0; p f N ¯`p G k p0; f ˚q B z G k p0; f ˚q B z G k ´0; p f N ¯´B z G k p0; f ˚q ´Bz G k ´0; p f N ¯¯.
Since ρ 2 is Lipschitz continuous by assumption,

ˇˇˇˇˇp G k p0; f ˚q B z G k p0; f ˚q B z G k ´0; p f N ¯´B z G k p0; f ˚q ´Bz G k ´0; p f N ¯¯ˇˇˇˇˇ" ˇˇˇˇˇp G k p0; f ˚q B z G k p0; f ˚q B z G k ´0; p f N ¯?nk ∆ E ˜ρ2 ˆ?n s L 1 pf ˚q ´Lpf ˚q ∆ ˙´ρ 2 ˜?n s L 1 p p f N q ´Lp p f N q ∆ ¸¸ˇˇˇˇˇď Lpρ 2 q ˇˇˇˇˇp G k p0; f ˚q B z G k p0; f ˚q B z G k ´0; p f N ¯?nk ∆ 2 Var 1{2 ´ p p f N pXqq ´ pf ˚pX qq ¯ˇˇˇˇ" Cpρq ˇˇˇˇˇp G k p0; f ˚q B z G k p0; f ˚q B z G k ´0; p f N ¯ˇˇˇˇˇ? nk ∆ 2 νp p δ N q. (5.12)
We following two lemmas are required to proceed.

Lemma 5.6. There exist Cpρq ą 0 such that for any f P F,

|B z G k p0; f q| ě ? kn ∆ ˜min ˜∆ a Var p pf pXqqq , 2 a log 2 ¸´Cpρq ? n E ˇˇˇ pf pXqq ´P pf q ∆ ˇˇˇ3 ¸.
Proof. See section A.1.

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

f PF |B z G k p0; f q| ě 1 2 ? kn max p∆, σp , Fqq " 1 2
? kn r ∆ .

(5.13)

It is also easy to deduce from the proof of Lemma 5.6 that for small n and ∆ ą σp , Fq, inf f PF |B z G k p0; f q| ě cpρq ? kn ∆ for some positive cpρq. Lemma 5.7. For any f P F,

p G k p0; f q ď 2 ˆ?k G f pn, ∆q `σp , f q ∆ ? s `2s ? k `O ? k ẇith probability at least 1 ´2e ´s,
where C ą 0 is an absolute constant.

Proof. See section A.2.

Lemma 5.7 and (5.13) imply, together with (5.12), that

ˇˇˇˇˇp G k p0; f ˚q B z G k p0; f ˚q B z G k ´0; p f N ¯´B z G k p0; f ˚q ´Bz G k ´0; p f N ¯¯ˇˇˇˇˇď Cpρq r ∆ 2 ∆ 2 ˆσp , f ˚q ∆ c s N `Gf˚p n, ∆q ? n `?n s N `?n O N ˙νp p δ N q (5.14)
on event Θ 1 of probability at least 1 ´2e ´s. As r ∆ ě σp , Fq by assumption, we deduce that

ˇˇˇˇˇp G k p0; f ˚q B z G k p0; f ˚q B z G k ´0; p f N ¯´B z G k p0; f ˚q ´Bz G k ´0; p f N ¯¯ˇˇˇˇˇď Cpρqνp p δ N q ˆc s N `Gf˚p n, ∆q ? n `?n s N `?n O N ˙. Define s δ 1 :" min " δ ą 0 : C 1 pρq ˆc s N `Gf˚p n, ∆q ? n `?n s `O N ˙r νpδq δ ď 1 7
* (5.15)
where C 1 pρq is sufficiently large. It is easy to see that on event Θ 1 X t p

δ N ą s δ 1 u, ˇˇˇˇˇp G k p0; f ˚q B z G k p0; f ˚q B z G k ´0; p f N ¯´B z G k p0; f ˚q ´Bz G k ´0; p f N ¯¯ˇˇˇˇˇˇď p δ N 7 , (5.16)
for appropriately chosen C 1 pρq.

Our next goal is to obtain an upper bound for ˇˇˇp

G k p0; p f N q´p G k p0;f˚q BzG k p0; p f N q ˇˇˇ.
To this end, we will need to control the local oscillations of the process p G k p0; f q. Specifically, we are interested in the bounds on the random variable sup f PF pδq ˇˇp G k p0; f q ´p G k p0; f ˚qˇ. The following technical lemma is important for the analysis.

Lemma 5.8. Let pξ 1 , η 1 q, . . . , pξ n , η n q be a sequence of independent identically distributed random couples such that Eξ 1 " 0, Eη 1 " 0, and E|ξ 1 | 2 `E|η 1 | 2 ă 8. Let F be an odd, smooth function with bounded derivatives up to fourth order. Then

ˇˇˇˇE F ˜n ÿ j"1 ξ j ¸´EF ˜n ÿ j"1 η j ¸ˇˇˇˇď max αPr0,1s ? n Var 1{2 pξ 1 ´η1 q ´E ˇˇF 1 `Sη n `α `Sξ n ´Sη n ˘˘ˇˇ2 ¯1{2 . Moreover, if E|ξ 1 | 4 `E|η 1 | 4 ă 8, then ˇˇˇˇE F ˜n ÿ j"1 ξ j ¸´EF ˜n ÿ j"1 η j ¸ˇˇˇˇď CpF q ¨nˆV ar 1{2 pξ 1 ´η1 q `R2 4 `?n ´1R 3 4 ˘``E |ξ 1 ´η1 | 4 ˘1{4 R 3 4 ˙,
where R 4 " `max `E|ξ 1 | 4 , E|η 1 | 4 ˘˘1{4 and CpF q ą 0 is a constant that depends only on F .

Proof. See section A.

B 3 p ,F q ? n ˜r νpδq ∆ 1 M 2 ∆ `r ν4pδq ∆ 1 M 3 ∆ ? n ¸, R 4 p , Fq ă 8.
where r ν 4 pδq upper bounds ν 4 pδq and is of concave type. Below, we will use a crude bound ν 4 pδq ď 2R 4 p , Fq, but additional improvements are possible if better estimates of ν 4 pδq are available. Lemma 5.9. With probability at least 1 ´e´2s ,

sup f PF pδq ˇˇp G k p0; f q ´p G k p0; f ˚qˇď U pδ, sq `Cpρq ? k r Bpδq `4 O ? k .
where Cpρq ą 0 is constant that depends only on ρ.

Proof. See section A.4.

Next, we state the "uniform version" of Lemma 5.9:

Lemma 5.10. With probability at least 1 ´e´s , for all δ ě δ min simultaneously,

sup f PF pδq ˇˇp G k p0; f q ´p G k p0; f ˚qˇď Cpρqδ ˜r U pδ min , sq δ min `?k r Bpδ min q δ min ¸`4 O ? k
where Cpρq ą 0 is constant that depends only on ρ.

Proof. See section A.5.

It follows from Lemma 5.10 and inequality (5.13) that on event Θ 2 of probability at least 1 ´e´s , for all δ ě δ min simultaneously,

sup f PF pδq ˇˇˇˇp G k p0; f q ´p G k p0; f ˚q B z G k p0; f q ˇˇˇˇď Cpρqδ ˜r ∆ ? N r U pδ min , sq δ min `r ∆ ? n r Bpδ min q δ min ¸`4 r ∆ ? n O N . (5.18) Define s δ 2 :" min # δ ą 0 : C 2 pρq r ∆ ? N r U pδ, sq δ ď 1 7
+ , s δ 3 :" min # δ ą 0 : C 3 pρq r ∆ ? n r Bpδq δ ď 1 7
+
where C 2 pρq, C 3 pρq are sufficiently large constants. Then, on event Θ 2 X

! p δ N ą maxp s δ 2 , s δ 3 q ) , sup f PF p p δ N q ˇˇˇˇp G k p0; f q ´p G k p0; f ˚q B z G k p0; f q ˇˇˇˇď 2 p δ N 7 `4 r ∆ ? n O N (5.19)
for appropriately chosen C 2 pρq, C 3 pρq. Finally, we provide an upper bound for the process R N pf q defined via R N pf q " p G k p0; f q `Bz G k p0; f q ¨p e pkq pf q.

Lemma 5.11. Assume that conditions of Theorem 3.1 hold, and let δ min ą 0 be fixed. Then for all s ą 0, δ ě δ min , positive integers n and k such that

δ r U pδ min , sq δ min ? k `sup f PF G f pn, ∆q `s `O k ď cpρq, (5.20)
the following inequality holds with probability at least 1 ´7e ´s, uniformly over all δ satisfying (5.20):

sup f PF pδq |R N pf q| ď Cpρq ? N r ∆ 2 ∆ 2 ˆn1{2 δ 2 ˜r U pδ min , sq δ min ? N ¸2 ł σ 2 p , f ˚q ∆ 2 n 1{2 s N ł n 1{2 ˜sup f PF G f `n, ∆ ?n ¸2 ł n 3{2 s 2 N 2 ł n 3{2 O 2 N 2 ˙. (5.21)
Moreover, the bound of Theorem 3.1 holds on the same event.

Proof. See section A.6.

Recall that

s δ 2 " min # δ ą 0 : C 2 pρq r ∆ ? N r U pδ, sq δ ď 1 7
+
where C 2 pρq is a large enough constant. Let Θ 3 be the event of probability at least 1 ´7e ´s on which Lemma 5.11 holds with δ min " s δ 2 , and consider the event Θ 3 X t p δ N ą s δ 2 u. We will now show that on this event, Lemma 5.11 applies with δ " p δ N . Indeed, the bound of Theorem 3.1 is valid on Θ 3 , hence the inequality (3.4)

implies that on Θ 3 , p δ N ď Cpρq r ∆ ?
n , and it is straightforward to check that condition (5.20) of Lemma 5.11 holds with δ min " s δ 2 and δ " p δ N . It follows from inequality (5.13) that on event

Θ 3 X t p δ N ě s δ 2 u, sup f PF p p δ N q ˇˇˇR N pf q B z G k p0; f q ˇˇˇď Cpρq r ∆ 2 ∆ 2 ˆn1{2 r ∆ p δ 2 N ˜r ∆ ? N r U pδ 2 , sq δ 2 ¸2 ł r ∆ σ 2 p , f ˚q ∆ 2 n 1{2 s N ł n 1{2 r ∆ ˜sup f PF G f `n, ∆ ?n ¸2 ł n 3{2 r ∆ s 2 `O2 N 2
˙.

Consider the expression

Cpρq

r ∆ 2 ∆ 2 n 1{2 r ∆ p δ 2 N ˜r ∆ ? N r U pδ 2 , sq δ 2 ¸2 " Cpρq r ∆ 2 ∆ 2 ˜r ∆ ? N r U pδ 2 , sq δ 2 ¸2 p δ N ¨n1{2p δ N r ∆
and observe that whenever Theorem 3.1 holds,

n 1{2 p δ N r ∆
ď cpρq, hence the latter is bounded from above by

p δ N ¨Cpρq r ∆ 2 ∆ 2 ˜r ∆ ? N r U p s δ 2 , sq s δ 2 ¸2 ď p δ N 7
whenever ∆ ě σp , Fq (so that r ∆ " ∆) and C 2 pρq in the definition of s δ 2 is large enough. Moreover,

Cpρq r ∆ 3 ∆ 3 σ 2 p , f ˚q ∆ n 1{2 s N ď C 1 pρq ¨σp , f ˚q? n s N ď C 1 pρq r ∆ ? n s N if r ∆ ě σp , f ˚q. As s`O k ď c under the conditions of Theorem 3.1, n 3{2 r ∆ s 2 `O2 N 2 ď C r ∆ ? n s `O N .
Combining the inequalities obtained above, we deduce on event Θ 3 X t p δ N ě s δ 2 u,

2 sup f PF p p δ N q ˇˇˇR N pf q B z G k p0; f q ˇˇˇď 2 p δ N 7 `Cpρq r ∆ ˜?n s `O N ł sup f PF `Gf `n, ∆ ˘˘2 ? n ¸(5.22)
whenever r ∆ ě σp , Fq. Finally, define

s δ 4 :" C 4 pρq r ∆ ˜?n s `O N ł sup f PF `Gf `n, ∆ ˘˘2 ? n ¸,
where C 4 pρq is sufficiently large. Then on event Θ 3 X

! p δ N ě max `s δ 2 , 7 s δ 4 ˘), 2 sup f PF p p δ N q ˇˇˇR N pf q B z G k p0; f q ˇˇˇ`4 r ∆ ? n O N ď 2 p δ N 7 `p δ N 7 " 3 p δ N 7 . (5.23)
Note that the expression above takes care of the term 4 r ∆ ? n O N that appeared in (5.19). Combining (5.16),(5.19),(5.23), we deduce that on event Θ

1 X Θ 2 X Θ 3 X ! p δ N ě max `s δ 1 , s δ 2 , s δ 3 , 7 s δ 4 ˘), p δ N ď 6 7 p δ N leading to a contradiction, hence on event Θ 1 X Θ 2 X Θ 3 of probability at least 1 ´10e ´s, p δ N ď max `s δ 1 , s δ 2 , s δ 3 , 7 s δ 4 ˘. (5.24)
Recall the definition (5.15) of s δ 1 . If condition 2 ("Bernstein condition") holds, then r νpδq ď D ? δ for small enough δ, in which case

s δ 1 ď CpρqD 2 ˜s `O N `G2 f˚p n, ∆q n ¸,
where we used the fact that s k ď c by assumption. Together with the bound (3.1) for G f˚p n, ∆q, we deduce that, under the assumption that R 4 p , Fq ă 8,

s δ 1 ď CpρqD 2 ¨s `O N `´E ˇˇf ˚pX q ´Ef ˚pX q ˇˇ3 ¯2 ∆ 6 n 2 ‹ '. Since ∆ " σp , FqM ∆ , E ˇˇf˚pXq´Ef˚pXq ˇˇ3 ∆ 3 ď sup f PF E ˇˇfpXq´EfpXq ˇˇ3 σ 3 p ,F qM 3 ∆ ď B 3 p ,F q M 3 ∆ , where
Bp , Fq " sup f PF E 1{4 p pf pXqq ´E pf pXqqq 4 σp , Fq , hence s δ 1 ď CpρqD 2 ˆs `O N `B6 p , Fq n 2 M 6 ∆ ˙. (5.25)
At the same time, if only σp , Fq ă 8, we similarly obtain that

s δ 1 ď CpρqD 2 ˆs `O N `1 M 4 ∆ n ˙. (5.26)
Next we will estimate s δ 3 . Recall that, when R 4 p , Fq ă 8,

r Bpδq " B 3 p , Fq ? n ˜r νpδq ∆ 1 M 2 ∆ `r ν 4 pδq ∆ 1 M 3 ∆ ? n ¸.
For sufficiently small δ (namely, for which condition 2 holds) and ∆ ě σp , Fq,

r ∆ ? n r Bpδq ď B 3 p , Fq n ˆr νpδq M 2 ∆ `R4 p , Fq M 3 ∆ ? n ˙ď B 3 p , Fq n ˜D ? δ M 2 ∆ `σp , Fq Bp , Fq M 3 ∆ ? n and s δ 3 ď Cpρq ˆD2 B 6 p , Fq n 2 M 4 ∆ `σp , Fq B 4 p , Fq n 3{2 M 3 ∆ ˙. (5.27)
At the same time, if only the second moments are finite, r Bpδq " r νpδq ∆ 1 M∆ , and it is easy to deduce that in this case,

s δ 3 ď Cpρq D 2 M 2 ∆ n . (5.28)
Next, we obtain a simpler bound for s δ 4 : as ∆ ě σp , Fq by assumption, r ∆ " ∆ " σp , Fq M ∆ , and the estimate (3.1) for G f˚p n, ∆q implies (if R 4 p , Fq ă 8) that

s δ 4 ď Cpρq σp , Fq ˆ?nM ∆ s `O N `B6 p , Fq M 5 ∆ n 3{2 ˙. (5.29)
If only σp , Fq ă 8, we similarly deduce from (3.1) that

s δ 4 ď Cpρq σp , Fq ˆ?nM ∆ ¨s `O N `1 M 3 ∆ ? n ˙. (5.30)
Finally, recall that

r U pδ, sq " 2 ∆ ˆcpγq r ωpδq `r νpδq c s 2 ˙`32s ? k and s δ 2 " min ! δ ą 0 : C 2 pρq r ∆ ? N r U pδ,sq δ ď 1 7 ) , hence s δ 2 ď s δ ł CpρqD 2 s N ł Cpρqσp , Fq s ? nM ∆ N , (5.31)
where s δ was defined in (3.5). Combining inequalities (5.25), (5.31) (5.27), (5.29) and (5.24), we obtain the final form of the bound under the stronger assumption R 4 p , Fq ă 8. Similarly, the combination of (5.26), (5.31) (5.28), (5.30) and (5.24) yields the bound under the weaker assumption σp , Fq ă 8.

Proof of Theorem 3.4.

Recall that p E N pf ˚q :" p L pkq pf ˚q ´p L pkq p p f 1 N q is the "empirical excess risk" of f ˚, and let p δ N :" Ep p f 1 N q. It follows from Remark 5.1 that (using the notation used in the proof of Theorems 3.2 and 3.3)

p E N pf ˚q ď ˇˇˇˇˇp G k ´0; p f 1 N Bz G ´0; p f 1 N ¯´p G k p0; f ˚q B z G p0; f ˚q ˇˇˇˇˇ`2 sup f PF p p δ N q ˇˇˇR N pf q B z G k p0; f q ˇˇˇ.
On the event of Theorem 3.3 of probability at least 1 ´10e ´s,

Ep p f 1 N q ď δ 1 :" s δ `Cpρq `D2 σp , Fq ? nM ∆ ˘ˆB 6 p , Fq M 4 ∆ n 2 `s `O N ˙,
hence on this event

p E N pf ˚q ď sup f PF pδ 1 q ˇˇˇˇp G k p0; f q B z G p0; f q ´p G k p0; f ˚q B z G p0; f ˚q ˇˇˇˇ`2 sup f PF pδ 1 q ˇˇˇR N pf q B z G k p0; f q ˇˇˇď 6 7 δ 1
where the last inequality again follows from main steps in the proof of Theorem 3.3. 4 Consider the set

p Fpδ 1 q " ! f P F : p E N pf q ď δ 1
)

. First, observe that on the event E 1 of Theorem 3.3, f ˚P p Fpδ 1 q as implied by the previous display. We will next show that p Fpδ 1 q Ď Fp7δ 1 q on the event E 1 of Theorem 3.3, meaning that for any f P p Fpδ 1 q, Epf q ď 7δ 1 . Indeed, let f P p Fpδ 1 q be such that Epf q " σ. Then (5.8) implies that Lpf q ´Lpf ˚q ď p

L pkq pf q ´p L pkq pf ˚q `ˇˇˇˇp G k p0; f q B z G k p0; f q ´p G k p0; f ˚q B z G k p0; f ˚q ˇˇˇˇ`ˇˇˇˇRN pf q B z G k p0; f q `RN pf ˚q B z G k p0; f ˚q ˇˇď p E N pf q `sup f PF pσq ˇˇˇˇp G k p0; f q B z G k p0; f q ´p G k p0; f ˚q B z G k p0; f ˚q ˇˇˇˇ`2 sup f PF pσq ˇˇˇR N pf q B z G k p0; f q ˇˇˇ.
Again, it follows from the arguments used in proof of Theorem 3.3 that on event E 1 of probability at least 1 ´10e ´s,

sup f PF pσq ˇˇˇˇp G k p0; f q B z G k p0; f q ´p G k p0; f ˚q B z G k p0; f ˚q ˇˇˇˇ`2 sup f PF pσq ˇˇˇR N pf q B z G k p0; f q ˇˇˇď 6 7 max `δ1 , σ ˘.
Consequently, σ ď δ 1 `6 7 max pδ 1 , σq on this event, implying that σ ď 7δ 1 . Next, Assumption 2 yields that sup

f P p F pδ 1 q Var ´ pf pXqq ´ p p f 1 N q ď 2 ˜sup f P p F pδ 1 q
Var p pf pXqq ´ pf ˚pX qqq `Var

´ p p f 1 N pXqq ´ pf ˚pX qq ¯¸ď 2Dp ? 7 `1qδ 1 on E 1 . It remains to apply Theorem 3.3, conditionally on E 1 , to the class p Fpδ 1 q ´p f 1 N :" ! f ´p f 1 N , f P p Fpδ 1 q ) .
To this end, we need to verify the assumption of Theorem 3.1 that translates into the requirement

c∆ 2 ě 1 ? k 2 E sup f PF p7δ 1 q 1 a |S 2 | |S2| ÿ j"1
p pf pX j qq ´ pf ˚pX j qq ´P p pf q ´ pf ˚qqq .

As δ 1 ą s δ and |S 2 | ě tN {2u, we have the inequality

E sup f PF p7δ 1 q 1 a |S 2 | |S2| ÿ j"1
p pf pX j qq ´ pf ˚pX j qq ´P p pf q ´ pf ˚qqq ď Cδ 1 ? N ,

hence it suffices to check that ∆ 2 " DM ∆2 ? 7δ 1 ě Cδ 1 b N k2 . The latter is equivalent to δ 1 ď CD 2 M 2 ∆2 k2 N
that holds by assumption. Result now follows easily as we assumed that the subsamples S 1 and S 2 used to construct p

f 1 N and p f 2 N are disjoint. s L 1 pf q ´Lpf q ∆ ˙.
Let W p pf qq denote a centered normal random variable variance equal to Var p pf pXqqq. Lemma 5.2 implies that

ˇˇˇE ρ 2 ˆ?n s L 1 pf q ´Lpf q ∆ ˙´Eρ 2 ˆW p pf qq ∆ ˙ˇˇˇď C }ρ p5q } 8 ∆ 3 ? n E ˇˇ pf pXqq ´P pf q ˇˇ3 .
Next, as ρ 2 pxq ě It|x| ď 1u by assumption, A.2. Proof of Lemma 5.7.

Eρ
Observe that

1 ? k k ÿ j"1 ρ 1 ˆ?n s L 1 pf q ´Lpf q ∆ ˙" 1 ? k ÿ jPJ ρ 1 ˆ?n s L 1 pf q ´Lpf q ∆ ˙`1 ? k ÿ jRJ ρ 1 ˆ?n s L 1 pf q ´Lpf q ∆ ď c |J| k 1 a |J| ÿ jPJ ρ 1 ˆ?n s L 1 pf q ´Lpf q ∆ ˙`2 O ? k ,
where we used the fact that }ρ 1 } 8 ď 2. Bernstein's inequality implies that

ˇˇˇˇ1 a |J| ˜ÿ jPJ ρ 1 ˆ?n s L 1 pf q ´Lpf q ∆ ˙´Eρ 1 ˆ?n s L 1 pf q ´Lpf q ∆ ˙¸ˇˇˇˇď 2 ˜Var 1{2 ˆρ1 ˆ?n s L 1 pf q ´Lpf q ∆ ˙˙? s `2s a |J|
with probability at least 1´2e ´s, where we again used the fact that }ρ 1 } 8 ď 2. Moreover, Var ´ρ1 ´?n

s L1pf q´Lpf q ∆ ¯¯ď σ 2 p ,f q ∆ 2
by Lemma 5.1, hence with the same probability

| p G k p0; f q| ď ? k ˇˇˇE ρ 1 ˆ?n s L 1 pf q ´Lpf q ∆ ˙ˇˇˇ`2 ˆσp , f q ∆ ? s `2s ? k `O ? k ˙.
Lemma 6.2 in [START_REF] Minsker | Uniform bounds for robust mean estimators[END_REF] implies that

ˇˇˇE ρ 1 ˆ?n s L 1 pf q ´Lpf q ∆ ˙ˇˇˇď Eρ 1 ˆW p pf qq ∆ looooooooomooooooooon "0 `2G f pn, ∆q,
hence the claim follows.

A.3. Proof of Lemma 5.8.

Since F is smooth, for any x, y P R, F pyq ´F pxq " ş 1 0 F 1 px `αpy ´xqqdα ¨py ´xq. Let S ξ n "

ř n j"1 ξ j , S η n " ř n j"1 η j . Then F `Sξ n ˘´F pS η n q " `Sξ n ´Sη n ˘ż 1 0 F 1 `Sη n `α `Sξ n ´Sη n ˘˘dα, hence E `F `Sξ n ˘´F pS η n q ˘" ż 1 0 E "`S ξ n ´Sη n ˘F 1 `Sη n `α `Sξ n ´Sη n ˘˘‰ dα.
Hölder's inequality yields that

ˇˇE `Sξ n ´Sη n ˘F 1 `Sη n `α `Sξ n ´Sη n ˘˘ˇˇˇď ´E ˇˇS ξ n ´Sη n ˇˇ2 ¯1{2 ´E ˇˇF 1 `Sη n `α `Sξ n ´Sη n ˘˘ˇˇ2 ¯1{2 ď ? n Var 1{2 pξ 1 ´η1 q ´E ˇˇF 1 `Sη n `α `Sξ n ´Sη n ˘˘ˇˇ2 ¯1{2 ,
implying the first inequality. The rest of the proof is devoted to the second inequality of the lemma. Let pW, Zq be a centered Gaussian vector with the same covariance as pξ 1 , η 1 q, and let pW 1 , Z 1 q, . . . , pW n , Z n q be i.i.d. copies of pW, Zq. We also set S W n " To this end, we will use Lindeberg's replacement method. For i " 0, . . . , n, denote

ř n j"1 W j , S Z n " ř n j"1 Z j .
T i " pξ 1 ´η1 , . . . , ξ i ´ηi , W i`1 ´Zi`1 , . . . , W n ´Zn , η 1 , . . . , η i , Z i`1 , . . . , Z n q.
Then the expression in (A.1) is equal to |EGpT n q ´EGpT 0 q|, where GpT q " ˜n ÿ

i"1

T piq ¸F 1 ˜n ÿ j"1
´T pj`nq `αT pjq ¯and T pjq stands for the j-th coordinate of T . Clearly,

|EGpT n q ´EGpT 0 q| ď n ÿ i"1 |EGpT i q ´EGpT i´1 q| . (A.2)
Fix i, and consider the Taylor expansions of GpT i q and GpT i´1 q at the point T 0 i " pξ 1 ´η1 , . . . , ξ i´1 ´ηi´1 , 0, W i`1 ´Zi`1 , . . . , W n ´Zn , η 1 , . . . , η i´1 , 0, Z i`1 , . . . , Z n q (note that T 0 i does not depend on ξ i , η i , W i and Z i ). For GpT i q we get, setting δ i " ξ i ´ηi ,

GpT i q " GpT 0 i q `Bi GpT 0 i q ¨δi `Bn`i GpT 0 i q ¨ηi `1 2 `B2 i,i GpT 0 i q ¨δ2 i `2B 2 i,n`i GpT 0 i q ¨δi η i `B2 n`i,n`i GpT 0 i q ¨η2 i 1 6 ´B3 i,i,i Gp T 0 i q ¨δ3 i `B3 n`i,n`i,n`i Gp T 0 i q ¨η3 i `B3 n`i,n`i,i Gp T 0 i q ¨η2 i δ i `B3 n`i,i,i Gp T 0 i q ¨ηi δ 2 i ¯,
where T 0 i is a point on a line segment between T 0 i and T i . Similarly, setting ∆ i " W i ´Zi , GpT i´1 q " GpT 0 i q `GpT 0 i q `Bi GpT 0 i q ¨∆i `Bn`i GpT 0

i q ¨Zi `1 2 `B2 i,i GpT 0 i q ¨∆2 i `B2 i,n`i GpT 0 i q ¨∆i Z i `B2 n`i,n`i GpT 0 i q ¨Z2 i 1 6 ´B3 i,i,i Gp T 0 i q ¨∆3 i `B3 n`i,n`i,n`i Gp T 0 i q ¨Z3 i `3B 3 n`i,n`i,i Gp T 0 i q ¨Z2 i ∆ i `3B 3 n`i,i,i Gp T 0 i q ¨Zi ∆ 2 i ¯, (A.3)
where T 0 i is a point on a line segment between T 0 i and T i´1 . Using independence of T 0 i and pξ i , η i , W i , Z i q and the fact that covariance structures of pξ i , η i q and pW, Zq are the same, we deduce that

|EGpT i q ´EGpT i´1 q| ď 1 6 E ˇˇB 3 i,i,i Gp T 0 i q ¨δ3 i `B3 n`i,n`i,n`i Gp T 0 i q ¨η3 i `3B 3 n`i,n`i,i Gp T 0 i q ¨η2 i δ i `3B 3 n`i,i,i Gp T 0 i q ¨ηi δ 2 i ˇ1 6 E ˇˇB 3 i,i,i Gp T 0 i q ¨∆3 i `B3 n`i,n`i,n`i Gp T 0 i q ¨Z3 i `3B 3 n`i,n`i,i Gp T 0 i q ¨Z2 i ∆ i `3B 3 n`i,i,i Gp T 0 i q ¨Zi ∆ 2 i ˇˇ.
It remains estimate each of the terms above. Assume that τ P r0, 1s is such that T 0 i " pξ 1 ´η1 , . . . , ξ i´1 ´ηi´1 , τ pξ i ´ηi q, W i`1 ´Zi`1 , . . . , W n ´Zn , η 1 , . . . , η i´1 , τ η i , Z i`1 , . . . , Z n q.

1. Direct computation implies that

B 3 i,i,i Gp T 0 i q " 3α 2 F 3 ˜ÿ j‰i ´ηj `αδ j ¯`τ pη i `αδ i q α3 F 4 ˜ÿ j‰i ´ηj `αδ j ¯`τ pη i `αδ i q ¸´ÿ j‰i δ j `τ δ i ¯, hence E ˇˇB 3 i,i,i Gp T 0 i q ¨δ3 i ˇˇď 3α 2 }F 3 } 8 E|δ 3 i | `α3 }F 4 } 8 ˜Eˇˇÿ j‰i δ j ˇˇE|δ i | 3 `E|δ i | 4 ḑ 3α 2 }F 3 } 8 `Eδ 2 i ˘1{2 `Eδ 4 i ˘1{2 `α3 }F 4 } 8 ¨dÿ j‰i Eδ 2 j `Eδ 2 i ˘1{2 `Eδ 4 i ˘1{2 `E|δ i | 4 ', (A.4)
where we used Hölder's inequality in the last step. 2. Next, B 3 G ηi,ηi,ηi p T 0 i q " F 4 ˜ÿ j‰i ´ηj `αδ j ¯`τ pη i `αδ i q ¸´ÿ j‰i δ j `τ δ i ¯, hence Hölder's inequality, together with the identity }F 4 } 8 " M ´3}H 4 } 8 , imply that

E ˇˇB 3 n`i,n`i,n`i Gp T 0 i q ¨η3 i ˇˇď }F 4 } 8 ˜E|η i | 3 E ˇˇˇˇÿ j‰i δ j ˇˇˇˇ`E |δ i η 3 i | ḑ }F 4 } 8 ¨E|η i | 3 d ÿ j‰i Eδ 2 j ``Eδ 4 i ˘1{4 `Eη 4 i ˘3{4 '. (A.5)
3. Proceeding in a similar fashion, we deduce that

B 3 G n`i,n`i,i p T 0 i q " F 3 ˜ÿ j‰i ´ηj `αδ j ¯`τ pη i `αδ i q αF 4 ˜ÿ j‰i ´ηj `αδ j ¯`τ pη i `αδ i q ¸´ÿ j‰i δ j `τ δ i ¯,
so that, applying Hölder's inequality, we obtain

E ˇˇB 3 n`i,n`i,i Gp T 0 i q ¨η2 i δ i ˇˇď }F 3 } 8 `Eη 4 i ˘1{2 `Eδ 2 i ˘1{2 `α}F 4 } 8 E ˇˇˇη 2 i δ i ˆÿ j‰i δ j `τ δ i ˙ˇˇď }F 3 } 8 `Eη 4 i ˘1{2 `Eδ 2 i ˘1{2 `α}F 4 } 8 ¨dÿ j‰i Eδ 2 j `Eη 4 i ˘1{2 `Eδ 2 i ˘1{2 `bEδ 4 i Eη 4 i '. (A.6)
4. Finally,

B 3 G n`i,i,i p T 0 i q " 2αF 3 ˜ÿ j‰i ´ηj `αδ j ¯`τ pη i `αδ i q α2 F 4 ˜ÿ j‰i ´ηj `αδ j ¯`τ pη i `αδ i q ¸´ÿ j‰i δ j `τ δ i ¯.
Hölder's inequality implies that

E|η i δ 2 i | " E|η i δ i δ i | ď `Eδ 2 i ˘1{2 `Eδ 4 i ˘1{4 `Eη 4 i ˘1{4 , hence ˇˇEB 3 n`i,i,i Gp T 0 i q ¨ηi δ 2 i ˇˇď 2α}F 3 } 8 `Eδ 2 i ˘1{2 `Eδ 4 i ˘1{4 `Eη 4 i ˘1{4 `α2 }F 4 } 8 E ˇˇηiδ 2 i ´ÿ j‰i δ j `τ δ i ¯ˇď 2α}F 3 } 8 `Eδ 2 i ˘1{2 `Eδ 4 i ˘1{4 `Eη 4 i ˘1{4 `α2 }F 4 } 8 ¨dÿ j‰i Eδ 2 j `Eδ 2 i ˘1{2 `Eδ 4 i ˘1{4 `Eη 4 i ˘1{4 ``Eδ 4 i ˘3{4 `Eη 4 i ˘1{4 '. (A.7)
Similar calculations yield an analogous bound for the terms in the expansion (A.3) of GpT i´1 q. The equivalence of the moments of Gaussian random variables together with the fact that the covariance structure of pW, Zq matches that of pξ 1 , η 1 q imply that the upper bounds (A.4),(A.5),(A.6),(A.7) remain valid for the terms in (A.3), up to an additional absolute multiplicative constant. Hence, combination of (A.2), (A.4),(A.5),(A.6), (A.7) and straightforward application of Hölder's inequality yields the result.

A.4. Proof of Lemma 5.9.

Define

Dpδq :" sup pf qPF pδq

E 1{2 ˆρ1 ˆ?n s L j pf q ´Lpf q ∆ ˙´ρ 1 ˆ?n s L j pf ˚q ´Lpf ˚q ∆ ˙˙2 .
Recall that ρ 1 is Lipschitz continuous and Lpρ 1 q " 1, hence ˆρ1 ˆ?n s L 1 pf q ´Lpf q ∆ ˙´ρ 1 ˆ?n s L 1 pf ˚q ´Lpf ˚q ∆ ˙˙2 ď ˆ?n s L 1 pf q ´s L 1 pf ˚q ´pLpf q ´Lpf ˚qq ∆ ˙2 , (A. .11) with probability at least 1 ´2e ´s. According to (A.9), Dpδq ď Lpρ 1 q ∆ νpδq. Hence, it remains to estimate the expected supremum. Sequential application of symmetrization, contraction and desymmetrization inequalities implies that

s ą 0 sup f PF pδq ˇˇp G |J| p0; f q ´p G |J| p0; f ˚q ´E ´p G |J| p0; f q ´p G |J| p0; f ˚q¯ˇď 2 " E sup f PF pδq ˇˇp G |J| p0; f q ´p G |J| p0; f ˚q ´E ´p G |J| p0; f q ´p G |J| p0; f ˚q¯ˇ`D pδq c s 2 `32 ? 2s 3 ? k  (A
E sup f PF pδq ˇˇp G |J| p0; f q ´p G |J| p0; f ˚q ´E ´p G |J| p0; f q ´p G |J| p0; f ˚q¯ď 2E sup f PF pδq ˇˇˇˇ1 a |J| ÿ jPJ ε j ˆρ1 ˆ?n s L j pf q ´Lpf q ∆ ˙˙´ρ 1 ˆ?n s L j pf ˚q ´Lpf ˚q ∆ ˙ˇˇˇď 4Lpρ 1 q ∆ E sup f PF pδq ˇˇˇˇˇ? n a |J| ÿ jP|J| ε j `p s L j pf q ´Lpf qqpX j q ´p s L j pf ˚q ´Lpf ˚qqpX j q ˘ˇˇˇˇď 8 ? 2Lpρ 1 q ∆ E sup f PF pδq ˇˇˇˇ1 ? N N J ÿ j"1
´p pf q ´ pf ˚qqpX j q ´P p pf q ´ pf ˚qq ¯ˇˇˇˇď 8

? 2 ∆ ωpδq (A.12)
since Lpρ 1 q " 1. To estimate sup f PF pδq |G k p0; f q ´Gk p0; f ˚q|, we consider 2 cases: the first case when only 2 finite moments of pf pXqq, f P F exist, and the second case when 4 moments are finite. To obtain the bound in the first case, we observe that, since E ´?n s L1pf q´Lpf q ∆ ¯" 0 for any f P F, . The first inequality of the lemma implies that

ˇˇˇE ρ 1 ˆ?n s L 1 pf q ´Lpf q ∆ ˙´Eρ 1 ˆ?n s L 1 pf
ˇˇˇE ρ 1 ˆ?n s L 1 pf q ´Lpf q ∆ ˙´Eρ 1 ˆ?n s L 1 pf ˚q ´Lpf ˚q ∆ ˙ˇˇˇď d Var ˆ pf pXqq ´ pf ˚pX qq ∆ ṁax αPr0,1s d E ˆT 1 ˆα? n s L 1 pf q ´Lpf q ∆ `p1 ´αq ? n s L 1 pf ˚q ´Lpf ˚q ∆ ˙˙2 .
Observe that T 1 pxq " 1 ´ρ2 pxq ď I t|x| ě 1u by Assumption 1. It implies that for any α P r0, 1s,

E ˆT 1 ˆα? n s L 1 pf q ´Lpf q ∆ `p1 ´αq ? n s L 1 pf ˚q ´Lpf ˚q ∆ ˙˙2 ď Pr ˆˇˇˇα? n s L 1 pf q ´Lpf q ∆ `p1 ´αq ? n s L 1 pf ˚q ´Lpf ˚q ∆ ˇˇˇě 1 ď sup f PF Var ˆ?n s L 1 pf q ´Lpf q ∆ ˙" sup f PF σ 2 p , f q ∆ 2 .
by Chebyshev's inequality. Hence

ˇˇˇE ρ 1 ˆ?n s L 1 pf q ´Lpf q ∆ ˙´Eρ 1 ˆ?n s L 1 pf
|G k p0; f q ´Gk p0; f ˚q| ď Cpρq c k n ˜νpδq ∆ ˆB3 p , Fq M 3 ∆ _ B 2 p , Fq M 2 ∆ ˙`ν 4 pδq ∆ B 3 p , Fq M 3 ∆ ? n ḑ Cpρq c k n B 3 p , Fq ˜νpδq ∆ 1 M 2 ∆ `ν4 pδq ∆ 1 M 3 ∆ ? n ¸ď Cpρq ? k r Bpδq, (A.14)
implying the result.

A.5. Proof of Lemma 5.10.

Recall that p

G |J| p0; f q :" 1 ? |J| ř jPJ ρ 1 ´?n p s Lj pf q´Lpf qq´z ∆ ¯. Given δ ě δ min , define p Q |J| pδq :" sup f PF pδq δ min δ ˇˇp G |J| p0; f q ´p G |J| p0; f ˚qˇ, p T |J| pδ min q :" sup δěδmin p Q |J| pδq.
Observe that for any δ ě δ min , sup

f PF pδq ˇˇp G |J| p0; f q ´p G |J| p0; f ˚qˇď δ δ min p T |J| pδ min q. (A.15)
Hence, our goal will be to find an upper bound for p T |J| pδ min q. To this end, note that

p T |J| pδ min q ď sup δěδmin sup f PF pδq δ min δ ˇˇp G |J| p0; f q ´p G |J| p0; f ˚q ´E ´p G |J| p0; f q ´p G |J| p0; f ˚q¯š up δěδmin sup f PF pδq δ min δ |G k p0; f q ´Gk p0; f ˚q| . (A.
δ min δ ˇˇp G |J| p0; f q ´p G |J| p0; f ˚q ´E ´p G |J| p0; f q ´p G |J| p0; f ˚q¯ď 2 " E sup δěδmin sup f PF pδq δ min δ ˇˇp G |J| p0; f q ´p G |J| p0; f ˚q ´E ´p G |J| p0; f q ´p G |J| p0; f ˚q¯Ľ pρ 1 q ∆ r νpδ min q c s 2 `32 ? 2s 3 ? k  (A.17)
with probability at least 1 ´e´s . To estimate the expectation, we proceed as follows: for j P Z, set δ j :" 2 ´j , and observe that

E sup δěδmin sup f PF pδq δ min δ ˇˇp G |J| p0; f q ´p G |J| p0; f ˚q ´E ´p G |J| p0; f q ´p G |J| p0; f ˚q¯ď E sup j:δj ěδmin sup δPpδj`1,δj s δ min δ sup f PF pδq ˇˇp G |J| p0; f q ´p G |J| p0; f ˚q ´E ´p G |J| p0; f q ´p G |J| p0; f ˚q¯ď ÿ j:δj ěδmin δ min δ j`1 E sup δPpδj`1,δj s sup f PF pδq ˇˇp G |J| p0; f q ´p G |J| p0; f ˚q ´E ´p G |J| p0; f q ´p G |J| p0; f ˚q¯ď 2 ÿ j:δj ěδmin δ min δ j E sup f PF pδj q ˇˇp G |J| p0; f q ´p G |J| p0; f ˚q ´E ´p G |J| p0; f q ´p G |J| p0; f ˚q¯ˇ,
where the last inequality relied on the fact that Fpδq Ď Fpδ 1 q for δ ď δ 1 . It follows from (A.12) that

E sup f PF pδj q ˇˇp G |J| p0; f q ´p G |J| p0; f ˚q ´E ´p G |J| p0; f q ´p G |J| p0; f ˚q¯ˇď 8 ? 2Lpρ 1 q ∆ ωpδ j q ď 8 ? 2 ∆ r ωpδ j q,
where r ωp¨q is an upper bound on ωp¨q of strictly concave type (with exponent γ for some γ P p0, 1q The following identity is immediate:

R N pf q " p G k ´p e pkq pf q; f loooooooomoooooooon "0

`Bz G k p0; f q ¨p e pkq pf q ´´p G k ´p e pkq pf q; f ¯´p G k p0; f q ¯.

Assumptions on ρ imply that for any f P F and j " 1, . . . , k, there exists τ j P r0, 1s such that ρ 1 ˆ?n s L j pf q ´Lpf q ´p e pkq pf q ∆ ˙" ρ 1 ˆ?n s L j pf q ´Lpf q ∆ ˙´? n ∆ ρ 2 ˆ?n s L j pf q ´Lpf q ∆ ˙¨p e pkq pf q `n ∆ 2 ρ 3 ˆ?n s L j pf q ´Lpf q ´τj p e pkq pf q ∆ ˙¨´p e pkq pf q ¯2 , (A. [START_REF] Hoeffding | A class of statistics with asymptotically normal distribution[END_REF])

hence p G k ´p e pkq pf q; f ¯´p G k p0; f q " ´?n ∆ p e pkq pf q ? k k ÿ j"1 ρ 2 ˆ?n s L j pf q ´Lpf q ∆ ṅ ∆ 2
`p e pkq pf q ˘2 ? k k ÿ j"1 ρ 3 ˆ?n s L j pf q ´Lpf q ´τj p e pkq pf q ∆ ˙, and

R N pf q " ? n ∆ p e pkq pf q ? k k ÿ j"1 ˆρ2 ˆ?n s L j pf q ´Lpf q ∆ ˙´Eρ 2 ˆ?n s L j pf q ´Lpf q ∆ ˙ṅ ∆ 2
`p e pkq pf q ˘2 ? k k ÿ j"1 ρ 3 ˆ?n s L j pf q ´Lpf q ´τj p e pkq pf q ∆ ˙. (A.20)

We will need the following modification of Theorem 3.1 that is stated below and proved in Section A.7.

Lemma A.1. Then there exist positive constants cpρq, Cpρq with the following properties. Fix δ min ą 0. Then for all s ą 0, δ ě δ min , positive integers n and k such that

δ r U pδ min , sq δ min ? k `sup f PF G f pn, ∆q `s `O k ď cpρq, (A.21)
the following inequality holds with probability at least 1 ´2e ´s:

sup f PF pδq ˇˇp e pkq pf q ˇˇď Cpρq r ∆ « δ ? N r U pδ min , sq δ min `σp , f ˚q ∆ c s N `sup f PF G f pn, ∆q ? n `ps `Oq ? n N ff . (A.22)
In the rest of the proof, we will assume that conditions of Lemma A.1 and Theorem 3.1 hold, and let Θ 1 be an event of probability at least 1 ´4e ´s on which inequalities (A.22) and (3.4) are valid. On event Θ 1 , the last term in (A.20) can thus be estimated as

sup f PF pδq ˇˇˇˇn ∆ 2 `p e pkq pf q ˘2 ? k k ÿ j"1 ρ 3 ˆ?n s L j pf q ´Lpf q ´τj p e pkq pf q ∆ ˙ˇˇˇˇď C 1 pρq ? nN ∆ 2 sup f PF pδq ˇˇp e pkq pf q ˇˇ2 ď C 2 pρq ? N r ∆ 2 ∆ 2 ˆn1{2 δ 2 N ˜r U pδ min , sq δ min ¸2 ł σ 2 p , f ˚q ∆ 2 n 1{2 s N ł n 1{2 ˜sup f PF G f `n, ∆ ?n ¸2 ł n 3{2 s 2 `O2 N 2 ˙. (A.23)
where we used the fact that }ρ 3 } 8 ă 8. It remains to estimate the first term in (A.20). The required bound will follow from the combination of Theorem A.1 and the following lemma that is proved in Section A.8.

Lemma A.2. Fix δ min ą 0. With probability at least 1 ´3e ´s, for all δ ě δ min simultaneously,

sup f PF pδq ˇˇˇˇ1 ? k k ÿ j"1 ˆρ2 ˆ?n s L j pf q ´Lpf q ∆ ˙´Eρ 2 ˆ?n s L j pf q ´Lpf q ∆ ˙˙ˇˇˇˇď Cpρq ˜δ r U pδ min , sq δ min `σp , f ˚q ∆ ? s `s `O ? k ¸.
Let Θ 2 be the event of probability at least 1 ´3e ´2s on which the inequality of Lemma A.2 holds. Then simple algebra yields that on event Θ 1 X Θ 2 of probability at least 1 ´7e ´s,

sup f PF pδq ˇˇˇˇ? n ∆ p e pkq pf q ? k k ÿ j"1 ˆρ2 ˆ?n s L j pf q ´Lpf q ∆ ˙´Eρ 2 ˆ?n s L j pf q ´Lpf q ∆ ˙˙ˇˇˇˇď C 3 pρq ? N r ∆ ∆ ˆn1{2 δ 2 N ˜r U pδ min , sq δ min ¸2 ł σ 2 p , f ˚q ∆ 2 n 1{2 s N ł n 1{2 ˜sup f PF G f `n, ∆ ?n ¸2 ł n 3{2 s 2 `O2 N 2 ˙. (A.24)
Combination of inequalities (A.23) and (A.24) that hold with probability at leat 1´7e ´s yields the result.

A.7. Proof of Lemma A.1.

In the situation when δ is fixed, the argument mimics the proof of Theorem 4.1 in [START_REF] Minsker | Uniform bounds for robust mean estimators[END_REF], with minor modifications outlined below. Recall that p G k pz; f q " 1 ? k k ÿ j"1 ρ 1 ˆ?n p s L j pf q ´Lpf qq ´z ∆

˙.

Let z 1 , z 2 be such that on an event of probability close to 1, p G k pz 1 ; f q ą 0 and p G k pz 2 ; f q ă 0 for all f P Fpδq simultaneously. Since p G k is decreasing in z, it is easy to see that p e pkq pf q P pz 1 , z 2 q for all f P Fpδq on this event. Hence, our goal is to find z 1 , z We will proceed in 4 steps: first, we will find ε 1 ą 0 such that for any z P R and all f P Fpδq, .25) under assumption that ε1`ε2`ε3 ? k `O k ď c for some absolute constants c, C ą 0. Proceeding in a similar way, it is easy to see that setting z 2 " ´z1 guarantees that p G k pz 2 ; f q ă 0 for all f P Fpδq with probability at least 1 ´e´s , hence the claim follows.

It remains to make the bound uniform in δ ě δ min . To this end, we need to repeat the "slicing argument" of Lemma 5.10 below (specifically, see equation (A.18)) to deduce that with probability at least 1 ´2e ´s, ˆρ2 ˆ?n s L j pf q ´Lpf q ∆ ˙´Eρ 2 ˆ?n s L j pf q ´Lpf q ∆ ˙" 1 ? k ÿ jRJ ˆρ2 ˆ?n s L j pf q ´Lpf q ∆ ˙´Eρ 2 ˆ?n s L j pf q ´Lpf q ∆ ˙1 ? k ÿ jPJ ˜ρ2 ˆ?n s L j pf q ´Lpf q ∆ ˙´ρ 2 ˆ?n s L j pf ˚q ´Lpf ˚q ∆ Ė ˆρ2 ˆ?n s L j pf q ´Lpf q ∆ ˇˇď 1 ¯¯2 , E ˆρ2 ˆ?n s L j pf q ´Lpf q ∆ ˙˙2 ď Pr ˆˇˇˇ? n s L j pf q ´Lpf q ∆ ˇˇˇď 1 ˙`Pr ˆˇˇˇ? n s L j pf q ´Lpf q ∆ ˇˇˇP r1, 2s ˙, and Var ˆρ2 ˆ?n s L j pf q ´Lpf q ∆ ˙˙ď Pr ˆˇˇˇ? n s L j pf q ´Lpf q ∆ ˇˇˇď 1 ˙´ˆP r ˆˇˇˇ? n s L j pf q ´Lpf q ∆ ˇˇˇď 1 ˙˙2

˙´ρ
`Pr ˆˇˇˇ? n s L j pf q ´Lpf q ∆ ˇˇˇě 1 ď 2Pr ˆˇˇˇ? n s L j pf q ´Lpf q ∆ ˇˇˇě 1 ˙ď 2 Var p pf pXqqq ∆ 2 .

Bernstein's inequality implies that with probability at least A.9. Proof of Lemma 4.1.

In the context of regression with quadratic loss, ωpδq takes the form ωpδq " E sup pf qPF pδq ˇˇˇˇ1 ?

N N ÿ j"1
´pY j ´f pZ j qq 2 ´pY j ´f˚p Z j qq 2 ´E `pY j ´f pZ j qq 2 ´pY j ´f˚p Z j qq 2 ˘¯ˇˇˇˇˇ.

for an absolute constant C ą 0. Finally, since }F } ψ2 ă 8,

E › › F 2 › › L8pΠ N q ď C 1 logpN q}F 2 } ψ1 " C 1 logpN q}F } 2 ψ2 , hence E sup BpF ;2δq ˇˇˇˇ1 ? N N ÿ j"1
pf pZ j q ´f˚p Z j qq 2 ´Epf pZ j q ´f˚p Z j qq 2 ˇˇˇď C 2 ˜?δ ? V logpA 2 N q}F } ψ2 ł V }F } 2 ψ2 log 2 pA 2 N q ? N ¸. (A.28)

Next, the multiplier inequality [START_REF] Wellner | Weak convergence and empirical processes: with applications to statistics[END_REF] implies that

E sup

BpF ;2δq

ˇˇˇˇ1 ? N N ÿ j"1
pf pZ j q ´f˚p Z j qqpY j ´f˚p Z j q ˇˇˇď C}η} 2,1 max k"1,...,N

E sup

BpF ;2δq

ˇˇˇˇ1 ? k k ÿ j"1
pf pZ j q ´f˚p Z j qq ˇˇˇˇ.

Using symmetrization inequality and applying Dudley's entropy integral bound, we deduce that for any k

E sup

BpF ;2δq ˇˇˇˇ1 ?

k k ÿ j"1 pf pZ j q ´f˚p Z j qq ˇˇˇˇď C ? V E ż σ k 0 log 1{2 ˆA}F 2δ } L2pΠ k q ε ˙dε ď C 1 ? V E ˆσk log 1{2 ˆeA}F 2δ } L2pΠ k q σ k ˙˙,
where F 2δ is the envelope of the class BpF; 2δq and σ According to (A.28),

Eσ 2 k ď 2δ `C2 ˜?δ c V N logpA 2 N q}F } ψ2 ł V }F } 2 ψ2 log 2 pA 2 N q N ¸.
Simple algebra now yields that

E sup

BpF ;2δq ˇˇˇˇ1 ?

N N ÿ j"1
pf pZ j q ´f˚p Z j qqpY j ´f˚p Z j q ˇˇˇď C}η} 2,1 a V logpe 2 A 2 N q ˜?δ `c V N logpA 2 N q}F } ψ2 ¸. (A.29)

Finally, combination of inequalities (A.28) and (A.29) implies that wpδq ď r ωpδq :" C ˜?δ ? V logpA 2 N qp}F } ψ2 `}η} 2,1 q ł V p}F } 2 ψ2 `}η} 2 2,1 q log 2 pA 2 N q ? N ¸, where r ωpδq is of strictly concave type, hence δ ď Cpρq V log 2 pA 2 N qp}F } 2 ψ2 `}η} 2 2,1 q N thus proving the claim.

3 )

 3 Given J P A pnq N , let s Lpf ; Jq :" 1 n ř iPJ f pX i q.Consider U-statistics of the form U N,n pz; f q "

Fig 3 :

 3 Fig 3: Algorithm 3 -evaluation of p β U N .

Fig 4 :

 4 Fig 4: Scatter plot of 630 samples from the training dataset (600 informative observations, 30 outliers),the color of the points correspond to their labels and the background color -to the predicted labels (brown region corresponds to "yellow" labels and blue -to "purple").

Fig 5 :

 5 Fig 5: Scatter plot of 600 training samples (570 informative data and 30 outliers) and the corresponding regression lines for our method, Huber's regression and regression with quadratic loss.

Fig 6 :

 6 Fig 6: Plot of the tuning parameter (x-axis) against the MSE (y-axis) obtained with Algorithm 3. The MSE was evaluated via the Monte-Carlo approximation over 500 samples of the data.

Fig 7 :

 7 Fig 7: Algorithm 4.

  (a) "Two moons" dataset [39] with outliers. (b) N " 100, no outliers (c) N " 100, with 10 outliers (d) N " 1000, no outliers (e) N " 1000, with 100 outliers

Fig 8 :

 8 Fig 8: Comparison of Algorithm 3, Algorithm 4 and standard logistic regression. The accuracy was evaluated using Monte-Carlo simulation over 300 runs.

a

  Var p pf pXqq ´ pf ˚pX qqq, ωpδq :" E sup pf qPF pδq ˇˇˇˇ1 ?

Theorem 3 . 3 .

 33 Assume that conditions of Theorem 3.1 hold. Additionally, suppose that sup f PF E 1{4 p pf pXqq ´E pf pXqqq 4 ă 8

Theorem 3 . 4 .

 34 Suppose that supf PF E 1{4 p pf pXqq ´E pf pXqqq 4 ă 8

A. 8 .

 8 sup f PF pδq ˇˇp G |J| pz; f q ´p G |J| pz; f ˚q ´E ´p G |J| pz; f q ´p G |J| pz; f ˚q¯ˇď δ r U pδ min , sq δ minuniformly for all δ ě δ min , hence the value of ε 1 should be replaced by ε 1 " δ r U pδmin,sq δmin. Proof of Lemma A.2.

2

 2 L2pΠ k q . Cauchy-Schwarz inequality, together with an elementary observation that kσ 2 k ě }F 2δ } 2 L2pΠ k q , givesE ˆσk log 1{2 ˆeA}F 2δ } L2pΠ k q σ k

Fig 12 :

 12 Fig 12: Histogram of densities of the logarithm of the MSE for the different methods (light blue corresponds to the approach of this paper (Algorithm 3), orange -to the standard least squares regression, and green -to Huber's regression).

Fig 13 :

 13 Fig 13: Comparison of Algorithms 1 and 3.

  p pf pX j qq ´E pf pXqqq converges weakly to a Gaussian limit. Next, we demonstrate that under additional assumption requiring that any f P F with small excess risk must be close to f ˚that minimizes the expected loss, p f

	1 ? N	ř N j"1

N and p f U N attain fast rates; we state the bounds only for p f N while the results for p f U N are similar, up to the change in absolute constants. Theorem 1.1 (Informal). Assume that σp , Fq ă 8. Then, for appropriately set k and ∆, Ep p f N q ď s δ `CpF, P q ˜s N 2{3 `ˆO N ˙2{3 with probability at least 1 ´e´s for all s À k. Moreover, if sup f PF E 1{4 p pf pXqq ´E pf pXqqq 4 ă 8, then Ep

  : the dataset pZ i , Y i q 1ďiďN , number of blocks k P N, step size parameter η ą 0, maximum number of iterations M , initial guess β 0 P R d , tuning parameter ∆ P R.

	Fig 1: Algorithm 1 -evaluation of p β N .
	Construct blocks G 1 , . . . , G k ;
	for all t " 0, . . . , M do
	Compute p L pkq pβtq using the Modified Weights algorithm;
	Compute ∇ β p L pkq pβtq from equation 2.3;
	Update
	β t`1 " βt ´η∇ β p L pkq pβtq.
	end for
	Output: β M `1.
							section 6.7].
	Complete version of the gradient descent algorithm used to approximate p β N (identified with the solution
	p f N of the problem (1.5)) is presented in Figure 1.
	Next, we discuss a variant of a stochastic gradient descent for approximating the "permutation-invariant"
	estimator p f U N used when the subgroup size n ą 1; in our numerical experiments (see Section B.2 for
	the numerical comparison of two approaches), this method demonstrated consistently superior per-
	formance. Below, we will identify p f U N with the vector of corresponding coefficients p β U N . Recall that
	A pnq N :" tJ : J Ď t1, . . . , N u, CardpJq " nu, and that
	p L pkq U pβq " argmin zPR	ÿ N JPA pnq	ρ ˆ?n	s Lpf β ; Jq ∆	´z	˙.	(2.4)

Input

  : the dataset pZ i , Y i q 1ďiďN , number of blocks k P N, step size parameter η ą 0, maximum number of iterations M , initial guess z 0 P R, tuning parameter ∆ P R. for all t " 0, . . . , M do Sample permutation τ uniformly at random from π N,n,k , construct blocks G 1 pτ q, . . . , G k pτ q according to (2.6);

	. Once a method for computing p L pkq U pβq is established, similar reasoning
		Fig 2: Algorithm 2 -evaluation of p L pkq U pβq.
	Compute ∇zRτ pβ, ztq " ´?n ∆	ř k j"1 ρ 1 ´?n	∆ Lpf β ;G j pτ qq´z t s	¯;
	Update
			z t`1 " zt ´η∇zRτ pβ, ztq.
	end for
	Output: z M `1.

Input

  3.Now we are ready to state the bound for the local oscillations of the process p G k p0; f q. Let

			E 1{4	´		pf pXqq ´E pf pXqq ¯4,
		f PF
	ν 4 pδq :" sup	E 1{4	ˆ	pf pXqq ´ pf ˚pX qq ´E p pf pXqq ´ pf ˚pX qqq ˙4,
		f PF pδq
	Bp , Fq :"	R 4 p , Fq σp , Fq	,
		$ ' &	r νpδq ∆	1 M∆ ,		R 4 p , Fq " 8,
	r Bpδq :"
		'
		%
	U pδ, sq :"	2 ∆	ˆ8?	2ωpδq `νpδq c	s 2	˙`32s 3 ? k	`2O ? k	.
	Moreover, if r ωpδq and r νpδq are upper bounds for ωpδq and νpδq and are of concave type, then
			r U pδ, sq :"	2 ∆	ˆcpγq r ωpδq `r νpδq c	s 2	˙`32s ? k	,	(5.17)

where cpγq ą 0 depends only on γ, is also an upper bound for U pδ, sq of strictly concave type. Moreover, define R 4 p , Fq :" sup

  2 ě 4 logp2qVar p pf pXqqq. On the other hand, if ξ " N p0, 1q, then clearly PrpZ ď |t|q ě

	Gaussian tail bound implies that
	Prp|W p pf qq| ď ∆q ě 1 ´2 exp	ˆ´1 2	∆ 2 Var p pf pXqqq	˙ě 1 2
	whenever ∆ 2|t| ? 2π e ´t2 {2 , hence
	Prp|W p pf qq| ď ∆q ě	2∆ 2πVar p pf pXqqq a	exp	ˆ´1 2	∆ 2 Var p pf pXqqq	˙ě	∆ 8πVar p pf pXqqq a
	whenever ∆ 2 ă 4 logp2qVar p pf pXqqq. Combination of two bounds yields that
	Prp|W p pf qq| ď ∆q ě	1 ? 2 2π	Var p pf pXqqq min ˜∆ a	, 2	a log 2 ¸.

2

ˆW p pf qq ∆ ˙ě Prp|W p pf qq| ď ∆q.

  Lemma 5.5) implies, together with the inequalities }ρ 1 } 8 ď 2 and |J| ą k{2, that for any

								8)
	which implies that
								Dpδq ď	νpδq ∆	.	(A.9)
	Next, observe that p G k p0; f q " 1 ? k	ř jPJ ρ 1 ´?n	p s Lj pf q´Lpf qq´z ∆	¯`1 ? k	ř jRJ ρ 1 ´?n	p s Lj pf q´Lpf qq´z ∆	¯, hence
	application of the triangle inequality yields that
	sup	ˇˇp G k p0; f q ´p G k p0; f ˚qˇď sup	|G k p0; f q ´Gk p0; f ˚q|
	f PF pδq				f PF pδq
		`c |J| k	sup f PF pδq	ˇˇp G |J| p0; f q ´p G |J| p0; f ˚q	´E ´p G |J| p0; f q ´p G |J| p0; f ˚q¯ˇ`4 O ? k	, (A.10)
	where p G |J| p0; f q :" 1 ? |J|	ř	jPJ ρ 1 ´?n	p s Lj pf q´Lpf qq´z ∆	¯. Talagrand's concentration inequality (specifically,
	the bound of

  ˚q ´Lpf

	˙ˇˇ"
	˚q
	∆
	ˇˇˇE T ˆ?n	∆ L 1 pf q ´Lpf q s	˙´ET ˆ?n	∆ L 1 pf ˚q ´Lpf ˚q s	˙ˇˇw
	here T pxq " x ´ρ1 pxq. Next, we apply Lemma 5.8 with F " T , ξ j "	pf pXj q´E pf pXj qq ∆ ? n	and η j "
	pf˚pXj q´E pf˚pXj qq ∆ ? n

  , taking supremum over f P Fpδq and recalling that ∆ " M ∆ ¨σp , Fq for M ∆ ě 1, we obtain the inequality sup Again, taking supremum over f P Fpδq and recalling that ∆ " M ∆ ¨σp , Fq for M ∆ ě 1, we deduce that sup

		f PF pδq	|G k p0; f q ´Gk p0; f ˚q| ď	?	k	νpδq ∆	1 M ∆	ď	?	k r Bpδq.	(A.13)
	On the other hand, under the assumption of existence of 4 moments, we get that
	ˇˇˇE ρ 1 ˆ?n	∆ L 1 pf q ´Lpf q s	˙´Eρ 1 ˆ?n	∆ L 1 pf ˚q ´Lpf s ˚q	˙ˇˇď
		Cpρq ? n∆	ˆVar 1{2 p pf pXqq ´ pf ˚pX qqq	ˆR2 4 p , Fq ∆ 2	∆ 3 4 p , Fq `R3	Ė1{4
											p pf pXqq ´ pf ˚pX qqq 4 n ?	∆ 3 4 p , Fq R 3	˙,
	f PF pδq

˚q ´Lpf ˚q ∆ ˙ˇˇˇď Var 1{2 p pf pXqq ´ pf ˚pX qqq σp , Fq ∆ 2 . and

  2 satisfying conditions above and such that |z 1 |, |z 2 | are as small as possible. Observe that

	and ˇˇ1 ? k	ř	jRJ ρ 1 ´?n	p s Lj pf q´Lpf qq´z ∆	¯ˇˇď 2 O ? k . Moreover,
	1 ? k	ÿ jPJ	ρ 1 ˆ?n	∆ L j pf q ´Lpf qq p s	´z	"
						1 k ?		jPJ ÿ	´ρ1 ˆ?n	∆ L j pf q ´Lpf qq p s	´z	˙´ρ 1 ˆ?n	∆ L j pf ˚q ´Lpf ˚qq p s	´z	Ė
								"	ρ 1 ˆ?n	∆ L j pf q ´Lpf qq p s	´z	˙´ρ 1 ˆ?n	∆ L j pf ˚q ´Lpf ˚qq p s	´z	˙ 1
					?	k	jPJ ÿ		´ρ1 ˆ?n	∆ L j pf ˚q ´Lpf ˚qq p s	´z	˙´Eρ 1 ˆ?n	∆ L j pf ˚q ´Lpf ˚qq p s	´z	˙1
								?	k	jPJ ÿ	ˆEρ 1 ˆ?n	∆ L j pf q ´Lpf qq p s	´z	∆ ˙´Eρ 1 ˆW p pf qq ´?nz	˙1
													?	k	ÿ jPJ	∆ Eρ 1 ˆW p pf qq ´?nz	˙.
			p G k pz; f q "	1 ? k	ÿ jPJ	ρ 1 ˆ?n	p s L j pf q ´Lpf qq ∆	´z	˙`1 ? k	ÿ jRJ	ρ 1 ˆ?n	∆ L j pf q ´Lpf qq p s	´z	˙

  and finally we will choose z 1 ă 0 such that for all f P Fpδq, Talagrand's concentration inequality[START_REF] Van De Geer | Estimation and testing under sparsity[END_REF] Corollary 16.1], together with the bound }ρ 1 } 8 ď 2, implies that for any s ą 0, |J| pz;f q ´p G |J| pz; f ˚q ´E ´p G |J| pz; f q ´p G |J| pz; f |J| pz; f q ´p G |J| pz; f ˚q ´E ´p G |J| pz; f q ´p G |J| pz; f ˚q¯ˇ`D pδqwith probability at least 1 ´2e ´s. It has been observed in (A.9) that Dpδq ď νpδq ∆ . It remains to estimate the expected supremum. Sequential application of symmetrization, contraction and desymmetrization inequalities, together with the fact that Lpρ 1 q " 1, implies thatE sup f PF pδq ˇˇp G |J| pz; f q ´p G |J| pz; f ˚q ´E ´p G |J| pz; f q ´p G |J| pz; fNext, Bernstein's inequality and Lemma 5.1 together yield that with probability at least 1 ´2e ´s, Lemma 5.3 impliies that ε 3 can be chosen as

												˚q¯ď
										ˇˇˇˇ1
				2E sup f PF pδq	a |J|	ÿ jPJ	ε j	ˆρ1 ˆ?n	∆ L j pf q ´Lpf q s	´z	˙˙´ρ 1 ˆ?n	∆ L j pf ˚q ´Lpf ˚q s	´z	˙ˇˇˇď
											4 ∆	E sup f PF pδq	ˇˇˇˇ? n a |J|	jPJ ÿ	ε j `p s L j pf q ´Lpf qq ´p s L j pf ˚q ´Lpf ˚qq	˘ˇˇˇď
												8 ? ∆ 2	E sup f PF pδq	ˇˇˇˇ1 ? N	N J ÿ j"1	´p	pf q ´ pf ˚qqpX j q ´P p pf q ´ pf ˚qq	¯ˇˇˇˇď 8 ? ∆ 2	ωpδq.
	Hence, it suffices to choose	ε 1 "	8 ? ∆	2	ωpδq	`νpδq ∆	?	s	`32 3	s ? k	.
	1 ? k 1 ? k	ÿ jPJ ÿ jPJ	´ρ1 ˆ?n ´ρ1 ˆ?n	p s L j pf q ´Lpf qq ∆ p s L j pf ˚q ´Lpf ˚qq ´z ´z ˙´ρ 1 ˆ?n ∆ ˙´Eρ 1 ˆ?n p s L j pf ˚q ´Lpf ˚qq ∆ p s L j pf ˚q ´Lpf ˚qq ´z ∆	Ė ´z ˙ḑ 2 ˆσp , f ˚q ∆ s `3s k ? ? ˙,
												" ρ 1 ˆ?n	p s L j pf q ´Lpf qq ∆	´z	˙´ρ 1 ˆ?n	p s L j pf ˚q ´Lpf ˚qq ∆	´z	˙ ¸ď ε 1
	with high probability, then ε 2 ą 0 such that ε 3 "	?	f PF pδq k sup	G f pn, ∆q.
	1 ? k Finally, we apply Lemma 6.3 of [35] with ÿ ´ρ1 ˆ?n p s L j pf ˚q ´Lpf ˚qq ∆ jPJ ε 3 satisfying ε :" ε 1 `ε2 `ε3 ´z ˙´Eρ 1 ˆ?n `2 O p s L j pf ˚q ´Lpf ˚qq ∆ ? k	´z	˙¸ď ε 2 ,
	sup f PF pδq to deduce that	ˇˇˇˇ1 ? k	ÿ jPJ	ˆEρ 1 ˆ?n z 1 "	p s L j pf q ´Lpf qq ∆ ´C r ∆ ? N ¨ˆε 1 `ε2 `ε3 ´z ˙´Eρ 1 ˆW p pf qq ´?nz ∆ ? k `2 O ˙,	˙˙ˇˇˇˇˇď	ε 3 ,
	satisfies (A
											1 ? k	ÿ jPJ	Eρ 1 ˆW p pf qq ´?nz ∆	˙ą ε 1 `ε2 `ε3	`2 O ? k	.	(A.25)
	c
	|J| k	f PF pδq sup	ˇˇp G ˚q¯ˇď
					2	"	E sup f PF pδq	ˇˇp G c	s 2	`32 3	k s ?	

thus we can set ε 2 " 2 ´σp ,f˚q ∆ ? s `3 s ? k ¯.

  2 ˆ?n s L j pf ˚q ´Lpf Clearly, as }ρ 2 } 8 ď 1, ˇˇ1 ? argument" of Lemma 5.10, it is not difficult to deduce that with probability at least 1´2e ´2s , for all δ ě δ min . Next, we will apply Bernstein's inequality to estimate the remaining term. Since ρ is convex, ρ 2 is nonnegative, moreover, it follows from Assumption 1 that ρ 2 pxq ‰ 0 for |x| ď 2, ρ 2 pxq " 1 for |x| ď 1, and }ρ 2 } 8 " 1, hence ´Eρ 2 ´?n

										˙˙1
										˚q
										∆
								?	k	jPJ ÿ	ˆρ2 ˆ?n	∆ L j pf ˚q ´Lpf s ˚q	˙´Eρ 2 ˆ?n	s L j pf ˚q ´Lpf
				k	ř	jRJ	´ρ2 ´?n	s Lj pf q´Lpf q ∆	¯´Eρ 2 ´?n	s Lj pf q´Lpf q	¯¯ˇˇˇď	2 O ? k . Next, repeating
	ˇˇˇˇ1 the "slicing sup f PF pδq k ?	jPJ ÿ	´ρ2 ˆ?n	∆ L j pf q ´Lpf q s	˙´ρ 2 ˆ?n	∆ L j pf ˚q ´Lpf ˚q s	Ė
			ˆρ2 ˆ?n	s L j pf q ´Lpf q ∆	˙´ρ 2 ˆ?n	s L j pf ˚q ´Lpf ˚q ∆	˙˙¸ˇˇˇˇˇď	Cpρq δ	r U pδ min , sq δ min
										s Lj pf q´Lpf q ∆	¯¯2	ě ´Pr ´ˇˇ? n

˚q ∆ ˙˙. uniformly s Lj pf q´Lpf q ∆

The "standard" median-of-means estimator corresponds to ρpxq " x and can be seen as a limit of p L pkq pf q when ∆ Ñ 0; this case is not covered by results of the paper, as we will require that ρ 1 is smooth and ∆ is bounded from below.

(a) M SE vs k (b) M SE vs ∆ (log-log scale)

this is only true in some neighborhood of 0, but is sufficient for our purposes

Definition..

Similar result holds if δ 1 is replaced by its analogue from Theorem 3.3.

L8pΠ N q

Acknowledgements

Stanislav Minsker gratefully acknowledges support by the National Science Foundation grant DMS-1712956.

Appendix A: Remaining proofs.

A.1. Proof of Lemma 5.6.

As ρ is sufficiently smooth, B z G k p0; f q "

´?kn ∆ Eρ 2 ˆ?n

In view of Bernstein's assumption verified above, ωpδq is bounded by

´pY j ´f pZ j qq 2 ´pY j ´f˚p Z j qq 2 ´E `pY j ´f pZ j qq 2 ´pY j ´f˚p Z j qq 2 ˘¯ˇˇˇˇˇ.

To estimate the latter quantity, we will use the approach based on the L 8 pΠ n q-covering numbers of the class F (e.g., see [START_REF] Bartlett | 1 -regularized linear regression: persistence and oracle inequalities[END_REF]). We will also set BpF; τ q :" tf P F : }f ´f˚}

It is easy to see that pY ´f pXqq 2 ´pY ´f˚p Xqq 2 " pf pXq ´f˚p Xqq 2 `2pf pXq ´f˚p Xqqpf ˚pX q ´Y q, hence wpδq ď E sup BpF ;2δq ˇˇˇˇ1 ?

pf pZ j q ´f˚p Z j qq 2 ´Epf pZ j q ´f˚p Z j qq 2 ˇˇˇ2

E sup

BpF ;2δq ˇˇˇˇ1 ?

pf pZ j q ´f˚p Z j qqpY j ´f˚p Z j q ˇˇˇˇ. (A.26)

We will estimate the two terms separately. By assumption, the covering numbers of the class F satisfy the bound

for some constants A ě 1, V ě 1 and all ε ą 0. We apply bound of Lemma 5.4 to the first term in (A. [START_REF] Lecué | Optimal rates of aggregation in classification under low noise assumption[END_REF] to get that

pf pZ j q ´f˚p Z j qq 2 ´Epf pZ j q ´f˚p Z j qq Moreover, for any f, g P F,

where log `pxq :" maxplog x, 0q. It yields that

We present additional sresults of numerical experiments omitted in the main text.

B.1. Application to the "Communities and Crime" data.

We compare performance of our methods with the ordinary least squares regression applied to a real dataset. The dataset we chose is called "Communities and Crime Unnormalized Data Set" and is available through the UCI Machine Learning Repository. These data contain 2215 observations from a census and law enforcement records. The task we devised was to predict the crime activity (represented as the count of incidents) using the following features: the population of the area, the per capita income, the median family income, the number of vacant houses, and the land area. The choice of this specific dataset was motivated by the fact that it likely contains a non-negligible number of outliers due to the nature of the features and the fact that the data have not been preprocessed, hence the advantages of proposed approach could be highlighted. Figure 9 presents a pairplot of the dataset; specifically, a pairplot shows all the different scatter plots of one feature versus another (hence, the diagonal consists of the histograms of an individual feature). Such a pairplot offers a visual confirmation of the fact that the data likely contains outliers. We studied the dependency of the MSE with k. Similarly to Figure 6a, we plotted the MSE as a function of k (figure 10). Cross-validation is a common way to assess the performance of a machine learning algorithm. However, cross-validation is not robust when the method itself is not robust (as it is the case here with regression with quadratic loss). For our purposes, we slightly changed the way we approach cross validation. Namely, we still partition the data into m parts used separately for training and testing, however, once we obtain the m scores associated with the m folds, we evaluate the median of these scores instead of the mean. The rationale behind this approach is that if at least half of the folds do not contain outliers, the results of cross-validation will be robust. To use this approach, we choose m, the number of folds, to be large (in the example above, m " 500). Input: the dataset pX i , Y i q 1ďiďN . Construct the blocks G 1 , . . . , Gm, partition of t1, . . . , N u. for all j " 1, . . . , m do Train p f on the dataset pX l , Y l q, l P Ť i‰j G i . Compute the test MSE Score j " 1 |G j | ř lPG j p f pX l q ´Yl q 2 end for Output: Median pScore 1 , . . . , Scoremq.

We compared the three algorithms using robust cross-validation with median described above Our method (based on Algorithm 3) yields MSE of » e 4.2 while the MSE for the ordinary least squares regression is of order e 22.1 , while the Huber Regression leads to MSE » e 8.9 . The empirical density of the logarithm of the MSE over 500 folds is shown in Figure 12.

B.2. Comparison of Algorithm 1 and Algorithm 3.

We present a numerical evidence that the permutation-invariant estimator p f U N is superior to the the estimator p f N based on fixed partition of the dataset. Evaluation was performed for the regression task where the data contained outliers of type (a), as described in Section 2.3. Average MSE was evaluated over 500 repetitions of the experiment, and the standard deviation of the MSE was also recored. Results are presented in Figure 13 and confirm the significant improvements achieved by Algorithm 3 over Algorithm 1. We set k " 71 and ∆ " 1 for both algorithms.