Guillaume Maillard
email: guillaume.maillard@u-psud.fr

Sylvain Arlot
email: sylvain.arlot@u-psud.fr

Matthieu Lerasle
email: matthieu.lerasle@u-psud.fr

Aggregated Hold-Out

Keywords: cross-validation, aggregation, bagging, hyperparameter selection, regularized kernel regression

Aggregated hold-out (Agghoo) is a method which averages learning rules selected by hold-out (that is, cross-validation with a single split). We provide the first theoretical guarantees on Agghoo, ensuring that it can be used safely: Agghoo performs at worst like the hold-out when the risk is convex. The same holds true in classification with the 0-1 risk, with an additional constant factor. For the hold-out, oracle inequalities are known for bounded losses, as in binary classification. We show that similar results can be proved, under appropriate assumptions, for other risk-minimization problems. In particular, we obtain an oracle inequality for regularized kernel regression with a Lipschitz loss, without requiring that the Y variable or the regressors be bounded. Numerical experiments show that aggregation brings a significant improvement over the hold-out and that Agghoo is competitive with cross-validation.

Introduction

The problem of choosing from data among a family of learning rules is central to machine learning. There is typically a variety of rules which can be applied to a given problem -for instance, support vector machines, neural networks or random forests. Moreover, most machine learning rules depend on hyperparameters which have a strong impact on the final performance of the algorithm. For instance, k-nearest-neighbors rules [START_REF] Biau | Lectures on the Nearest Neighbor Method[END_REF] depend on the number k of neighbors. A second example, among many others, is given by regularized empirical risk minimization rules, such as support vector machines [START_REF] Steinwart | Support vector machines[END_REF] or the Lasso [START_REF] Tibshirani | Regression shrinkage and selection via the lasso[END_REF][START_REF] Bühlmann | Statistics for high-dimensional data[END_REF], which all depend on some regularization parameter. A related problem is model selection [START_REF] Burnham | Model Selection and Multimodel Inference[END_REF][START_REF] Massart | Concentration Inequalities and Model Selection[END_REF], where one has to choose among a family of candidate models.

In supervised learning, cross-validation (CV) is a general, efficient and classical answer to the problem of selecting a learning rule [START_REF] Arlot | A survey of cross-validation procedures for model selection[END_REF]. It relies on the idea of splitting data into a training sample -used for training a predictor with each rule in competition-and a validation sample -used for assessing the performance of each predictor. This leads to an estimator of the risk -the hold-out estimator when data are split once, the CV estimator when an average is taken over several data splits-, which can be minimized for selecting among a family of competing rules.

A completely different strategy, called aggregation, is to combine the predictors obtained with all candidates [START_REF] Nemirovski | Topics in Non-parametric Statistics[END_REF][START_REF] Yang | Adaptive regression by mixing[END_REF][START_REF] Alexandre | Optimal aggregation of classifiers in statistical learning[END_REF]. Aggregation is the key step of ensemble methods [START_REF] Thomas | Ensemble methods in machine learning[END_REF], among which we can mention bagging [START_REF] Breiman | Bagging predictors[END_REF], AdaBoost [START_REF] Freund | A decision-theoretic generalization of on-line learning and an application to boosting[END_REF] and random forests [START_REF] Breiman | Random forests[END_REF][START_REF] Biau | A random forest guided tour[END_REF]. A major interest of aggregation is that it builds a learning rule that may not belong to the family of rules in competition. Therefore, it sometimes has a smaller risk than the best of all rules [27, Table 1]. In contrast, cross-validation, which selects only one candidate, cannot outperform the best rule in the family.

Aggregated hold-out (Agghoo) This paper studies a procedure mixing cross-validation and aggregation ideas, that we call aggregated hold-out (Agghoo). Data are split several times; for each split, the hold-out selects one predictor; then, the predictors obtained with the different splits are aggregated. A formal definition is provided in Section 3. This procedure is as general as cross-validation and it has roughly the same computational cost (see Section 3.3). Agghoo is already popular among practicioners, and has appeared in the neuro-imaging literature [START_REF] Hoyos-Idrobo | Improving sparse recovery on structured images with bagged clustering[END_REF][START_REF] Varoquaux | Assessing and tuning brain decoders: Cross-validation, caveats, and guidelines[END_REF] under the name "CV + averaging". Yet, to the best of our knowledge, existing experimental studies do not give any indication on how to choose Agghoo's parameters. No general mathematical definition has been provided, so it is unclear how to generalize Agghoo beyond a given article's setting. Theoretical guarantees on Agghoo have not been established yet, to the best of our knowledge. The closest results we found study other procedures, called ACV [START_REF] Jung | A K-fold averaging cross-validation procedure[END_REF], EKCV [START_REF] Jung | Efficient tuning parameter selection by cross-validated score in high dimensional models[END_REF], or "bagged cross-validation" [START_REF] Hall | Reducing variability of crossvalidation for smoothing-parameter choice[END_REF], and they do not prove oracle inequalities. We explain in Section 3.2 why Agghoo should be preferred to these procedures in the general prediction setting.

Because of the aggregation step, Agghoo is an ensemble method, and like bagging, it combines resampling with aggregation. The application of bagging to the hold-out was first suggested by Breiman [START_REF] Breiman | Bagging predictors[END_REF] as a way to com-bine pruning and bagging of CART trees. The combination of bagging and cross-validation has been studied numerically by [START_REF] Petersen | Cross-validated bagged learning[END_REF]. A major difference with Agghoo is that the training and validation samples are not independent with bagging, which uses sampling with replacement. If the bootstrap is replaced by subsampling, bagging becomes subagging [START_REF] Bühlmann | Analyzing bagging[END_REF], and its combination with cross-validation yields a procedure much closer to Agghoo, but still different, see Section 3.2. Overall, previous results on bagging or subagging do not apply to Agghoo; new developments are required.

Contributions In this article, Agghoo's performance is studied both theoretically and experimentally. We consider Agghoo from a prediction point of view. Performance is measured by a risk functional. On the theoretical side, the aim is to show that the risk of Agghoo's final predictor is as low as the risk of the optimal rule among the given collection. This is known as an oracle inequality. By a convexity argument, Agghoo always improves on the hold-out, provided that the risk is convex. Hence, Agghoo can safely replace the hold-out in any application where this hypothesis holds true. Another consequence is that oracle inequalities for Agghoo can be deduced from oracle inequalities for the hold-out.

This kind of result on the hold-out has already appeared in the literature: for example, Massart [START_REF] Massart | Concentration Inequalities and Model Selection[END_REF]Corollary 8.8] proves a general theorem under an abstract noise assumption; more explicit results have been obtained in specific settings such as least-squares regression [START_REF] Györfi | A Distribution-Free Theory of Nonparametric Regression[END_REF]Theorem 7.1] or maximum-likelihood density estimation [START_REF] Massart | Concentration Inequalities and Model Selection[END_REF]Theorem 8.9]. A review on cross-validation -which includes the hold-out-can be found in [START_REF] Arlot | A survey of cross-validation procedures for model selection[END_REF].

Most existing theoretical guarantees on the hold-out have a limitation: they assume that the loss function is uniformly bounded. In regression, the variable Y and the regressors are also usually assumed to be bounded, which excludes some standard least-squares estimators. Even when the boundedness assumption holds true, constants arising from general bounds may be of the wrong order of magnitude, leading to vacuous results. By replacing uniform supremum bounds by local ones, we are able to relax these hypotheses in a general setting (Theorem A.3). This enables us to prove an oracle inequality for the hold-out and Agghoo in regularized kernel regression with a general Lipschitz loss (Theorem 4.3). This oracle inequality allows for instance to recover state-of-the-art convergence rates in median regression without knowing the regularity of the regression function (adaptivity), both in the general case and, for small enough regularity, also in the specific setting of [START_REF] Eberts | Optimal regression rates for SVMs using gaussian kernels[END_REF]. To illustrate the implications of Theorem 4.3, we also apply it to ε-regression (Corollary 4.4). To the best of our knowledge, all these oracle inequalities are new, even for the hold-out.

A limitation of Agghoo is that it does not cover settings where averaging does not make sense, such as classification. In classification with the 0-1 loss, the natural way to aggregate classifiers is to take a majority vote among them. This yields a procedure which we call Majhoo. Using existing theory for the hold-out in classification, we prove that Majhoo satisfies a general, margin-adaptive oracle inequality (Theorem 4.5) under Tsybakov's margin assumption [START_REF] Mammen | Smooth discrimination analysis[END_REF].

All our oracle inequalities are valid for any size of the aggregation ensemble. Qualitatively, since bagging and subagging are well-known for their stabilizing effects [START_REF] Breiman | Bagging predictors[END_REF][START_REF] Bühlmann | Analyzing bagging[END_REF], we can expect Agghoo to behave similarly. In particular, large ensembles should improve much the prediction performance of CV when the hold-out selected predictor is unstable.

For further insights into Agghoo and Majhoo, we conduct in Section 5 a numerical study on simulated datasets. Its results confirm our intuition: in all settings considered, Agghoo and Majhoo actually perform much better than the hold-out, and even better than CV, provided their parameters are well-chosen. When choosing the number of neighbors for k-nearest neighbors, the prediction performance of Majhoo is much better than the one of CV, which illustrates the strong interest of using Agghoo/Majhoo when learning rules are "unstable". In support vector regression, Agghoo can even perform better than the oracle, an improvement made possible by aggregation, that cannot be matched by any hyperparameter selection rule. Based upon our experiments, we also give in Section 5 some guidelines for choosing Agghoo's parameters: the training set size and the number of data splits.

The remaining of the article is structured as follows. In Section 2, we introduce the general statistical setting. In Section 3, we give a formal definition of Agghoo. In Section 4, we state the main theoretical results. In Section 5, we present our numerical experiments and discuss the results. Finally, in Section 6, we draw some qualitative conclusions about Agghoo. The proofs are postponed to the Appendix.

Setting and Definitions

We consider a general statistical learning setting, following the book by Massart [START_REF] Massart | Concentration Inequalities and Model Selection[END_REF].

Risk minimization

The goal is to minimize over a set S a risk functional L : S → R ∪ {+∞}. The set S may be infinite dimensional for non-parametric problems. Assume that L attains its minimum over S at a point s, called a Bayes element. Then the excess risk of any t ∈ S is the nonnegative quantity ℓ(s, t) = L(t) -L(s) .

Suppose that the risk can be written as an expectation over an unknown probability distribution:

L(t) = E γ(t, ξ) ,
for a contrast function γ : S × Ξ → R and a random variable ξ with values in some set Ξ and unknown distribution P , such that

∀t ∈ S, ξ ∈ Ξ → γ(t, ξ) is P -measurable .
The statistical learning problem is to use data D n = {ξ 1 , ..., ξ n }, where ξ 1 , ..., ξ n are independent and identically distributed (i.i.d.), with common distribution P , to find an approximate minimizer for L. The quality of this approximation is measured by the excess risk.

Examples

Supervised learning aims at predicting a quantity of interest Y ∈ Y using explanatory variables X ∈ X . The statistician observes pairs (X 1 , Y 1 ), . . . (X n , Y n ), so that Ξ = X × Y, and seeks a predictor in S = {t : X → Y : t measurable}. The contrast function is defined by γ(t, (x, y)) = g(t(x), y) for some loss function g : Y × Y → R. Here, g(y ′ , y) measures the loss incurred by predicting y ′ instead of the observed value y. Two classical supervised learning problems are classification and regression, which we detail below.

Example 2.1 (Classification)

In classification Y belongs to a finite set of labels Y = {0, . . . , M }. We wish to correctly label any new data point X, and the risk is the probability of error :

∀t ∈ S, L(t) = P t(X) = Y ,
which corresponds to the loss function g(y ′ , y) = I{y ′ = y}. Classification with convex losses (such as the hinge loss or logistic loss) can also be described using the formalism of Section 2.1.

Example 2.2 (Regression)

In regression we wish to predict a continuous variable Y ∈ Y = R d . The error made by predicting y ′ instead of y is measured by the loss function defined by g(y ′ , y) = φ( y ′y ) where φ : R + → R + is nondecreasing and convex. Some typical choices are φ(x) = x 2 (least squares), φ(x) = x (median regression) or φ(x) = (|x|ε) + (Vapnik's ε-insensitive loss, leading to ε-regression). The risk is given by

L(t) = E φ Y -t(X) .
If φ is strictly convex, the minimizer of L over S is a unique function, up to modification on a set of probability 0 under the distribution of X.

In some applications, such as robust regression, it is of interest to define s and ℓ(s, t) even when φ( Y ) / ∈ L1 . This is possible for Lipschitz contrasts, by the following remark.

Remark 2.1 When φ is convex and increasing (as in Example 2.2), and also Lipschitz-continuous, it is always possible to define

s : x → argmin u∈R E φ( Y -u ) -φ( Y ) X = x .
When s ∈ L 1 (X), it is a Bayes element for the loss function g(y ′ , y) = φ( y ′y )φ( y ). Whenever φ( Y ) ∈ L 1 , this loss yields the same Bayes element and excess risk as in Example 2.2.

This small adjustment to the general definition allows to consider Example 2.2 when φ( Ys(X) ) is not integrable, for example when Y = s(X)+ η, where η is independent from X and follows a multivariate Cauchy distribution with location parameter 0. Some density estimation problems, such as maximum likelihood or leastsquares density estimation, also fit the formalism of Section 2.1, see [START_REF] Massart | Concentration Inequalities and Model Selection[END_REF].

Learning rules and estimator ensembles

Statistical procedures use data to compute an element of S which approximately minimizes L. Since Agghoo uses subsampling, we require learning rules to accept as input datasets of any size. Therefore, we define a learning rule to be a function which maps any dataset to an element of S.

Definition 2.1 A dataset D n of length n is a finite i.i.d sequence (ξ i ) 1 i n of Ξ-valued random variables with common distribution P . A learning rule A is a measurable function 1 A : ∞ n=1 Ξ n → S .
In the risk minimization setting, A should be chosen so as to minimize

L(A(D n )).
A generic situation is when a family (A m ) m∈M of learning rules is given, so that we have to select one of them (estimator selection), or to combine their outputs (estimator aggregation). For instance, when X is a metric space, we can consider the family (A NN k ) k 1 of nearest-neighbors classifiers -where k is the number of neighbors-, or, for a given kernel on X , the family (A SVM λ ) λ∈[0,+∞) of support vector machine classifiers -where λ is the regularization parameter. Not all rules in such families perform well on a given dataset. Bad rules should be avoided when selecting the hyperparameter, or be given small weights if the outputs are combined in a weighted average. This requires a data-adaptive procedure, as the right choice of rule in general depends on the unknown distribution P .

Aggregation and parameter selection methods aim to resolve this problem, as described in the next section.

3 Cross-Validation and Aggregated Hold-Out (Agghoo)

This section recalls the definition of cross-validation for estimator selection, and introduces a new procedure called aggregated hold-out (Agghoo). For more details and references on cross-validation, we refer the reader to the survey by Arlot and Celisse [START_REF] Arlot | A survey of cross-validation procedures for model selection[END_REF].

Background: cross-validation

Cross-validation uses subsampling and the empirical risk. We introduce first some notation.

Definition 3.1 (Empirical risk) For any dataset D n = (ξ i ) 1 i n and any t ∈ S, the empirical risk of t over D n is defined by

P n γ(t, •) = 1 n n i=1 γ(t, ξ i ) .
For any nonempty subset T ⊂ {1, . . . , n}, let also

D T n = (ξ i ) i∈T
be the subsample of D n indexed by T , and define the associated empirical risk by

∀t ∈ S, P T n γ(t, •) = 1 |T | i∈T γ(t, ξ i ) .
The most classical estimator selection procedure is to hold out some data to calculate the empirical risk of each estimator, and then select the estimator with the lowest empirical risk. This ensures that the data used to evaluate the risk are independent from the training data used to compute the learning rules.

Definition 3.2 (Hold-out) For any dataset D n and any subset T ⊂ {1, . . . , n}, the associated hold-out risk estimator of a learning rule A is defined by

HO T (A, D n ) = P T c n γ A(D T n ), • .
Given a collection of learning rules (A m ) m∈M , the hold-out procedure selects

m ho T (D n ) ∈ argmin m∈M HO T (A m , D n ) ,
measurably with respect to D n . The overall learning rule is then given by

f ho T (A m ) m∈M , D n = A m ho T (Dn) (D T n ) .
Hold-out depends on the arbitrary choice of a training set T , and is known to be quite unstable, despite its good theoretical properties [22, Section 8.5.1]. Therefore, practicioners often prefer to use cross-validation instead, which considers several training sets. Definition 3.3 (Cross-validation) Let D n denote a dataset. Let T denote a collection of nonempty subsets of {1, . . . , n}. The associated crossvalidation risk estimator of a learning rule A is defined by

CV T (A, D n ) = 1 |T | T ∈T HO T (A, D n ) .
The cross-validation procedure then selects

m cv T (D n ) ∈ argmin m∈M CV T (A m , D n ) .
The final predictor obtained through this procedure is

f cv T (A m ) m∈M , D n = A m cv T (Dn) (D n ) .
Depending on how T is chosen, this can lead to leave-one-out, leave-p-out, V -fold cross-validation or Monte-Carlo cross-validation, among others [START_REF] Arlot | A survey of cross-validation procedures for model selection[END_REF]. In the following, we omit some of the arguments A, D n which appear in Definitions 3.2 and 3.3, when they are clear from context. For example, we often write HO

T (A) , m ho T , f ho T instead of HO T (A, D n ) , m ho T (D n ), f ho T (A m ) m∈M , D n (respectively).

Aggregated hold-out (Agghoo) estimators

In this paper, we study another way to improve on the stability of holdout selection, by aggregating the predictors f ho T obtained by the hold-out procedure applied repeatedly with different training sets T ∈ T . When S is convex (e.g., regression), aggregated hold-out (Agghoo) consists in averaging them. Definition 3.4 (Agghoo) Assume that S is a convex set. Let (A m ) m∈M denote a collection of learning rules, D n a dataset, and T a collection of subsets of {1, . . . , n}. Using the notation of Definition 3.2, the associated Agghoo estimator is defined by

f ag T (A m ) m∈M , D n = 1 |T | T ∈T f ho T (A m ) m∈M , D n .
In the classification framework, as seen in Example 2.1, S = {f : X → {0, . . . , M }} which is not convex. However, there is still a natural way to aggregate several classifiers, by taking a majority vote. Definition 3.5 (Majhoo) Let Y = {0, . . . , M } be the set of labels. Given a collection of learning rules (A m ) m∈M , a dataset D n and a collection T of subsets of {1, . . . , n}, the majority hold-out (Majhoo) classifier is any measurable f mv T (A m ) m∈M , D n : X → Y such that, using the notation f ho T introduced in Definition 3.2, for all x ∈ X ,

f mv T (A m ) m∈M , D n (x) ∈ argmax j∈Y T ∈ T f ho T (A m ) m∈M , D n (x) = j .
In most situations, it is clear how hold-out rules should be aggregated and there is no ambiguity in discussing hold-out aggregation. However, there is an important exception where both Agghoo and Majhoo can be used. with φ : R → R convex [START_REF] Boucheron | Theory of classification: a survey of some recent advances[END_REF]. Then, given a family of S conv -valued learning rules A m m∈M , one can either apply Agghoo to the surrogate problem and get I f ag T ((Am) m∈M ,Dn) 0 , or apply Majhoo to the binary classification problem and get

f mv T I Am(•) 0 m∈M , D n .
In the rest of this section, we focus on Agghoo, though much of the following discussion applies also to Majhoo.

Compared to cross-validation rules (Definition 3.3), Agghoo reverses the order between aggregation (majority vote or averaging) and minimization of the risk estimator: instead of averaging hold-out risk estimators before selecting the hyperparameter, the selection step is made first to produce hold-out predictors f ho T T ∈T (given by Definition 3.2) and then an average is taken.

Related procedures

To the best of our knowledge, Agghoo has not been studied theoretically before, though it is used in applications [START_REF] Hoyos-Idrobo | Improving sparse recovery on structured images with bagged clustering[END_REF][START_REF] Varoquaux | Assessing and tuning brain decoders: Cross-validation, caveats, and guidelines[END_REF], under the name "CV + averaging" in [START_REF] Varoquaux | Assessing and tuning brain decoders: Cross-validation, caveats, and guidelines[END_REF]. According to [START_REF] Varoquaux | Assessing and tuning brain decoders: Cross-validation, caveats, and guidelines[END_REF], Agghoo is commonly used by the machine learning community thanks to the Scikit-learn library [START_REF] Pedregosa | Scikit-learn: machine learning in Python[END_REF].

A closely related procedure is "K-fold averaging cross-validation" (ACV), proposed by [START_REF] Jung | A K-fold averaging cross-validation procedure[END_REF] for linear regression. With our general notation, ACV corresponds to averaging the A m T ho (D n ), which are "retrained" on the whole dataset, while Agghoo averages the A m T ho (D T n ). An advantage of averaging the rules A m T ho (D T n ) is that they have been selected for their good performance on the validation set T c , unlike the A m T ho (D n ) whose performance has not been assessed on independent data. Furthermore, similarly to bagging, using several distinct training sets may result in improvements for unstable methods through a reduction in variance. Note finally that the theoretical results of [START_REF] Jung | A K-fold averaging cross-validation procedure[END_REF] on ACV are limited to a specific setting, and much weaker than an oracle inequality.

A second family of related procedures is averaging the chosen parameters m ho T T ∈T , contrary to Agghoo which averages the chosen prediction rules. This leads to different procedures for learning rules that are not linear functions of their parameters. This idea has been put forward under the name "bagged cross-validation" (BCV) [START_REF] Hall | Reducing variability of crossvalidation for smoothing-parameter choice[END_REF] -with numerical and theoretical results in the case of bandwidth choice in kernel density estimation-, and under the name "efficient K-fold cross-validation" (EKCV) [START_REF] Jung | Efficient tuning parameter selection by cross-validated score in high dimensional models[END_REF] for the choice of a regularization parameter in high-dimensional regression -with numerical results only. Unlike Agghoo, which only depends on the set {A m | m ∈ M} of learning rules, EKCV and BCV depend on the parametrization m → A m . Sometimes, the most natural parametrization does not allow the use of such procedures: for example, model dimensions are integers, and averaging them does not make sense. In contrast, in regression, it is always possible to average the real-valued functions A m (D nt ) ∈ S.

Even when all procedures are applicable, averaging rules is generally safer than averaging hyperparameters. Often in regression, the risk L is known to be convex over S, so given t 1 , . . . , t V ∈ S,

L 1 V i=1 t i 1 V V i=1 L(t i ) .
Hence, averaging regressors (Agghoo) always improves performance compared to selecting a single t i at random (hold-out). On the other hand, if (t θ ) θ∈Θ is a family of elements of S parametrized by a convex set Θ, there is no guarantee in general that the function θ → L(t θ ) is convex over Θ. So, for some θ 1 , . . . , θ V ∈ Θ, it may happen that

L t 1 V V i=1 θ i 1 V V i=1 L(t θ i ) .
In such a case, it is better to choose one parameter at random (hold-out) that to average them (EKCV or BCV).

A third family of related procedures is bagging or subagging applied to hold-out selection

D n → f ho T ((A m ) m∈M , D n ).
The bagging case has been studied numerically by [START_REF] Petersen | Cross-validated bagged learning[END_REF], but clearly differs from Agghoo since it relies on bootstrap resamples, in which the original data can appear several times. Subagging -which is not explicitly studied in the literature, to the best of our knowledge-is closer to Agghoo, but there is still a slight difference. When applying subagging to the hold-out, the sample is divided into three parts: the training part of the bagging subsample, the validation part of the bagging subsample, and the data not in the bagging subsample. With Agghoo, the sample is only divided into two parts.

Computational complexity

In general, for a given value of V = |T |, both Agghoo ( f ag T ) and CV ( f cv T ) must compute V hold-out risk estimators over all values of m ∈ M. Let C ho (M, n t , n v ) be the average computational complexity of the hold-out, with a training dataset of size n t and validation dataset of size n v . Then the overall complexity of risk estimation is of order V × C ho (M, n t , n v ) for both Agghoo and CV. Next, CV must average V risk vectors of length |M| and find a single minimum, while Agghoo computes V minima over m ∈ M; these operations have similar complexity, of order V ×|M|. Thus, computing the ensemble aggregated by Agghoo takes about as much time as selecting a learning rule using cross-validation.

A potential difference occurs when evaluating Agghoo and CV on new data. If there is no fast way to perform aggregation at training time, it is always possible to evaluate each predictor in the ensemble on the new data, and to average the results; then, Agghoo is slower than CV by a factor of order V at test time.

Theoretical results

The purpose of Agghoo is to construct an estimator whose risk is as small as possible, compared to the (unknown) best rule in the class (A m ) m∈M . This is guaranteed theoretically by proving "oracle inequalities" of the form

E ℓ(s, f ag T ) CE inf m∈M ℓ s, A m (D n ) + ε n , (1)
with ε n negligible compared to the oracle excess risk E[inf m∈M ℓ(s, A m (D nt ))] and C close to 1. Equation ( 1) then implies that Agghoo performs as well as the best choice of m ∈ M, up to the constant C. In the following, we actually prove slightly weaker inequalities that are more natural in our setting. By definition, Agghoo is an average of predictors chosen by hold-out over the collection (A m ) m∈M . Therefore, when the risk is convex, an oracle inequality (1) can be deduced from an oracle inequality for the hold-out, provided that there exists an integer n t ∈ {1, . . . , n -1} such that

T is independent from D n and ∀T ∈ T , |T | = n t . (2)
We make this assumption in the rest of the article. Most cross-validation methods satisfy hypothesis (2), including leave-p-out, V -fold cross-validation (with nn t = n v = n/V ) and Monte-Carlo cross-validation [START_REF] Arlot | A survey of cross-validation procedures for model selection[END_REF].

In the remainder of this section, we introduce the RKHS setting of interest, and prove an oracle inequality for Agghoo without changing the standard estimators or requiring Y to be bounded.

Agghoo in regularized kernel regression

Kernel methods such as support vector machines, kernel least squares or ε-regression use a kernel function to map the data X i into an infinitedimensional function space, more specifically a reproducing kernel Hilbert space (RKHS) [START_REF] Scholkopf | Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond[END_REF][START_REF] Steinwart | Support vector machines[END_REF]. We consider in this section regularized empirical risk minimization using a training loss function c, with a penalty proportional to the square norm of the RKHS, to solve the supervised learning problem (defined in Section 2.2) with loss function g. Hence, the contrast γ can be written γ(t, (x, y)) = g(t(x), y) := (g • t)(x, y). We assume that g and c are convex in their first argument. Definition 4.1 (Regularized kernel estimator) Let c : R × R → R be convex in its first argument, and let K : X × X → R be a positive-definite kernel function. Given λ > 0 and training data (X i , Y i ) 1 i nt , define the regularized kernel estimator as

A λ (D nt ) = argmin t∈H P nt (c • t) + λ t 2 H ,
where H is the reproducing kernel Hilbert space induced by K. By the representer theorem, A λ can be computed explicitly:

A λ (D nt )(x) = nt j=1 θ λ,j K(X j , x)
where

θ λ = argmin θ∈R n t    1 n t nt i=1 c   nt j=1 θ j K(X j , X i ), Y i   + λ nt i=1 nt j=1 θ i θ j K(X i , X j )    . (3)
The loss function c is used to measure the accuracy of the fit on the training data: for example, taking c : (u, y) → (1uy) + (the hinge loss) in Definition 4.1 corresponds to svm. The loss function g used for risk evaluation may or may not be equal to c. For example, in classification, the 0-1 loss often cannot be used for training for computational reasons, hence a surrogate convex loss, such as the hinge loss, is used instead (see Remark 3.1), but there is no reason to use the hinge loss for risk estimation and hyperparameter selection.

In Definition 4.1, the hyperparameter of interest is λ (we assume that K is fixed). We show below some guarantees on Agghoo's performance when it is applied to a finite subfamily (A λ ) λ∈Λ of the one defined by Definition 4.1. We first state some useful assumptions.

Hypothesis Comp C (g, c): L c : t → P (c • t) and L g have a common minimum s ∈ argmin t∈S L c (t) ∩ argmin t∈S L g (t) and for any t ∈ S, L c (t) -L c (s) C [L g (t) -L g (s)].
Note that Comp 1 (g, c) is always satisfied when g = c. When g = c, some hypothesis relating c and g is necessary anyway for Definition 4.1 to be of interest, if only to ensure consistency (asymptotic minimization of the risk) for some sequence of hyperparameters (λ n ) n∈N .

In addition, some information about the evaluation loss g helps to obtain an oracle inequality (1) with a smaller remainder term ε n .

Hypothesis SC ρ,ν : Let ℓ X (u) = E[g(u, Y )|X] -inf v∈R E[g(v, Y )|X]. The triple (g, X, Y ) satisfies SC ρ,ν if and only if, for any u, v ∈ R, E[(g(u, Y ) -g(v, Y )) 2 |X] ρ ∨ (ν|u -v|) [ℓ X (u) + ℓ X (v)]. (4)
For example, in the case of median regression, that is, g(u, y) = |u -y|, hypothesis SC ρ,ν holds whenever there is a uniform lower bound on the concentration of Y around s(X), as shown by the following proposition.

Proposition 4.2 Let g(u, y) = |u -y| for all u, y ∈ R. For any x ∈ X , let F x be the conditional cumulative distribution function of Y knowing X = x.
Assume that, for any x ∈ X , F x is continuous with a unique median s(x) and that there exists a(x) > 0, b(x) > 0 such that

∀u ∈ R, F x (u) -F x s(x) a(x) u -s(x) ∧ b(x) . (5)
For instance, this holds true if dFx (1θ)E ℓ s, f ag

T (1 + θ)E min λ∈Λ ℓ s, A λ (D nt ) + max 18ρ log n v |Λ| θn v , b 1 log 2 n v |Λ| θ 3 λ m n 2 v , b 2 log 3 2 n v |Λ| θλ m n v √ n t , (6)
where b 1 , b 2 do not depend on n v , n t , λ m or θ but only on κ, L, ν and C.

Theorem 4.3 is proved in Appendix B as a consequence of a result valid in the general framework of Section 2.1 (Theorem A.3). It shows that f ag T satisfies an oracle inequality of the form (1), with A λ (D nt ) instead of A λ (D n ) on the right-hand side of the inequality. The fact that D nt appears in the bound instead of D n is a limitation of our result, but it is natural since predictors aggregated by Agghoo are only trained on part of the data. In most cases, it can be expected that ℓ(s,

A λ (D nt )) is close to ℓ(s, A λ (D n )) whenever nt n is close to 1.
The assumption that K is bounded is mild. For instance, popular kernels such as Gaussian kernels, (x, x ′ ) → exp[-xx ′ 2 /(2h 2 )] for some h > 0, or Laplace kernels, (x, x ′ ) → exp(-xx ′ /h) for some h > 0, are bounded by κ = 1.

Taking |T | = 1 in Theorem 4.3 yields a new oracle inequality for the hold-out. Oracle inequalities for the hold-out have already been proved in a variety of settings (see [START_REF] Arlot | A survey of cross-validation procedures for model selection[END_REF] for a review), and used to obtain adaptive rates in regularized kernel regression [START_REF] Steinwart | Support vector machines[END_REF]. However, this work has mostly been accomplished under the assumption that the contrast γ (A λ (D n ), (X, Y )) is bounded uniformly (in n, D n and λ ∈ Λ) by a constant. If this constant increases with n, bounds obtained in this manner may worsen considerably. As many "natural" regression procedures -including regularized kernel regression (Definition 4.1)-fail to satisfy such bounds, some theoreticians introduce "truncated" versions of standard procedures [START_REF] Steinwart | Support vector machines[END_REF], but truncation has no basis in practice. Theorem 4.3 avoids these complications.

In order to be satisfactory, Theorem 4.3 should prove that Agghoo performs asymptotically as well as the best choice of λ ∈ Λ, at least for reasonable choices of Λ. This is the case whenever the maximum in Equation ( 6) is negligible with respect to the oracle excess risk E[min λ∈Λ ℓ(s, A λ (D nt ))] as n → +∞. This depends on the range [λ m ; +∞) in which the hold out is allowed to search for the optimal λ. On the one hand, it is desirable that this interval be wide enough to contain the true optimal value. On the other hand, if λ m = 0, then inequality (6) becomes vacuous. We now provide precise examples where Theorem 4.3 applies with a remainder term in Equation ( 6) that is negligible relative to the oracle excess risk.

Take the example of median regression, in which c(u, y) = g(u, y) = |u -y|. Then Comp 1 (g, c) holds trivially. Make also the same assumptions as in Proposition 4.2, which ensures that SC ρ,ν holds for some finite values of ρ and ν. Theorem 4.3 therefore applies as long as the kernel K is bounded and λ m > 0. Choose n v = n t = n 2 and Λ of cardinality at most polynomial in n (which is sufficient in theory and in practice). Then [29, Theorem 9.6] proves the consistency of A λn (D n ) as n → +∞, provided that λ 2 n n → +∞. This suggests choosing λ m = 1/ √ n t , in which case the remainder term of Equation ( 6) is of order (log n) 3/2 /n, which is negligible relative to nonparametric convergence rates in median regression.

In order to have a more precise idea of the order of magnitude of the oracle excess risk, let us consider median regression with a Gaussian kernel. Under some assumptions, one of which coincides with Proposition 4.2, [14, Corollary 4.12] shows that taking λ n = c 1 n leads to rates of order n -2α 2α+d , where d ∈ N is the dimension of X and α > 0 is the smoothness of s. Therefore, taking λ m = 1/n t in Theorem 4.3, the remainder term of Equation ( 6) is at most of order (log n) 3/2 / √ n, hence negligible relative to the above risk rates as soon as 2α < d.

Theorem 4.3 can handle situations where g is different from the training loss c, provided that Comp(g, c) holds true. Such situations arise for instance in the case of support vector regression [START_REF] Scholkopf | Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond[END_REF]Chapter 9], which uses for training Vapnik's ε-insensitive loss c eps ε (u, y) = (|u -y|ε) + . This loss depends on a parameter ε, the choice of which is usually motivated by a tradeoff between sparsity and prediction accuracy [START_REF] Scholkopf | Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond[END_REF]. Therefore, some other loss is typically used to measure predictive performance, independently of ε. We state one possible application of Theorem 4.3 to this case, as a corollary. : (u, y) → (|y -u|ε) + be Vapnik's ε-insensitive loss and assume that the evaluation loss is g = c eps 0 : (u, y) → |u -y|. Assume that for every x the conditional distribution of Y given X = x has a unimodal density with respect to the Lebesgue measure, symmetric around its mode. Introduce the robust noise parameter :

σ = sup x∈X inf y ∈ R P(Y y | X = x) 3 4 -sup y ∈ R P(Y y | X = x) 1 4 . (7)
Then, applying Agghoo to a finite subfamily (A λ ) λ∈Λ of the rules given by Definition 4.1 with c = c eps ε and a kernel K such that K ∞ 1 yields the following oracle inequality. Assuming n v 100 and 3 |Λ| e √ nv , for any

θ ∈ (0; 1], (1 -θ)E ℓ s, f ag T (1 + θ)E min λ∈Λ ℓ s, A λ (D nt ) + max 72σ log n v |Λ| θn v , b 1 log 2 n v |Λ| θ 3 λ m n 2 v , b 2 log 3 2 n v |Λ| θλ m n v √ n t ,
where b 1 and b 2 are absolute constants.

Corollary 4.4 is proved in Appendix C.2. When ε = 0, ε-regression becomes median regression, which is discussed above. The oracle inequality of Corollary 4.4 is then the same as that given by Theorem 4.3 and Proposition 4.2. Assumptions of unimodality and symmetry allow to give more explicit values of a m and µ m in terms of σ. When ε > 0, the unimodality and symmetry assumptions are used to prove hypothesis Comp C (g, c).

Classification

Loss functions are not all convex. When convexity fails, the aggregation procedure should be revised.

In classification, Majhoo is a possible solution (see Definition 3.5). By Proposition D.1 in Appendix D, majority voting satisfies a kind of "convexity inequality" with respect to the 0-1 loss; as a result, oracle inequalities for the hold-out imply oracle inequalities for majhoo.

Hold-out for binary classification with 0-1 loss has been studied by Massart [START_REF] Massart | Concentration Inequalities and Model Selection[END_REF]. In that work, Massart makes an assumption which is closely related to margin hypotheses, such as the Tsybakov noise condition [START_REF] Mammen | Smooth discrimination analysis[END_REF] which we consider here. This approach allows to derive the following theorem. Assume that there exists β 0 and r ≥ 1 such that for ξ = (X, Y ) with distribution P ,

∀h > 0, P 2η(X) -1 h rh β (MA)
where η(X) := P(Y = 1 | X). Then, we have

E ℓ s, f mv T 3E inf m∈M ℓ s, A m (D nt ) + 29r 1 β+2 log e|M| n β+1 β+2 v .
Theorem 4.5 is proved in Appendix D. It shows that f mv T , like f ag T , satisfies an oracle inequality of the form (1) with A λ (D nt ) instead of A λ (D n ). Tsybakov's noise condition (MA) only depends on the distribution of (X, Y ) and not on the collection of learning rules. It is a standard hypothesis in classification, under which "fast" learning rates -faster than n -1/2 -are attainable [START_REF] Alexandre | Optimal aggregation of classifiers in statistical learning[END_REF]. In contrast with the results of Section 4.1, that are valid for various losses but only for a specific type of learning rule, Theorem 4.5 holds true for any family of classification rules.

The constant 3 in front of the oracle excess risk can be replaced by any constant larger than 2, at the price of increasing the constant in the remainder term, as can be seen from the proof (in Appendix D). However, our approach cannot yield a constant lower than 2, because we use Proposition D.1 instead of a convexity argument, since the 0-1 loss is not convex.

Numerical experiments

This section investigates how Agghoo and Majhoo's performance vary with their parameters V and τ = nt n , and how it compares to CV's performance at a similar computational cost -that is, for the same values of V and τ . Two settings are considered, corresponding to Corollary 4.4 and Theorem 4.5.

ε-regression

Consider the collection (A λ ) λ∈Λ of regularized kernel estimators (see Definition 4.1) with loss function c eps ε (u, y) = (|u -y|ε) + and Gaussian kernel

K(x, x ′ ) = exp[-(x -x ′ ) 2 /(2h 2 )] over X = R. Experimental setup Data (X 1 , Y 1 ), . . . , (X n , Y n ) are independent, with X i ∼ N (0, π), Y i = s(X i ) + Z i , with Z i ∼ N (0, 1/2) independent from X i .
The regression function is s(x) = e cos(x) , the kernel parameter is h = 1 2 and the threshold for the ε-insensitive Expectations of these quantities are estimated by taking an average over the 1000 samples; we also compute standard deviations for these estimates, which are not shown on Figure 1 since they are all smaller than 2.7% of the estimated value, so that most visible differences on the graph are significant.

loss is ε = 1 4 . Agghoo is applied to (A λ ) λ∈Λ over the grid Λ = { 2 j-1 500nt | 0 j 17},
Results are shown on Figure 1. The performance of Agghoo strongly depends on both τ and V . For a fixed τ , increasing V improves significantly the performance of the resulting estimator. Most of the improvement occurs between V = 1 and V = 5, and taking V much larger seems useless -at least for τ 0.5-, a behavior previously observed for CV [START_REF] Arlot | Choice of V for V -fold crossvalidation in least-squares density estimation[END_REF]. For a fixed V , the risk strongly decreases when τ increases from 0.1 to 0.5, decreases slowly over the interval [0.5; 0.8] and seems to rise for τ > 0.8. It seems that τ ∈ [0.6, 0.9] yields the best performance, while taking τ close to 0 should clearly be avoided (at least for V 10). Taking V large enough, say V = 10, makes the choice of τ less crucial: a large region of values of τ yield (almost) optimal performance. We do not know whether taking V larger can make the performance of Agghoo with τ 0.4 close to the optimum.

As a function of τ , the risk of CV behaves quite differently from Agghoo's. The performance does not degrade significantly when τ is small. The optimum is located at τ = 0.2, which is much smaller than for Agghoo. A possible explanation is that the regressors produced by cross-validation are all trained on the whole sample, so that τ only impacts risk estimation. Furthermore, additional simulations show, as expected, that higher values of τ (τ = 0.8 or τ = 0.9) improve risk estimation while degrading the hyperparameter selection performance. Compared to Agghoo, CV's performance depends much less on V : only V = 2 appears to be significantly worse than V 5. Let us now compare Agghoo and CV. For a given τ , Agghoo performs much better than the hold-out. This is not surprising and confirms that considering several data splits is always useful. For fixed (τ, V ) with τ 0.5, Agghoo does significantly better than CV if V 5, mostly worse if V = 1, and they yield similar performance for V = 2. When both parameters are well chosen, Agghoo can outperform the oracle, which is possible because Agghoo involves aggregation. Cross-validation, which is a pure selection method, naturally cannot beat the oracle. Overall, if the computational cost of V = 10 data splits is not prohibitive, Agghoo with optimized parameters (V = 10, τ ∈ [0.6, 0.9]) clearly improves over CV with optimized parameters (V = 10, τ = 0.2). The same holds with V = 5. This advocates for the use of Agghoo instead of CV, unless we have to take V < 5 for computational reasons.

Computational complexity By Equation (3), regularized kernel regressors can be represented linearly by vectors of length n t , therefore the aggregation step can be performed at training time by averaging these vectors. The complexity of this aggregation is at most O(V × n t ). In general, this is negligible relative to the cost of computing the hold-out, as simply computing the kernel matrix requires n t (n t + 1)/2 kernel evaluations. Therefore, the aggregation step does not affect much the computational complexity of Agghoo, so the conclusion of Section 3.3 that Agghoo and CV have similar complexity applies in the present setting.

Evaluating Agghoo and CV on new data x ∈ X also takes the same time in general, as both are computed by evaluating the expression nt j=1 θ j K(X j , x) with a pre-computed value of θ. A potential difference occurs when the θ λgiven by Definition 4.1, Equation (3)-are sparse: aggregation increases the number of non-zero coefficients, so evaluating f ag T on new data can be slower than evaluating f cv T if the implementation is designed to take advantage of sparsity.

k-nearest neighbors classification

Consider the collection (A NN k ) k 1, k odd of nearest-neighbors classifiersassuming k is odd to avoid ties-on the following binary classification problem.

P(Y i = 1 | X i ) = σ g(X i ) -b λ
where ∀u, v ∈ R, σ(u) = 1 1 + e -u and g(u, v) = e -(u 2 +v) 3 + u 2 + v 2 , b = 1.18 and λ = 0.05. The Bayes classifier is s : x → I g(x) b and the Bayes risk, computed numerically using the scipy.integrate python library, is approximately equal to 0.242. Majhoo (the classification version of Agghoo, see Definition 3.5) and CV are used with the collection (A NN k ) k 1, k odd and "Monte Carlo" training sets as in Section 5.1. An experimental procedure similar to the one of Section 5.1 is used to evaluate the performance of Agghoo and to compare it with Monte-Carlo cross-validation. Standard deviations of the excess risk were computed; they are smaller than 3.6% of the estimated value.

Results are shown on Figure 2. They are similar to the regression case (see Section 5.1), with a few differences. First, Agghoo does not perform better than the oracle. In fact, all methods considered here remain far from the oracle, which has an excess risk around 0.0034 ± 0.0004; both Agghoo and CV have excess risks at least 4 times larger. Second, risk curves as a function of τ for Agghoo are almost U -shaped, with a significant rise of the risk for τ > 0.6. Therefore, less data is needed for training, compared to Section 5.1. The optimal value of τ here is 0.6, at least for some values of V , up to statistical error. Third, the performance of CV as a function of τ has a similar U-shape, which makes the comparison between Agghoo and CV easier. For a given τ , Agghoo performs significantly better if V 10, while CV performs significantly better if V = 2; the difference is mild for V = 5.

Computational complexity As said in Section 3.3, the complexity of computing the optimal parameters for CV ( kcv T ) is the same as for Majhoo (( kho T ) T ∈T ). Here, there is no simple way to represent the aggregated estimator, so aggregation may have to be performed at test time. In that case, the complexity of evaluating Majhoo on new data is roughly V times greater than for CV, as explained in Section 3.3 for Agghoo.

Discussion

Theoretical and numerical results of the paper show that Agghoo can be used safely in RKHS regression, at least when its parameters are properly chosen; V 10 and τ = 0.8 seem to be safe choices. A variant, Majhoo, can be used in supervised classification with the 0-1 loss, with a general guarantee on its performance (Theorem 4.5). Experiments show that Agghoo actually performs much better than what the upper bounds of Section 4 suggest, with a significant improvement over cross-validation except when V < 5 splits are used. Proving theoretically that Agghoo can improve over CV is an open problem that deserves future works.

Since Agghoo and CV have the same training computational cost for fixed (V, τ ), Agghoo -with properly chosen parameters V, τ -should be preferred to CV, unless aggregation is undesirable for some other reason, such as interpretability of the predictors, or computational complexity at test time.

Our results can be extended in several ways. First, our theoretical bounds directly apply to subagging hold-out, which also averages several hold-out selected estimators. The difference is that, in subagging, the training set size is npq and the validation set size is q, for some q ∈ {1, . . . , np -1}, leading to slightly worse bounds than those we obtained for Agghoo (at least if E [ℓ(s, A m (D n ))] decreases with n). The difference should not be large in practice, if q is well chosen.

Oracle inequalities can also be obtained for Agghoo in other settings, as a consequence of our general theorems A.2 and A.3 in Appendix A.

A General Theorems

We need the following hypothesis, defined for two functions w i : R + → R + , i ∈ {1; 2} and a family (t m ) m∈M ∈ S M . Hypothesis H(w 1 , w 2 , (t m ) m∈M ): w 1 and w 2 are non-decreasing, and for any (m, m ′ ) ∈ M 2 , some c m m ′ ∈ R exists such that, for all k 2,

P γ(t m ) -γ(t m ′ ) -c m m ′ k k! w 1 ℓ(s, t m ) + w 1 ( ℓ(s, t m ′ )) 2 × w 2 ℓ(s, t m ) + w 2 ℓ(s, t m ′ ) k-2
.

This hypothesis is similar to those used by Massart [START_REF] Massart | Concentration Inequalities and Model Selection[END_REF] to study the hold-out and empirical risk minimizers. However, unlike [START_REF] Massart | Concentration Inequalities and Model Selection[END_REF], we intend to go beyond the setting of bounded risks.

We also need the following definition.

Definition A.1 Let w : R + → R + and r ∈ R + . Let δ(w, r) = inf δ 0 : ∀x δ, w(x) rx 2 ,
with the convention inf ∅ = +∞.

Remark A.1 • If r > 0 and x → w(x)
x is nonincreasing, then δ(w, r) is the unique solution to the equation w(x)

x = rx. • r → δ(w, r) is nonincreasing.

• If w(x) = cx β for c > 0 and β ∈ [0; 2), then δ(w, r) = c r 1 2-β .

A.1 Theorem statements

We can now state two general theorems from which we deduce all the theoretical results of the paper. The first theorem is a general oracle inequality for the hold-out. Assume that H(w 1 , w 2 , (t m ) m∈M ) holds true. Let x > 0. Then, with probability larger than 1e -x , for any θ ∈ (0; 1], we have

(1 -θ) ℓ(s, t m ) (1 + θ) min m∈M ℓ(s, t m ) + √ 2θδ 2 w 1 , θ 2
n v x + log|M| + θ 2 2 δ 2 w 2 , θ 2 4 n v x + log|M| . ( 8
)
If in addition, the two functions x → w j (x)

x , j = 1, 2, are nonincreasing, then for any x > 0, with probability larger than 1e -x , for all θ ∈ (0; 1], we have

(1 -θ)ℓ(s, t m ) (1 + θ) min m∈M ℓ(s, t m ) + δ 2 (w 1 , √ n v ) θ + 2(x + log|M|) θ (9) + δ 2 (w 2 , n v ) θ + (x + log|M|) 2 θ . ( 10
)
Using Theorem A.2, we prove the following general oracle inequality for Agghoo.

Theorem A.3 Assume that the hyperparameter space S is convex and that the risk L is convex. Let (A m ) m∈M be a finite collection of learning rules of size |M| 3. Let f ag T be an Agghoo estimator, according to Definition 3.4, with T satisfying assumption [START_REF] Arlot | Choice of V for V -fold crossvalidation in least-squares density estimation[END_REF]. Assume that w 1,1 , w 1,2 are D nt -measurable random functions such that almost surely, H w 1,1 , w 1,2 , (A m (D nt )) m∈M holds true. Assume also that for i ∈ {1, 2}, x →

w 1,i (x)
x is non-increasing. Then for any θ ∈ (0; 1],

(1 -θ)E ℓ s, f ag T (1 + θ)E min m∈M ℓ s, A m (D nt ) + R 1 (θ) (11)
where

R 1 (θ) = R 1,1 (θ) + R 1,2 (θ) with R 1,1 (θ) = θ + 2 1 + log|M| θ E δ 2 w 1,1 , √ n v , R 1,2 (θ) = θ + 2 1 + log|M| + log 2 |M| θ E δ 2 w 1,2 , n v .
Now, for any D nt -measurable functions w 2,1 and w 2,2 such that assumption H( w 2,1 , w 2,2 , (A m (D nt )) m∈M ) holds true almost surely, and any x > 0, θ ∈ (0; 1], we have

(1 -θ)E ℓ s, f ag T (1 + θ)E min m∈M ℓ s, A m (D nt ) + R 2 (θ) ( 12
)
where

R 2 (θ) = R 2,1 (θ) + R 2,2 (θ) + R 2,3 (θ) + R 2,4 (θ) with R 2,1 (θ) = √ 2θE δ 2 w 2,1 , θ 2
n v x + log|M| , R 2,2 (θ) = θ 2 2 E δ 2 w 2,2 , θ 2 4 n v x + log|M| , R 2,3 (θ) = e -x R 1,1 (θ) , and R 2,4 (θ) = e -x R 1,2 (θ) .

A.2 Proof of Theorem A.2

We start by proving three lemmas.

Lemma A.4 Let w be a non-decreasing function on R + . Let r > 0. Then ∀u 0, w(u) r u 2 ∨ δ 2 (w, r) ,

where δ(w, r) is given by Definition A.1.

Proof If u > δ(w, r), by Definition A.1,

w(u) ru 2 .
If u δ(w, r), since w is non-decreasing, for all v > δ(w, r),

w(u) w(v) rv 2 .
By taking the infimum over v, we recover w(u) rδ(w, r) 2 .

Lemma A.5 Let w be a nondecreasing function such that x → w(x)

x is nonincreasing over (0; +∞). Let a ∈ R + and b ∈ (0; +∞). For any θ ∈ (0; 1] and u 0,

a b w( √ u) θ 2 u + δ 2 (w, b) + a 2 δ 2 (w, b) θ .
Proof Since w is nondecreasing,

w( √ u) w( u + δ 2 (w, b)) = u + δ 2 (w, b) w( u + δ 2 (w, b)) u + δ 2 (w, b) . Since w(x)
x is nonincreasing and δ(w, b) > 0,

w( √ u) u + δ 2 (w, b) w(δ(w, b)) δ(w, b) u + δ 2 (w, b)bδ(w, b) by Definition A.1.
Therefore, using the inequality On that event, for all θ ∈ (0; 1],

√ ab θ 2 a + b 2θ , valid for any a > 0, b > 0, a b w( √ u) a 2 (u + δ(w, b) 2 )δ(w, b) 2 θ 2 (u + δ(w, b) 2 ) + a 2 δ(w, b) 2 θ . Lemma A.6 Let n v ∈ N * .
P γ(t m , •) = P nv γ(t m , •) + (P -P nv )γ(t m , •) P nv γ(t m * , •) + (P -P nv )γ(t m , •) = P γ(t m * , •) + (P -P nv )[γ(t m , •) -γ(t m * , •)] P γ(t m * , •) + θℓ(s, t m * ) + θℓ(s, t m ) + R(θ).
Substracting the Bayes risk P γ(s, •) on both sides, we get with probability greater than 1 -|M|p, for all θ ∈ (0; 1],

ℓ(s, t m ) ℓ(s, t m * ) + θℓ(s, t m * ) + θℓ(s, t m ) + R(θ),

that is, (1 -θ)ℓ(s, t m ) (1 + θ) min m∈M ℓ(s, t m ) + R(θ).
We now prove Theorem A.2. Let (m, m ′ ) ∈ M 2 be fixed. Let

σ := w 1 ( ℓ(s, t m )) + w 1 ( ℓ(s, t m ′ )), and
c := w 2 ( ℓ(s, t m )) + w 2 ( ℓ(s, t m ′ )) . ( 13
)
By hypothesis

H w 1 , w 2 , (t m ) m∈M , ∃c m,m ′ such that ∀k 2, P γ(t m , •) -γ(t m ′ , •) -c m,m ′ k k!σ 2 c k-2 . ( 14
) For all y > 0, let Ω y (m, m ′ ) be the event on which

(P nv -P ) γ(t m , •) -γ(t m ′ , •) 2y n v σ + cy n v . ( 15
)
By Bernstein's inequality, P Ω y (m, m ′ )

1e -y .

Let q = θ 2 nv x+log|M| . By Lemma A.4 with r = q, σ := w 1 ( ℓ(s, t m ))+w 1 ( ℓ(s, t m ′ )) q ℓ(s, t m ) ∨ δ 2 (w 1 , q) + ℓ(s, t m ′ ) ∨ δ 2 (w 1 , q) .

Set y = x + log|M| in [START_REF] Freund | A decision-theoretic generalization of on-line learning and an application to boosting[END_REF]. Then

2y n v σ := 2(x + log|M|) n v σ 2(x + log|M|) n v θ 2 n v x + log|M| ℓ(s, t m ) ∨ δ 2 (w 1 , q) + ℓ(s, t m ′ ) ∨ δ 2 (w 1 , q) θ √ 2 ℓ(s, t m ) + ℓ(s, t m ′ ) + 2δ 2 w 1 , θ 2
n v x + log|M| . ( 16
)
As for the second term of ( 15), by Lemma A.4 with r = q 2 , we have

c := w 2 ( ℓ(s, t m ))+w 2 ( ℓ(s, t m ′ )) q 2 ℓ(s, t m ) ∨ δ 2 (w 2 , q 2 ) + ℓ(s, t m ′ ) ∨ δ 2 (w 2 , q 2 ) .
Recall that q is shorthand for θ 2 nv x+log|M| . Therefore:

c y n v x + log|M| n v θ 2 4 n v x + log|M| ℓ(s, t m ) ∨ δ 2 (w 2 , q 2 ) + ℓ(s, t m ′ ) ∨ δ 2 (w 2 , q 2 ) = θ 2 4 ℓ(s, t m ) ∨ δ 2 (w 2 , q 2 ) + ℓ(s, t m ′ ) ∨ δ 2 (w 2 , q 2 ) θ 2 4 ℓ(s, t m ) + ℓ(s, t m ′ ) + 2δ 2 w 2 , θ 2 4 n v x + log|M| . ( 17
) Since 1 2 + 1 4
1 and θ ∈ (0; 1], plugging ( 16) and ( 17) in ( 15) yields, on the event Ω x+log|M| (m, m ′ ), for all θ ∈ (0; 1],

(P nv -P )[γ(t m , •) -γ(t m ′ , •)] θ ℓ(s, t m ) + ℓ(s, t m ′ ) + √ 2θδ 2 w 1 , θ 2
n v x + log|M| + θ 2 2 δ 2 w 2 , θ 2 4 n v x + log|M| . ( 18
)
Suppose now that x →

w j (x) x is nonincreasing for j ∈ {1; 2}. Let θ ∈ [0; 1]. Let y 0. By Lemma A.5 with a = √ 2y and b = √ n v , 2y n v σ = 2y n v w 1 ( ℓ(s, t m )) + w 1 ( ℓ(s, t m ′ )) θ 2 ℓ(s, t m ) + θ 2 ℓ(s, t m ′ ) + δ 2 (w 1 , √ n v ) θ + 2y θ . (19)
By Lemma A.5 with a = y and b = n v ,

c y n v = y n v w 2 ( ℓ(s, t m )) + w 2 ( ℓ(s, t m ′ )) θ 2 ℓ(s, t m ) + θ 2 ℓ(s, t m ′ ) + δ 2 (w 2 , n v ) θ + y 2 θ . ( 20
)
Plugging ( 19) and ( 20) in ( 15) yields, on the event Ω y (m, m ′ ), for all θ ∈ (0; 1],

(P nv -P )[γ(t m , •) -γ(t m ′ , •)] θℓ(s, t m ) + θℓ(s, t m ′ ) + δ 2 (w 1 , √ n v ) θ + 2y θ + δ 2 (w 2 , n v ) θ + y 2 θ . (21)
By ( 18), Lemma A.6 applies with p = e -x |M| and

R(θ) = √ 2θδ 2 w 1 , θ 2
n v x + log|M| + θ 2 2 δ 2 w 2 , θ 2 4 n v x + log|M| .
This yields [START_REF] Breiman | Random forests[END_REF]. By ( 21), Lemma A.6 applies with p = e -y and

R(θ) = θ δ 2 1 + δ 2 2 + 1 θ 2yδ 2 1 + y 2 δ 2 2 .
Setting y = log|M| + x yields [START_REF] Bühlmann | Analyzing bagging[END_REF].

A.3 Proof of Theorem A.3

We start by proving two lemmas.

Lemma A.7 Let f ∈ L 1 (R + , e -x dx) be a non-negative, non-decreasing function such that lim x→+∞ f (x) = +∞. Let X be a random variable such that

∀x ∈ R + , P X > f (x) e -x .
Then

E[X] +∞ 0 f (x)e -x dx .
Proof Let g ∈ L 1 (R + , e -x dx) be a non-decreasing, differentiable function such that g f . Then

E[X] +∞ 0 P[X > t]dt = g(0) 0 P[X > t]dt + +∞ 0 P[X > g(x)]g ′ (x)dx g(0) + +∞ 0 e -x g ′ (x)dx since g f = g(0) + [e -x g(x)] ∞ 0 + +∞ 0 e -x g(x)dx = +∞ 0 e -x g(x)dx .
It remains to show that g can approximate f in L 1 (I x 0 e -x dx). Let K be a nonnegative smooth function vanishing outside [-1; 1], normalized such that

K(t)dt = 1. Let ε > 0. Define f ε (x) = 1 ε f (t)K x + ε -t ε dt (22)
= 1 ε f (x + ε -t)K t ε dt (23)
By [START_REF] Massart | Concentration Inequalities and Model Selection[END_REF], f ε is smooth. By [START_REF] Meir | Generalization error bounds for bayesian mixture algorithms[END_REF], f ε is nondecreasing, moreover

f ε (x) -f (x) = 1 ε f (x + ε -t) -f (x) K t ε dt since K = 1 = 1 ε ε -ε f (x + ε -t) -f (x) K t ε dt since K(u) = 0 when |u| 1 0 since f is nondecreasing and K 0 .
Thus f ε f . Finally, by Jensen's inequality and Fubini's theorem,

|f ε (x) -f (x)|e -x dx 1 ε ε -ε K t ε |f (x + ε -t) -f (x)|e -x dx sup |τ | 2ε |f (x + τ ) -f (x)|e -x dx , which converges to 0 when ε → 0 since f ∈ L 1 (R + , e -x dx).
We use the following additional notation:

Definition A.8 Let g be the function defined by

∀(θ, y, p, q) ∈ (0; 1] × R 3 + , g(θ, y, p, q) = θ[p + q] + 1 θ 2yp + y 2 q .
This function satisfies the following properties.

Lemma A.9 Let g be the function given in Definition A.8. For any θ ∈ [0; 1] and any u > 0, p 0, q 0, e u +∞ u g(θ, y, p, q)e -y dy = θ +

2(1 + u) θ p + θ + 2 + 2u + u 2 θ q .
Proof of Lemma A.9

Using the formulas

+∞ u e -x dx = e -u , +∞ u xe -x dx = (1 + u)e -u , +∞ u x 2 e -x dx = (u 2 + 2u + 2)e -u ,
we get:

e u +∞ u g(θ, y, p, q)e -y dy = θ[p + q] + 2 θ (1 + u)p + (u 2 + 2u + 2) q θ = θ + 2(1 + u) θ p + θ + 2 + 2u + u 2 θ q .
We can now proceed with the proof of Theorem A.3. Let θ ∈ (0; 1] be fixed. Let ( f ho T ) T ∈T be the individual hold out estimators, so that

f ag T = 1 |T | T ∈T f ho T .
By convexity of the risk functional L, we have

L( f ag T ) 1 |T | T ∈T L( f ho T ) .
It follows by substracting L(s) that:

ℓ(s, f ag T ) 1 |T | T ∈T ℓ(s, f ho T ) .
Since the data are i.i.d, by assumption (2), all f ho T have the same distribution. Let T 1 = {1, . . . , n t }, so that D T 1 n = D nt . Taking expectations yields

E[ℓ(s, f ag T )] E[ℓ(s, f ho T 1 )] . (24)
Since H ( w 1,1 , w 1,2 , (A m (D nt ) m∈M )) holds, we can apply Theorem A.2 conditionally on D nt , with t m = A m (D nt ).

Proof of (11) For i ∈ {1; 2}, let δ 1,i = δ( w 1,i , √ n v i ). Let g be given in Definition A.8. By Theorem A.2, Equation [START_REF] Bühlmann | Analyzing bagging[END_REF], for any z 0, with probability greater than 1e -z ,

(1 -θ)ℓ(s, f ho T 1 ) (1 + θ) min m∈M ℓ(s, t m ) + g θ, z + log|M|, δ 2 1,1 , δ 2 1,2 . ( 25
)
As g is nondecreasing in its second variable, Lemma A.7 applied to the random variable (1θ)ℓ(s, f ho T 1 ) yields:

(1-θ)E ℓ(s, f ho T 1 ) D T 1 n (1+θ) min m∈M ℓ(s, t m )+ +∞ log|M| g θ, y, δ 2 1,1 , δ 2 1,2 e -(y-log|M|) dy .
Lemma A.9 yields

(1 -θ)E ℓ(s, f ho T 1 ) D T 1 n (1 + θ) min m∈M ℓ(s, t m ) + θ + 2 (1 + log|M|) θ δ 2 1,1 + θ + 2 (1 + log|M|) + log 2 |M| θ δ 2 1,2 .
Taking expectations with respect to

D T 1 n = D nt , (1 -θ)E ℓ(s, f ho T 1 ) (1 + θ)E min m∈M ℓ(s, A m (D nt )) + θ + 2 (1 + log|M|) θ E δ 2 1,1 + θ + 2 (1 + log|M|) + log 2 |M| θ E δ 2 1,2
.

Equation ( 11) then follows from Equation [START_REF] Nemirovski | Topics in Non-parametric Statistics[END_REF].

Proof of (12) Fix x 0.

For i ∈ {1; 2}, let δ 2,i = δ w 2,i , θ 2 nv x+log|M| i .
By Theorem A.2, Equation (8), with probability larger than 1e -x ,

(1 -θ)ℓ(s, f ho T 1 ) (1 + θ) min m∈M ℓ(s, t m ) + √ 2θ δ 2 2,1 + θ 2 2 δ 2 2,2 . (26)
Combining ( 25) and ( 26), for any z 0, with probability larger than 1-e -z ,

(1 -θ)ℓ(s, f ho T 1 ) (1 + θ) min m∈M ℓ(s, t m ) + √ 2θ δ 2 2,1 + θ 2 2 δ 2 2,2 + I z x g θ, z + log|M|, δ 2 1,1 , δ 2 1,2 .
By Lemma A.7,

(1 -θ)E ℓ(s, f ho T 1 ) D T 1 n (1 + θ) min m∈M ℓ(s, t m ) + √ 2θ δ 2 2,1 + θ 2 2 δ 2 2,2 + +∞ x+log|M| g θ, y, δ 2 1,1 , δ 2 1,2 e -(y-log|M|) dy .
By Lemma A.9, it follows that

(1 -θ)E ℓ(s, f ho T 1 ) D T 1 n (1 + θ) min m∈M ℓ(s, t m ) + √ 2θ δ 2 2,1 + θ 2 2 δ 2 2,2 + e -x θ + 2(1 + x + log|M|) θ δ 2 1,1 + e -x θ + 2(1 + x + log|M|) + (x + log|M|) 2 θ δ 2 1,2 .
Taking expectations with respect to D T 1 n and using inequality (24) yields Equation ( 12) of Theorem A.3.

B RKHS regression: proof of Theorem 4.3

In the following, for any g : R × R → R and t : X → R, the function (x, y) → g(t(x), y) is denoted by g • t.

B.1 Preliminary results

Remark first that the RKHS norm dominates the supremum norm:

Lemma B.1 If κ = sup x K(x, x) < +∞ then for any t ∈ H, t ∞ √ κ t H .
Proof By definition of an RKHS, ∀t ∈ H, ∀x ∈ X , t, K(x, •) H = t(x). It follows that, for any t ∈ H,

t 2 ∞ = sup x t(x) 2 = sup x t, K(x, •) 2 H t 2 H sup x K(x, •), K(x, •) t 2 H sup x K(x, x).
Using standard arguments, the following deviation inequality can be derived.

Proposition B.2 Let H denote a RKHS with bounded kernel K : X × X → R. Let κ = sup x K(x, x) and h : R 2 → R be Lipschitz in its first argument with Lipschitz constant L. For any t ∈ H and r > 0, denote

B H (t, r) = t ′ ∈ H | t ′ -t H r .
Let t 0 ∈ H. Then for any probability measure P on X × R and any y > 0,

P ⊗n sup (t 1 ,t 2 )∈B H (t 0 ,r) 2 (P n -P ) h • t 1 -h • t 2 2(2 + 2y)L r √ κ √ n e -y . Proof Let D n = (X i , Y i ) 1 i n be a dataset drawn from P . Let (σ i ) 1 i n be i.i.d Rademacher variables independent from D n . Denote by R n (F) = E sup f ∈F 1 n n i=1 σ i f (X i ) the Rademacher complexity of a class F of real valued functions. By Lemma B.1, for any (t 1 , t 2 ) ∈ B H (t 0 , r) 2 , h • t 1 -h • t 2 ∞ L t 1 -t 2 ∞ L [ t 1 -t 0 ∞ + t 2 -t 0 ∞ ] 2L √ κr .
By symmetry under exchange of t 1 and t 2 , notice that

R n {h • t 1 -h • t 2 |(t 1 , t 2 ) ∈ B H (t 0 , r) 2 } = sup (t 1 ,t 2 )∈B H (t 0 ,r) 2 1 n n i=1 σ i (h • t 1 -h • t 2 )(X i ) .
By the bounded difference inequality and [START_REF] Boucheron | Theory of classification: a survey of some recent advances[END_REF], Theorem 3.2, it follows that for any y > 0, with probability greater than 1e -y ,

sup (t 1 ,t 2 )∈B H (t 0 ,r) 2 (P n -P )(h•t 1 -h•t 2 ) 2R n {h • t 1 -h • t 2 |(t 1 , t 2 ) ∈ B H (t 0 , r) 2 } +2Lr 2κy n .
Moreover,

R n {h • t 1 -h • t 2 |(t 1 , t 2 ) ∈ B H (t 0 , r) 2 } R n ({h • t|t ∈ B H (t 0 , r)}) + R n ({-h • t|t ∈ B H (t 0 , r)})
2LR n (B H (t 0 , r))by the contraction lemma (relevant version: [START_REF] Meir | Generalization error bounds for bayesian mixture algorithms[END_REF], Theorem 7),

= 2LR n (B H (0, r)) (by translation invariance).
Finally, by a classical computation (see for example [START_REF] Boucheron | Theory of classification: a survey of some recent advances[END_REF], Section 4.1.2),

R n {h • t 1 -h • t 2 |(t 1 , t 2 ) ∈ B H (t 0 , r) 2 } 2L r n E n i=1 K(X i , X i ) 2Lr κ n .
The proof of Theorem 4.3 also uses the following peeling lemma.

Lemma B.3 Let (Z u ) u∈T be a stochastic process and d : T → R + be a function. Let a 0 and b ∈ (0; 2] and assume that ∀r, y 0, P sup

u∈T :d(u) r Z u r 1 + b(a + y) √ n e -y . (27)
Then, for any θ ∈ (0; +∞),

P ∃u ∈ T, Z u θd 2 (u) + 2 + b 1.1 + 2(a + y) θn e -y .
Proof Let x > 0. Let η ∈ (1; 2], j m ∈ N * and y 0 ∈ R be absolute constants that will be determined later. Then

I sup u∈T Z u d 2 (u) + x 2 1 + b(a + y) x √ n I sup u∈T :d(u) x Z u d 2 (u) + x 2 1 + b(a + y) x √ n + +∞ j=0 I sup u∈T :η j x d(u) η j+1 x Z u d 2 (u) + x 2 1 + b(a + y) x √ n I sup u∈T :d(u) x Z u x 2 1 + b(a + y) x √ n + +∞ j=0 I sup u∈T :η j x d(u) η j+1 x Z u (1 + η 2j )x 2 1 + b(a + y) x √ n I sup u∈T :d(u) x Z u x(1 + b(a + y)) √ n + +∞ j=0 I sup u∈T :d(u) η j+1 x Z u (1 + η 2j ) x(1 + b(a + y)) √ n . (28)
Notice that:

(1 + η 2j ) x(1 + b(a + y)) √ n = xη j+1 η 2j + 1 η j+1 1 + b(a + y) √ n = xη j+1 1 + b(a + z j ) √ n ,
where:

z j = 1 b η 2j + 1 η j+1 -1 + η 2j + 1 η j+1 b(a + y) 2 -a 1 b η 2j + 1 η j+1 -1 2 + η 2j + 1 η j+1 2 y
since a 0 and η 2j + 1 η j+1 .

Taking expectations in [START_REF] Scholkopf | Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond[END_REF] and using hypothesis [START_REF] Salmon | Optimal aggregation of affine estimators[END_REF], we obtain:

P sup u∈T Z u d 2 (u) + x 2 1 + b(a + y) x √ n e -y + +∞ j=0 e -z j .
So for any y y 0 ,

P sup u∈T Z u d 2 (u) + x 2 1 + b(a + y) x √ n e -y + e -y +∞ j=0 exp - 1 b η 2j + 1 η j+1 -1 2 - (η 2j + 1) 2 (η j+1 ) 2 -1 y e -y + e -y +∞ j=0 exp - 1 b η 2j + 1 η j+1 -1 2 - (η 2j + 1) 2 (η j+1 ) 2 -1 y 0 . (29)
Now, we have

exp - 1 b η 2j + 1 η j+1 -1 2 - (η 2j + 1) 2 (η j+1 ) 2 -1 y 0 exp - (η 2j + 1) 2 (η j+1 ) 2 -1 y 0 exp y 0 -η 2(j-1) y 0 . (30)
Let u denote the sequence u j = exp y 0η 2(j-1) y 0 . Then for j j m , log u j+1log u j = η 2(j-1) y 0η 2j y 0

= y 0 (1 -η 2 )η 2(j-1) y 0 (1 -η 2 )η 2(jm-1) since η > 1 .
Thus, ∀j j m , u j+1 u j exp -y 0 (η 2 -1)η 2(jm-1) .

Therefore, we have ∀j 0, u j+jm u jm exp -jy 0 (η 2 -1)η 2(jm-1))

and +∞ j=jm u j u jm 1exp -y 0 (η 2 -1)η 2(jm-1) -1 .

It follows from ( 29) and ( 30) that for any y y 0 , since b 2,

e y P sup u Z u d 2 (u) + x 2 1 + b(a + y) x √ n 1 + jm j=0 exp - 1 2 η 2j + 1 η j+1 -1 2 - (η 2j + 1) 2 (η j+1 ) 2 -1 y 0 + exp y 0 -η 2(jm-1) y 0 1 -exp -y 0 (η 2 -1)η 2(jm-1) . ( 31
)
On the other hand, when y y 0 , trivially,

P sup u Z u d 2 (u) + x 2 1 + b(a + y) x √ n 1 e y 0 e -y .
Taking η = 1.18, j m = 10, y 0 = 0.52, the right-hand side of (31) evaluates to 1.6765 < 1.7 whereas e y 0 1.683 < 1.7. It follows that for all y > 0,

P sup u Z u d 2 (u) + x 2 1 + b(a + y) x √ n 1.7e -y . ( 32
)
Now take x = 1+ √ b(a+y) θ √ n with θ > 0. We can rewrite:

P sup u Z u d 2 (u) + x 2 1 + b(a + y) x √ n = P ∃u ∈ T, Z u d 2 (u) + x 2 θ = P ∃u ∈ T, Z u θd 2 (u) + 1 θn 1 + b(a + y) 2 P ∃u ∈ T, Z u θd 2 (u) + 2 + 2b(a + y) θn .
It follows from Equation [START_REF] Varoquaux | Assessing and tuning brain decoders: Cross-validation, caveats, and guidelines[END_REF], with y replaced by y + 0.55, that

P ∃u ∈ T, Z u θd 2 (u) + 2 + b(
h(t µ ) µ + t µ 2 H h(t λ ) µ + t λ 2 H = h(t λ ) λ + t λ 2 H + 1 µ - 1 λ h(t λ ) h(t µ ) λ + t µ 2 H + 1 µ - 1 λ h(t λ ) ,
which implies (µ -1λ -1 )h(t µ ) (µ -1λ -1 )h(t λ ) and thus h(t λ ) h(t µ ) since λ < µ. For a projection Π C , it is well known that:

∀t ∈ H, ∀t ′ ∈ C, t -Π C (t), Π C (t) -t ′ H 0 . Choosing C = {t : h(t) h(t µ )}, t ′ = t λ ∈ C, t = 0 yields -t µ , t µ -t λ H 0. Therefore t λ 2
H = t µ + (t λ -t µ ) 2 H = t µ 2 H + t λ -t µ 2 H + 2 t µ , t λ -t µ H t µ 2 H + t λ -t µ 2 H . Lemma B.5 Let (b, c) ∈ R 2
+ and l b,c (x) = bx + c. Let δ be given by Definition A.1. For any r ∈ R + ,

δ 2 (l b,c , r) b 2 r 2 + 2c r . (33)
For (a, b, c) ∈ R 3 + , let g a,b,c (x) = ax ∨ bx 3 + cx 2 1 2 . For any r ∈ R + ,

δ 2 g a,b,c , r a 2 r 2 ∨ b 2 r 4 + 2c r 2 a 2 r 2 + b 2 r 4 + 2c r 2 . ( 34
) Proof Since x → l b,c (x) x
is nonincreasing, we have by Remark A.1:

bδ(l b,c , r) + c = rδ 2 (l b,c , r), i.e

δ 2 (l b,c , r) - bδ(l b,c , r) r - c r = 0 . Hence δ(l b,c , r) = b 2r + 1 2 b 2 r 2 + 4c r . Thus δ 2 (l b,c , r) 2 b 2 4r 2 + b 2 4r 2 + c r b 2 r 2 + 2c r .
This proves [START_REF] Yang | Adaptive regression by mixing[END_REF]. For any x > 0, g a,b,c (x) rx 2 is equivalent to

ax rx 2 (35)
and

bx 3 + cx 2 r 2 x 4 . (36)
Eq. ( 35) is equivalent to x a r . On the other hand,

x > b 2 r 4 + 2c r 2 1 2
=⇒ x > δ(l b,c , r 2 ) by ( 33)

=⇒ bx + c r 2 x 2 by Definition A.1 =⇒ (36).

Therefore, whenever

x > a r ∨ b 2 r 4 + 2c r 2 1 2
, it holds that g a,b,c (x) rx 2 . (34) follows by Definition A.1.

B.2 Uniform control on the empirical process

From now on until the end of the proof, the notation and hypotheses of Theorem 4.

(P nt -P )(c • t 1 -c • t 2 ) - λ m 2 d(t 1 , t 2 ) 2 ,
so that

∀(t 1 , t 2 ) ∈ H 2 , (P nt -P )(c • t 1 -c • t 2 ) λ m 2 d(t 1 , t 2 ) 2 + 32κL 2 y λ m n t . (38)
We then have the following bounds on y.

Claim B.6.1 For all x 0, P y 2.6 + log|Λ| + x e -x .

In particular, E[ y] 4 + log|Λ|.

Proof Let (t

{(P nt -P )(c • t 1 -c • t 2 )} max λ∈Λ sup (t 1 ,t 2 )∈B(s λ ,r) 2 (P nt -P )(c•t 1 -c•t 2 ).
(39) From Proposition B.2 and the union bound, it follows that, for any x 0,

P max λ∈Λ sup (t 1 ,t 2 )∈B(s λ ,r) 2 (P nt -P )(c • t 1 -c • t 2 ) 2 2 + 2(x + log|Λ|) L r √ κ √ n t e -x .
It follows by Equation (39) that, for all x 0, P sup

(t 1 ,t 2 ):d(t 1 ,t 2 ) r 1 4L √ κ (P nt -P )(c • t 1 -c • t 2 ) 1 + x + log|Λ| 2 r √ n t e -x . By Lemma B.3 with θ = λm 8L √ κ , a = log|Λ|, b = 1 2 , with probability larger than 1 -e -x , ∀(t 1 , t 2 ), (P nt -P )(c • t 1 -c • t 2 ) λ m 2 d(t 1 , t 2 ) 2 + 32L

B.3 Verifying the assumptions of Theorem A.3

Theorem 4.3 is a consequence of Theorem A.3. For all λ ∈ Λ, let t λ = A λ (D nt ), where A λ is given by Definition 4.1. To verify the assumptions of Theorem A.3, adequate functions ( w i,j ) (i,j)∈{1;2} 2 must be found such that for i ∈ {1; 2}, H w i,1 , w i,2 , ( t λ ) λ∈Λ holds almost surely . This is the purpose of this section.

The core of the proof of Theorem 4.3 lies in the following deterministic claim.

Claim B.6.2 For all λ, µ ∈ Λ such that λ µ,

t λ -t µ 2 ∞ κC λ m ℓ(s, t µ ) + 96L 2 κ 2 y λ 2 m n t .
Proof Let (λ, µ) ∈ Λ 2 with λ µ. Let s µ be as in Definition B.6, Equation (37). By convexity of c, the function t

→ P (c • t) + µ t 2 H is µ-strongly convex. Since s µ is its optimum, we get ∀t ∈ H, P (c • t) + µ t 2 H P (c • s µ ) + µ s µ 2 H + µ t -s µ 2 H . Hence, taking t = t µ , λ m t µ -s µ 2 H µ t µ -s µ 2 H P (c • t µ ) + µ t µ 2 H -P (c • s µ ) -µ s µ 2 H = P nt (c • t µ ) + µ t µ 2 H -P nt (c • s µ ) -µ s µ 2 H + (P -P nt )(c • t µ -c • s µ ) . By Definition 4.1, P nt (c • t µ ) + µ t µ 2 H P nt (c • s µ ) + µ s µ 2 H . Hence λ m t µ -s µ 2 H (P -P nt )(c • t µ -c • s µ ) = (P nt -P )(c • s µ -c • t µ ). Now take t 1 = s µ and t 2 = t µ in Equation (38) of Definition B.6 to get λ m t µ -s µ 2 H λ m 2 d(s µ , t µ ) 2 + 32L 2 κ y λ m n t = λ m 2 s µ -t µ 2 H + 32L 2 κ y λ m n t . Therefore, t µ -s µ 2 H 64L 2 yκ λ 2 m n t . ( 40
) Now t λ -t µ 2
H can be bounded as follows. Since t → P nt (c • t) + λ t 2 H is λ-strongly convex and t λ is its optimum,

λ m t λ -t µ 2 H λ t λ -t µ 2 H P nt (c • t µ ) -P nt (c • t λ ) + λ t µ 2 H -λ t λ 2 H . By Lemma B.4 with h(t) = P nt (c • t), t λ -t µ 2 H t λ 2 H -t µ 2 H . Hence (λ m + λ) t λ -t µ 2 H P nt (c • t µ ) -P nt (c • t λ ) = P (c • t µ ) -P (c • t λ ) + (P nt -P ) c • t µ -c • t λ P (c • t µ ) -min t∈S P (c • t) + (P nt -P ) c • t µ -c • t λ Cℓ(s, t µ ) + (P nt -P ) c • t µ -c • t λ by hypothesis Comp C (g, c) .
By Definition B.6, Equation (38) with t 1 = t µ and t 2 = t λ ,

(λ m + λ) t λ -t µ 2 H Cℓ(s, t µ ) + λ m 2 t µ -s µ H + t λ -t µ H 2 + 32L 2 κ y λ m n t Cℓ(s, t µ ) + λ m 2 8 L yκ λ m √ n t + t λ -t µ H 2 + 32L 2 κ y λ m n t by equation (40).
For any (a, b), (a + b) 2 2a 2 + 2b 2 , hence

(λ + λ m ) t λ -t µ 2 H Cℓ(s, t µ ) + λ m 2 128L 2 yκ λ 2 m n t + 2 t λ -t µ 2 H + 32L 2 κ y λ m n t .
This yields:

λ t λ -t µ 2 H Cℓ(s, t µ ) + 96L 2 κ y λ m n t ,
and finally, since λ λ m :

t λ -t µ 2 H Cℓ(s, t µ ) λ m + 96L 2 κ y λ 2 m n t . Now, by Lemma B.1, t λ -t µ 2 ∞ κ t λ -t µ 2 H κC λ m ℓ(s, t µ ) + 96L 2 κ 2 y λ 2 m n t .
This proves Claim B.6.2.

Using hypothesis SC ρ,ν -Equation ( 4)-, a refined bound can be ob-

tained on P g • t λ -g • t µ 2 . Claim B.6.3 For any (λ, µ) ∈ Λ 2 , P g • t λ -g • t µ 2 w B ℓ(s, t λ ) 2 + w B ℓ(s, t µ ) 2 where w B (x) 2 = max ρx 2 , ν 4 3 κC λ m x 3 + 10νL κ y λ m √ n t x 2 .
Proof By hypothesis SC ρ,ν -Equation ( 4)-with u = t λ (X) and v = t µ (X),

E (g • t λ -g • t µ ) 2 (X, Y )|X ρ ∨ ν| t λ (X) -t µ (X)| ℓ X ( t λ (X)) + ℓ X ( t µ (X)) ρ ∨ ν t λ -t µ ∞ ℓ X ( t λ (X)) + ℓ X ( t µ (X)) , where ℓ X (u) = E[g(u, Y )|X]-min v∈R E[g(v, Y )|X].
Integrating this inequality with respect to X, it follows that,

P g • t λ -g • t µ 2 ρ ∨ ν t λ -t µ ∞ ℓ(s, t λ ) + ℓ(s, t µ ) .
Assume without loss of generality that λ µ. By Claim B.6.2,

P g • t λ -g • t µ 2 ρ ∨ ν κC λ m ℓ(s, t µ ) + 10 Lκ y λ m √ n t ℓ(s, t λ ) + ℓ(s, t µ ) max ρ ℓ(s, t λ ) + ℓ(s, t µ ) , ν κC λ m ℓ(s, t µ )ℓ(s, t λ ) + ℓ(s, t µ ) 3 + 10 Lκ y λ m √ n t ℓ(s, t λ ) + ℓ(s, t µ ) . (41)
Using the inequality ab a p p + b q q with Hölder conjugates p = 3, q = 3 2 , we have:

ℓ(s, t µ )ℓ(s, t λ ) + ℓ(s, t µ ) 3 1 3 ℓ(s, t µ ) 3 + 2 3 ℓ(s, t λ ) 3 2 + ℓ(s, t µ ) 3 4 3 ℓ(s, t λ ) 3 + ℓ(s, t µ ) 3 . (42)
Claim B.6.3 then follows from inequalities (41) and (42) using the elementary inequality

(a + b) ∨ (c + d) a ∨ c + b ∨ d.
As g is L-Lipschitz in its first argument, it follows from Claim B.6.2 that for all λ, µ ∈ Λ s.t. λ µ,

g • t λ -g • t µ ∞ L t λ -t µ ∞ L κC λ m ℓ(s, t µ ) + 10L 2 κ y λ m √ n t w A ℓ(s, t µ ) + w A ℓ(s, t λ ) , (43)
where

w A (x) = L κC λ m x + 5L 2 κ y λ m √ n t . (44)
If follows that for all k 2,

P g • t λ -g • t µ k g • t λ -g • t µ k ∞ w A ℓ(s, t µ ) + w A ℓ(s, t λ ) k .
This proves that hypothesis H w A , w A , ( t λ ) λ∈Λ , as defined in Appendix A, holds true. It follows from Claim B.6.3 and Equation (43) that, for all k 2,

P |g • t λ -g • t µ | k g • t λ -g • t µ k-2 ∞ P g( t λ (X), Y ) -g( t µ (X), Y ) 2 w A ℓ(s, t λ ) + w A ℓ(s, t µ ) k-2 × w B ℓ(s, t λ ) + w B ℓ(s, t µ ) 2 ;
which proves that H w B , w A , ( t λ ) λ∈Λ holds true.

B.4 Conclusion of the proof

We have proved that H w B , w A , ( t λ ) λ∈Λ and H w A , w A , ( t λ ) λ∈Λ hold, where w B is defined in Proposition B.6.3 and w A in Equation (44). Moreover, x → w A (x)

x is nonincreasing. Therefore, Theorem A.3 applies with w 1,1 = w A , w 1,2 = w A , w 2,1 = w B , w 2,2 = w A , x = log n v and it remains to bound the remainder terms (R 2,i ) 1 i 4 of Equation [START_REF] Luc | A Probabilistic Theory of Pattern Recognition[END_REF]. For each i, we bound R 2,i (θ) by an absolute constant times max{T 1 (θ), T 2 (θ), T 3 (θ)}, where

T 1 (θ) = 6ρ 100 log(n v |Λ|) θn v T 2 (θ) = (ν ∨ L) 2 κC log 2 (n v |Λ|) θ 3 λ m n 2 v T 3 (θ) = L(ν ∨ L)κ log 3 2 (n v |Λ|) θλ m n v √ n t .
Summing up these bounds yields Theorem 4.3. . Moreover, if Y is symmetric around q, i.e (q -Y ) ∼ (Y -q), then R reaches a minimum at q.

B.4.1 Bound on R 2,1 (θ) = √ 2θE δ 2 w B , θ 2 nv log(nv |Λ|) Recall that w B (x) 2 := max ρx 2 , ν 4 3 κC λm x 3 + 10νL κ √ y λm √ nt x 2 . By Equation (34) in Lemma B.5 with a = √ ρ, b = ν 4 3 κC λm , c = 10νL κ √ y λm √ nt , δ 2 w B , θ 2
n v log(n v |Λ|) 4ρ log(n v |Λ|) θ 2 n v + 29ν
Proof First, remark that R is convex by convexity of ψ. Let u ∈ R.

Remark 3 . 1 (

 31 Two options for binary classification) In binary classification (Example 2.1 with M = 2), it is classical to consider classifiers of the form I f 0 where f ∈ S conv = {f : X → R} aims at minimizing a surrogate convex risk associated with the loss g conv : (y ′ , y) → φ[(2y ′ -1)(2y -1)]

  du a(x)I |u-s(x)| b(x) for every x ∈ X . Let a m = inf x∈X a(x) and µ m = inf x∈X a(x)b(x) . If a m > 0 and µ m > 0, then (g, X, Y ) satisfies SC 4 am , 2 µm . Proposition 4.2 is proved in Appendix C.1. We can now state our first main result. Theorem 4.3 Let Λ ⊂ R * + be a finite grid. Using the notation of Definition 3.4, let f ag T be the output of Agghoo, applied to the collection (A λ ) λ∈Λ given by Definition 4.1. Assume that λ m = min Λ > 0 and κ = sup x∈X K(x, x) < +∞. Assume that Comp C (g, c) holds for a constant C > 0 and that (g, X, Y ) satisfies SC ρ,ν with constants ρ 0, ν 0. Assume that c and g are convex and Lipschitz in their first argument, with Lipschitz constant less than L. Assume also that n v 100 and 3 |Λ| e √ nv . Then, for any θ ∈ (0; 1],

Corollary 4 .

 4 4 (ε-regression) Let c = c eps ε

Theorem 4 . 5

 45 Consider the classification setting described in Example 2.1 with M = 2 classes (binary classification). Let (A m ) m∈M be a collection of learning rules and T a collection of training sets satisfying assumption (2).

Figure 1 :

 1 Figure 1: Performance of Agghoo and CV for ε-regression

Figure 2 :

 2 Figure 2: Classification performance of Majhoo and CV for the k-NN family

Theorem A. 2

 2 Let (t m ) m∈M be a finite collection in S, and m ∈ argmin

m∈MP

  nv γ(t m , •) .

3 2 θλ m n v √ n t 100T 1

 321 (θ) + 42T 2 (θ) + 114T 3 (θ) 256 × max {T 1 (θ), T 2 (θ), T 3 (θ)} . B.4.2 Bound on R 2,2 (θ) = θ 2 2 E δ 2 w A , θ24 nv log(nv|Λ|) Recall that by definition, w A (x) = L κC λm x+ 5L 2 κ √ y λm √ nt (Equation (44)). By Equation (33) in Lemma B.5 with b = L κC λm and c = 5L

R 2 , 4

 24 (θ) 0.014T 2 (θ) + 2.1T 3 (θ) 2.2 × max{T 1 (θ), T 2 (θ), T 3 (θ)} .B.4.5 ConclusionSumming up the above inequalities, we get that for every θ ∈ (0; 1],R 2 (θ) = R 2,1 (θ) + R 2,2 (θ) + R 2,3 (θ) + R 2,4 (θ) 289 max{T 1 (θ), T 2 (θ), T 3 (θ)} .Equation (12) in Theorem A.3 thus yields1θ E[ℓ(s, f ag T )] 1 + θ E min λ∈Λ ℓ(s, A λ (D nt )) + 289 max{T 1 (θ), T 2 (θ), T 3 (θ)}which proves Theorem 4.3 with b 1 = 289(ν ∨L) 2 κC and b 2 = 289L(ν ∨L)κ. C Proof of Proposition 4.2 and Corollary 4.4 Let us start by two useful lemmas. Lemma C.1 If ψ is a convex, Lipschitz-continuous, and even function, and Y is a random variable with a non-atomic distribution, the function R : u → E ψ(u -Y ) is convex and differentiable with derivative R ′ (u) = E[ψ ′ (u -Y )]

For h = 0 , 4 am , 4 µm.C. 2 4 Corollary 4 . 4

 0442444 let k(h, Y ) = ψ(u+h-Y )-ψ(u-Y ) h . Let A be the set on which ψ is non-differentiable. Since ψ is convex, A is at most countable. By definition, k(h, Y ) -→ h→0 ψ ′ (u-Y ) whenever u-Y / ∈ A, that is to say Y / ∈ u-A. Since Y is non-atomic, P(Y / ∈ u -A) = 1.Moreover, since ψ is Lipschitz, there exists a constant L such that ∀h = 0, |k(h, Y )| L. Therefore, by the dominated convergence theorem,R(u + h) -R(u) h = E[k(h, Y )] -→ h→0 E[ψ ′ (u -Y )] . Thus, R is differentiable and for all u ∈ R, R ′ (u) = E[ψ ′ (u -Y )].Otherwise, by Equation (54),(uv) 2 |u -v| |uu * | + |vu * | 2|u -v||uu * | 4 εδ |u -v| g(u)g u * 4 εδ |u -v| g(u) + g(v) -2g(u * ) .(56)C.1 Proof of Proposition 4.2Now, we can prove Proposition 4.2. Let R x : u → |u -y|dF x (y). By Lemma C.1 with ψ = | • |, for all v ∈ R, R ′ x (v) = [-I v-y 0 + I v-y 0 ] dF x (y) = F x (v) -1 -F x (v) = 2 [F x (v) -F x (s(x))]since by definition, F x (s(x)) = 1 2 . Hence by hypothesis (5), for all u ∈ [s(x)b(x); s(x) + b(x)],|R ′ x (u)| 2a(x)|us(x)|.Therefore by Lemma C.2, for all x ∈ X and (u,v) ∈ R 2 , (uv) 2 4 a(x) ∨ 4|u -v| a(x)b(x) R x (u) + R x (v) -2R x s(x) R x (u) + R x (v) -2R x s(x) .Since g : (u, y) → |u -y|, it follows by taking x = X that(g(u, Y )g(v, Y )) 2 (uv) ℓ X (u) + ℓ X (v) ,which implies hypothesis SC Proof of Corollary 4.is a consequence of Theorem 4.3. Let us check that its assumptions are satisfied.for some nonnegative and nondecreasing continuous function w on R + , such that x → w(x)/x is nonincreasing on (0, +∞) and w(1) 1.Let us first prove that assumption (63) holds true. On one hand, since Y = {0, 1}, for any t ∈ S,Var I {t(X) =Y } -I {s(X) =Y } E[|I {t(X) =Y } -I {s(X) =Y } | 2 ] = E[I {t(X) =s(X)} ] = E |t(X)s(X)|] . (64)On the other hand, since we consider binary classification with the 0-1 loss, for any t ∈ S and h > 0,ℓ(s, t) = E |2η(X) -1| • |t(X)s(X)| by [12, Theorem 2.2] hE |t(X)s(X)|I {|2η(X)-1| h} hE |t(X)s(X)| -I {|2η(X)-1|<h} since ts ∞ 1 hE |t(X)s(X)|rh β+1 by (MA).This lower bound is maximized by takingh = h * := E |t(X)s(X)| r(β + 1)1 β , which belongs to [0, 1] since r 1 and E |t(X)s(X)| 1. Thus, we obtain ℓ(s, t) h * β β + 1 E |t(X)s(X)| = β (β + 1) (β+1)/β r 1/β E |t(X)s(X)| (β+1)/β hence Eq. (64) leads to Var I {t(X) =Y } -I {s(X) =Y } E |t(X)s(X)| β + 1 β β/(β+1) r 1 β+1 ℓ(s, t) . (63) holds true with w(u) = √ r 1 u β β+1 and r 1 = 2r 1 β+1 , which statisfies the required conditions. So, by [22, Eq. (8.60)], for any θ ∈ (0, 1), E ℓ s, f ho T where δ * is the positive solution of the fixed-point equation w(δ * ) = √ n v δ 2 * , that is δ 2 * = (r 1 /n v ) β+1 β+2 . Taking expectations with respect to the training data D T n , we obtain E ℓ(s, f ho T )

  Let M be a finite set and let (t m ) m∈M ∈ S M . Assume that there exists p ∈ [0; 1/|M|) and a function R : (0; 1] → R + such that for any m, m ′ in M, with probability greater than 1p, Then for m ∈ argmin m∈M P nv γ(t m , •), with probability greater than 1-|M|p, Proof Let m * ∈ argmin m∈M P γ(t m , •). Then for any m ∈ M, with probability greater than 1p,

	∀θ ∈ (0; 1], (P ∀θ ∈ (0; 1],	(1 -θ)ℓ(s, t m ) (1 + θ) min m∈M	ℓ(s, t m ) + R(θ) .

nv -P )[γ(t m , •)γ(t m ′ , •)] θℓ(s, t m ) + θℓ(s, t m ′ ) + R(θ) . ∀θ ∈ (0; 1], (P nv -P )[γ(t m * , •)γ(t m , •)] θℓ(s, t m * ) + θℓ(s, t m ) + R(θ).

So by the union bound, with probability greater than 1 -|M|p, ∀θ ∈ (0; 1], ∀m ∈ M, (P nv -P )[γ(t m * , •)-γ(t m , •)] θℓ(s, t m * )+θℓ(s, t m )+R(θ).

  We need two other technical lemmas in the proof of Theorem 4.3. For any nonnegative, continuous convex function h over a Hilbert space H, and any λ ∈ R + , the elements of the regularization path, Proof By [3, Theorem 2.11], t λ exists for any λ ∈ R + . Moreover, it is unique by strong convexity of • 2 H . For a closed convex set C ⊂ H, let Π C denote the orthogonal projection onto C. Let µ > 0. The set {t : h(t) h(t µ )} is closed by continuity of h and convex by convexity of h. Moreover, for any t ∈ H such that h(t) h(t µ ), Therefore, t µ = Π {t:h(t) h(tµ)} (0). Let λ ∈ (0; µ). By definition of t λ , t µ ,

	Lemma B.4 t λ = argmin t∈H	h(t) + λ t 2 H	,
	satisfy, for any (λ, µ) ∈ R 2 such that 0 < λ µ,
		t λ -t µ	2 H	t λ	2 H -t µ	2 H .
	µ t µ	2 H	2 H H by definition of t µ . h(t µ ) -h(t) + µ t µ µ t 2
					1.1 + 2(a + y)) θn	1.7e -0.55 e -y
						e -y .

  3 are used. Recall also the notation g • t : (x, y) → g(t(x), y), for any g : R × R → R and t : X → R. Fix a training set D nt . Start with the following definition.

	where s λ = argmin t∈H P (c • t) + λ t 2 H . Furthermore, let
	y =	λ m n t 32κL 2 × sup (t 1 ,t 2 )∈H 2
	Definition B.6 For t 1 , t 2 ∈ H, let
		d(t 1 , t 2 ) = min	(37)

λ∈Λ t 1s λ H + t 1t 2 H ,

  1 , t 2 ) ∈ H be such that d(t 1 , t 2 ) r. Let λ ∈ Λ be such that t 1s λ H + t 1t 2 H r. By the triangle inequality, t 1 , t 2 ∈ B(s λ , r). Hence sup (t 1 ,t 2 ):d(t 1 ,t 2 ) r

  2 κ(2.6 + x + log|Λ|) λ m n t . Definition B.6 and Proposition B.6.1 together imply a uniform control on the empirical process thanks to the drift term λ m d(t 1 , t 2 ) 2 , whereas Proposition B.6.2 only gave a bound on an RKHS ball of fixed radius.

	On the same event, y 2.6 + x + log|Λ| by Definition B.6.
	Therefore, by Lemma A.7, E[ y] 3.6 + log|Λ|.

  By Proposition B.6.1, E[ y] 4 + log|Λ|. Since n v 100 e 4 , E[ y] log(n v |Λ|). As a result,

									2 κC	log(n v |Λ|) θ 4 λ m n 2 v	2	+80νLκ (45) log(n v |Λ|) y θ 2 λ m n v √ n t	.
	Therefore,
	R 2,1 (θ) 4 √	2ρ	log(n v |Λ|) θn v	+29 √	2ν 2 κC	log(n v |Λ|) θ 3 λ m n 2 v	2	+80 √	2νLκ	log(n v |Λ|) E[ y] θλ m n v √ n t	.
	R 2,1 (θ) 6ρ	log(n v |Λ|) θn v	+ 42ν 2 κC	log(n v |Λ|) v θ 3 λ m n 2	2	+ 114νLκ	log(n v |Λ|)

  As E[ y] log(n v |Λ|) by Proposition B.6.1, it follows thatR 2,2 (θ) 8L 2 κC log 2 (n v |Λ|) θ 2 λ m n 2 max {T 1 (θ), T 2 (θ), T 3 (θ)} since θ ∈ (0; 1] . Since E[ y] log(n v |Λ|) by Proposition B.6.1, R 2,3 (θ) 2 log(n v |Λ|) L 2 κC θλ m n 2 (θ) + 2T 3 (θ) since n v 100 and |Λ| 2 2.4 × max{T 1 , T 2 , T 3 } . B.4.4 Bound on R 2,4 (θ) = 1 nv θ + 2 1+log(|Λ|) +log 2 (|Λ|) θ E δ 2 w A , n vBy Equation (33) in Lemma B.5 with b = L κC λm , c = 5L 2 κ

	Since n v log(100) 100	100 and |Λ|	e √ nv , we have log(nv |Λ|) nv 2 log(n v |Λ|) θ	log(nv) nv .	√ nv ) + log(e nv (48)
	Therefore,
		R 2,3 (θ)	2 log(n v |Λ|) θn v	L 2 κC λ m n v	+ L 2 10κ E[ y] λ m √ n v n t	.
					v	+ 20L 2 κ	log θλ m n v 3 2 (n v |Λ|) √ n v n t
			2θ 2 log(n v |Λ|) 0.4T 2 √ T 2 (θ) + 20 √ n v T 3 (θ) y λm √ nt ,
		δ 2 ( w A , n v ) L 2 κC λ m n 2 v	+ L 2 10κ y λ m n v √ n t	.	2 κ λm √ √ nt , we have y (49)
	δ 2 w A , Since θ ∈ [0; 1], n v θ 2 4 n v and log(n v |Λ|) 100 and |Λ| 16L 2 κC θ + 2 1 + log(|Λ|) θ 2 log(n v |Λ|) log 2 (n v |Λ|) θ 4 λ m n 2 v 2, we have log(n v |Λ|) + 40L 2 κ log(n v |Λ|) y θ 2 λ m n v √ n t log(200) (46) . 5 θ by equation (48)
	v 2 log 2 (n v |Λ|) + 20L 2 κ log λ m n v 3 2 (n v |Λ|) . 5θ √ n t 8θT 2 (θ) + 20θT 3 (θ) Hence, by Equation (49),
	R 2,4 (θ) 28 × B.4.3 Bound on R 2,3 (θ) = 1 1, 4 log 2 (n v |Λ|) θn v nv θ + L 2 κC λ m n 2 v 2 1+log(|Λ|) + L 2 10κ E[ y] λ m n v √ n t θ E δ 2 w A , Since E[ y] log(n v |Λ|),	. √ n v
	By Equation (33) in Lemma B.5 with b = L κC λm , c = 5L 2 κ λm √ y √ nt , R 2,4 (θ) 1, 4 log 2 (n v |Λ|) L 2 κC θλ m n 3 v + 14L 2 κ log 5 2 (n v |Λ|) θλ m n 2 v √ n t
		δ 2 ( w A , 1, 4θ 2 √ n v ) L 2 κC λ m n v n v T 2 (θ) + 14 log(n v |Λ|) + L 2 10κ y λ m √ n v n t n v T 3 (θ) .	.	(47)

For any n,Ξ n × Ξ → R (ξ1:n, ξ) → γ(A(ξ1:n), ξ)is assumed to be measurable (with respect to the product σ-algebra on Ξ n+1 ).

Moreover, we have

which implies that R ′ (q) = 0. Hence, R reaches a minimum at q since R is convex.

Lemma C.2 Let g : R → R be a differentiable convex function that reaches a minimum at u * ∈ R. If there exists ε, δ such that

then for all (u, v) ∈ R 2 ,

Proof By integrating Equation (50),

By convexity of g, for any u u * + δ, g(u)g(u * ) h(u). Hence by Equation (51) with u = u * + δ and Equation (52),

The same argument applies to the convex function g(-•) with minimum -u * , which yields

Compatibility hypothesis (Comp 1 (c eps 0 , c eps ε )) Fix x ∈ X and let p x , F x be the pdf and cdf corresponding to the distribution Y given X = x. By assumption, p x is symmetric; s(x) can be chosen equal to the center of symmetry (recall that the contrast function here is γ(t, (x, y)) = c eps 0 (t(x), y) = |t(x) -y|, so any conditional median is a possible value for s(x)). Let

where ψ ε (z) = (|z|ε) + for any z ∈ R. Lemma C.1 applies, since p x is symmetric by assumption and ψ ε is even, convex and 1-Lipschitz.

Hence for any ε 0, R ε,x has a minimum at s(x) and is differentiable, with

Therefore, for any ε 0 and u ∈ R,

Now, assume that u s(x). By symmetry of p x around s(x), for all t 0,

Since p x is unimodal, its mode is s(x) and p x is non-increasing on [s(x); +∞). It follows from Equation (60) that for all u s(x) and t 0,

Therefore, by Eq. ( 59) and ( 61), for all u s(x) and ε 0,

. By integration, this implies that for all u s(x),

By Equation (57) and symmetry of p x , R ε,x and R 0,x are symmetric around s(x), hence inequality (62) is also valid when u s(x). Taking x = X, u = t(X) and integrating, we get

Hypothesis SC 4σ, [START_REF] Breiman | Random forests[END_REF] We first compute a lower bound on R 0,x . Let q x, 1

4

= sup{y|F x (y)

, which is the smallest determination of the interquartile range. By symmetry of p x around s(x), 1 2 q x, 1 4

2

, by symmetry of p x around s(x),

Hence, by Proposition 4.2 with a(x) = 1 σ(x) and b(x) = σ(x) 2 , (g, X, Y ) satisfies hypothesis SC 4σ,8 . In the proof of Theorem A.3, we used convexity of the risk to show that the risk of the average was less than the average of the risk. A property of this type also holds in the setting of classification, with the average replaced by the majority vote.

Conclusion

Proposition D.1 In the classification classification -see Example 2.1-, let ( f i ) 1 i V denote a finite family of functions X → Y and let f mv be some majority vote rule: ∀x ∈ X ,

Proof For any y ∈ Y, define η y :

We now fix some x ∈ X and define

On the other hand, by definition of f mv ,

Integrating over x (with respect to the distribution of X) yields the first bound.

For the second bound, fix x ∈ X and define C x (y) and C x as above. Let y ∈ Y be such that f mv (x) = y. Since y occurs less often than f mv (x) among f 1 (x), . . . , f V (x), we have |C x (y)| V /2. Therefore,

Hence, for any y ∈ Y,

Taking expectations with respect to (x, y) yields L(

We can now proceed with the proof of Theorem 4.5. Proof The proof relies on a result by [START_REF] Massart | Concentration Inequalities and Model Selection[END_REF]Eq. (8.60) .

Taking θ = 1/5 leads to the result.