Sylvain Arlot
email: sylvain.arlot@ens.fr

Model selection by resampling penalization

Keywords: AMS 2000 subject classifications: Primary 62G09; secondary 62G08, 62M20 Non-parametric statistics, resampling, exchangeable weighted bootstrap, model selection, penalization, non-parametric regression, adaptivity, heteroscedastic data, regressogram, histogram selection

In this paper, a new family of resampling-based penalization procedures for model selection is defined in a general framework. It generalizes several methods, including Efron's bootstrap penalization and the leave-one-out penalization recently proposed by Arlot (2008), to any exchangeable weighted bootstrap resampling scheme. In the heteroscedastic regression framework, assuming the models to have a particular structure, these resampling penalties are proved to satisfy a non-asymptotic oracle inequality with leading constant close to 1. In particular, they are asympotically optimal. Resampling penalties are used for defining an estimator adapting simultaneously to the smoothness of the regression function and to the heteroscedasticity of the noise. This is remarkable because resampling penalties are general-purpose devices, which have not been built specifically to handle heteroscedastic data. Hence, resampling penalties naturally adapt to heteroscedasticity. A simulation study shows that resampling penalties improve on V -fold cross-validation in terms of final prediction error, in particular when the signal-to-noise ratio is not large.

Introduction

In the last decades, model selection has received much interest. When the final goal is prediction, model selection can be seen more generally as the question of choosing between the outcomes of several prediction algorithms. With such a general formulation, a natural and classical answer is the following. First, estimate the prediction error for each model or algorithm; second, select the model minimizing this criterion. Model selection procedures mainly differ on the way of estimating the prediction error.

The empirical risk, also known as the apparent error or the resubstitution error, is a natural estimator of the prediction error. Nevertheless, minimizing the empirical risk can fail dramatically: the empirical risk is strongly biased for models involving a number of parameters growing with the sample size because the same data are used for building predictors and for comparing them.

In order to correct this drawback, cross-validation methods have been introduced [START_REF] Allen | The relationship between variable selection and data augmentation and a method for prediction[END_REF][START_REF] Stone | Cross-validatory choice and assessment of statistical predictions[END_REF], relying on a data-splitting idea for estimating the prediction error with much less bias. In particular, V -fold cross-validation (VFCV, [START_REF] Geisser | The predictive sample reuse method with applications[END_REF]) is a popular procedure in practice because it is both general and computationally tractable. A large number of papers exist about the properties of cross-validation methods, showing that they are efficient for a suitable choice of the way data are split (or V for VFCV). Asymptotic optimality results for leave-one-out crossvalidation (that is the V = n case) in regression have been proved for instance by Li [START_REF] Li | Asymptotic optimality for C p , C L , cross-validation and generalized cross-validation: discrete index set[END_REF] and by Shao [START_REF] Shao | An asymptotic theory for linear model selection[END_REF]. However, when V is fixed, VFCV can be asymptotically suboptimal, as showed by Arlot [START_REF] Arlot | V -fold cross-validation improved: V -fold penalization[END_REF]. We refer to the latter paper for more references on cross-validation methods, including the small amount of available non-asymptotic results.

Another way to correct the empirical risk for its bias is penalization. In short, penalization selects the model minimizing the sum of the empirical risk and of some measure of complexity1 of the model (called penalty); see FPE [START_REF] Akaike | Statistical predictor identification[END_REF], AIC [START_REF] Akaike | Information theory and an extension of the maximum likelihood principle[END_REF], Mallows' C p or C L [START_REF] Mallows | Some comments on C p[END_REF]. Model selection can target two different goals. On the one hand, a procedure is efficient (or asymptotically optimal) when its quadratic risk is asymptotically equivalent to the risk of the oracle. On the other hand, a procedure is model consistent when it selects the smallest true model asymptotically with probability one. This paper deals with efficient procedures, without assuming the existence of a true model. Therefore, the ideal penalty for prediction is the difference between the prediction error (the "true risk") and the empirical risk; penalties should be data-dependent estimates of the ideal penalty.

Many penalties or complexity measures have been proposed. Consider for instance regression and least-squares estimators on finite-dimensional vector spaces (the models). When the design is fixed and the noise-level constant equal to σ, Mallows' C p penalty [START_REF] Mallows | Some comments on C p[END_REF] is equal to 2n -1 σ 2 D for a model of dimension D and it can be modified according to the number of models [START_REF] Birgé | Gaussian model selection[END_REF][START_REF] Sauvé | Histogram selection in non Gaussian regression[END_REF]. Mallows' C p -like penalties satisfy some optimality properties [START_REF] Shibata | An optimal selection of regression variables[END_REF][START_REF] Li | Asymptotic optimality for C p , C L , cross-validation and generalized cross-validation: discrete index set[END_REF][START_REF] Baraud | Model selection for regression on a random design[END_REF][START_REF] Birgé | Minimal penalties for Gaussian model selection[END_REF] but they can fail when the data are heteroscedastic [START_REF] Arlot | Suboptimality of penalties proportional to the dimension for model selection in heteroscedastic regression[END_REF] because these penalties are linear functions of the dimension of the models.

In the binary supervised classification framework, several penalties have been proposed. First, VC-dimension-based penalties have the drawback of being independent of the underlying measure, so that they are adapted to the worst case. Second, global Rademacher complexities [START_REF] Koltchinskii | Rademacher penalties and structural risk minimization[END_REF][START_REF] Peter | Model selection and error estimation[END_REF] (generalized by Fromont with resampling ideas [START_REF] Fromont | Model selection by bootstrap penalization for classification[END_REF]) take into account the distribution of the data, but they are still too large to achieve fast rates of estimation when the margin condition [START_REF] Mammen | Smooth discrimination analysis[END_REF] holds. Third, local Rademacher complexities [START_REF] Peter | Local Rademacher complexities[END_REF][START_REF] Koltchinskii | Local Rademacher complexities and oracle inequalities in risk minimization[END_REF] are tighter estimates of the ideal penalty, but their computational cost is heavy and they involve huge (and sometimes unknown) constants. Therefore, easy-to-compute penalties that can achieve fast rates are still needed.

All the above penalties have serious drawbacks making them less often used in practice than cross-validation methods: AIC and Mallows' C p rely on strong assumptions (such as homoscedasticity of the data and linearity of the models) and some mainly asymptotic arguments; VC-dimension-based penalties and global Rademacher complexities are far too pessimistic; local Rademacher complexities are computationally intractable, and their calibration is a serious issue. Another approach for designing penalties in the general framework may not suffer from these drawbacks: the resampling idea.

Efron's resampling heuristics [START_REF] Efron | Bootstrap methods: another look at the jackknife[END_REF] was first stated for the bootstrap, then generalized to the exchangeable weighted bootstrap by Mason and Newton [START_REF] Mason | A rank statistics approach to the consistency of a general bootstrap[END_REF] and by Praestgaard and Wellner [START_REF] Praestgaard | Exchangeably weighted bootstraps of the general empirical process[END_REF]. In short, according to the resampling heuristics, the distribution of any function of the (unknown) distribution of the data and the sample can be estimated by drawing "resamples" from the initial sample. In particular, the resampling heuristics can be used to estimate the variance of an estimator [START_REF] Efron | Bootstrap methods: another look at the jackknife[END_REF], a prediction error [START_REF] Wu | Jackknife, bootstrap and other resampling methods in regression analysis[END_REF][START_REF] Efron | Improvements on cross-validation: the .632+ bootstrap method[END_REF] or the ideal penalty (using the bootstrap [START_REF] Efron | Estimating the error rate of a prediction rule: improvement on cross-validation[END_REF][START_REF] Efron | How biased is the apparent error rate of a prediction rule?[END_REF][START_REF] Ishiguro | Bootstrapping log likelihood and EIC, an extension of AIC[END_REF], the M out of n bootstrap2 [START_REF] Shao | Bootstrap model selection[END_REF] or a V -fold subsampling scheme [START_REF] Arlot | V -fold cross-validation improved: V -fold penalization[END_REF]). The asymptotic optimality of Efron's bootstrap penalty for selecting among maximum likelihood estimators has been proved by Shibata [START_REF] Shibata | Bootstrap estimate of Kullback-Leibler information for model selection[END_REF]. Note also that global and local Rademacher complexities are using an i.i.d. Rademacher resampling scheme for estimating different upper bounds on the ideal penalty and Fromont's penalties [START_REF] Fromont | Model selection by bootstrap penalization for classification[END_REF] generalize the global Rademacher complexities to the exchangeable weighted bootstrap.

The first goal of this paper is to define and study general-purpose penalties, that is penalties well-defined in almost every framework and performing reasonably well in most of them, including regression and classification. The main interest of such penalties would be the ability to solve difficult problems (for instance heteroscedastic data, a non-smooth regression function or the fact that the oracle model achieves fast rates of estimation) without knowing them in advance. From the practical point of view, such a property is crucial.

To this aim, the resampling heuristics with the general exchangeable weighted bootstrap is used for estimating the ideal penalty (Section 2). This defines a wide family of model selection procedures, called "Resampling Penalization" (RP), which includes Efron's and Shao's penalization methods [START_REF] Efron | Estimating the error rate of a prediction rule: improvement on cross-validation[END_REF][START_REF] Shao | Bootstrap model selection[END_REF] as well as the leave-one-out penalization defined in [START_REF] Arlot | V -fold cross-validation improved: V -fold penalization[END_REF]. To our knowledge, it has never been proposed with such general resampling schemes, so that the RP family contains a wide range of new procedures. Note that RP is well-defined in a general framework, including regression and classification, but also many other application fields (Section 7.2). Even if the main results are proved in the leastsquares regression framework only, we obviously do not mean that RP should be restricted to this framework.

In this paper, the model selection efficiency of RP is studied with a unified approach for all the exchangeable resampling schemes. Therefore, comparing bootstrap with subsampling is quite straightforward (Section 5) which is not common in the resampling literature (except a few asymptotic results, see Barbe and Bertail [15]).

The point of view used in the paper is non-asymptotic, which has two major implications. First, non-asymptotic results allow to consider collections of models depending on the sample size n: in practice, it is usual to increase the number of explanatory variables with the number of observations. Considering models with a large number of parameters (for instance of order n α for some α > 0) is also particularly useful for designing adaptive estimators of a function which is only assumed to belong to some Hölderian ball (see Section 3.2). Thus, the non-asymptotic point of view allows not to assume that the regression function is described with a small number of parameters.

Second, several practical problems are "non-asymptotic" in the sense that the signal-to-noise ratio is low. As noticed in [START_REF] Arlot | V -fold cross-validation improved: V -fold penalization[END_REF], with such data, VFCV can have serious drawbacks which can be naturally fixed by using the flexibility of penalization procedures. It is worth noting that such a non-asymptotic approach is not common in the model selection literature and few non-asymptotic results exist on general resampling methods.

Another important point is that the framework of the paper includes several kinds of heteroscedastic data. The observations (X i , Y i ) 1≤i≤n are only assumed to be i.i.d. with

Y i = s(X i ) + σ(X i )ǫ i ,
where s : X → R is the (unknown) regression function, σ : X → R is the (unknown) noise-level and ǫ i has zero mean and unit variance conditionally on X i . In particular, the noise-level σ(X) can strongly depend on X and the distribution of ǫ i can depend on X i . Such data are generally considered as difficult to handle because no information on σ is known, making irregularities of the signal difficult to distinguish from noise. As already mentioned, simple model selection procedures such as Mallows' C p can fail in this framework [START_REF] Arlot | Suboptimality of penalties proportional to the dimension for model selection in heteroscedastic regression[END_REF] whereas it is natural to expect that resampling methods are robust to heteroscedasticity. In this article, both theoretical and simulation results confirm this fact (Sections 3 and 5).

The two main results of the paper are stated in Section 3. First, making mild assumptions on the distribution of the data, a non-asymptotic oracle in-equality for RP is proved with leading constant close to 1 (Theorem 1). It holds for several kinds of resampling schemes (including bootstrap, leave-oneout, half-subsampling and i.i.d. Rademacher weighted bootstrap) and implies the asymptotic optimality of RP, even when the data are highly heteroscedastic. For proving such a result, each model is assumed to be the vector space of piecewise constant functions (histograms) on some partition of the feature space. This is indeed a restriction, but we conjecture that it is mainly technical and that RP remains efficient in a much more general framework (see Section 7.2). Moreover, studying extensively the toy model of histograms allows to derive precise heuristics for the general framework. A major goal of the paper is to help practicioners who would like to know how to use resampling for performing model selection (see in particular Sections 6 and 7.3).

Second, RP is used to build an estimator simultaneously adaptive to the smoothness of the regression function (assuming that s is α-Hölderian for some unknown α ∈ (0, 1]) and to the unknown noise-level σ ( • ) (Theorem 2). This result may seem surprising since RP has never been designed specifically for such a purpose. We interpretate Theorem 2 as a confirmation that RP is naturally adaptive and should work well in several other difficult frameworks.

Several results similar to Theorem 1 exist in the literature for other procedures such as Mallows' C p (with homoscedastic data only), VFCV and leave-oneout cross-validation. Moreover, there exist several minimax adaptive estimators for heteroscedastic data with a smooth noise-level, for instance [START_REF] Efromovich | Sharp-optimal and adaptive estimation for heteroscedastic nonparametric regression[END_REF][START_REF] Galtchouk | Adaptive asymptotically efficient estimation in heteroscedastic nonparametric regression via model selection[END_REF], and the regression function and the noise level can be estimated simultaneously [START_REF] Gendre | Simultaneous estimation of the mean and the variance in heteroscedastic Gaussian regression[END_REF]. In comparison, the interest of RP is both its generality (contrary to Mallows' C p and specific adaptive estimators) and its flexibility (contrary to VFCV, see [START_REF] Arlot | V -fold cross-validation improved: V -fold penalization[END_REF]), as detailed in Section 7.1.

A simulation study is conducted in Section 5 with small sample sizes. RP is showed to be competitive with Mallows' C p for "easy" problems, and much better for some harder ones (for instance with a variable noise-level). Moreover, a well-calibrated RP yields almost always better model selection performance than VFCV. Therefore, RP can be of great interest in situations where no a priori information is known about the data. RP can deal with difficult problems, and compete with procedures that are fitted for easier problems. In short, RP is an efficient alternative to VFCV. This article is organized as follows. The framework and the Resampling Penalization (RP) family of procedures are defined in Section 2. The main results are stated in Section 3. The differences between the resampling weights are investigated in Section 4. Then, a simulation study is presented in Section 5. Practical issues concerning the implementation of RP are considered in Section 6. RP is compared to other penalization methods in Section 7.1 and the extension of RP to the general framework is discussed in Section 7.2. Finally, Section 8 is devoted to the proofs. Some additional material (other simulation experiments and proofs) is available in a technical Appendix [START_REF] Arlot | Technical appendix to "Model selection by resampling penalization[END_REF].

The Resampling Penalization procedure

In order to simplify the presentation, we choose to focus on the particular framework of least-squares regression on models of piecewise constant functions (histograms), which is the framework of the main results of Section 3 and the simulation study of Section 5.

Nevertheless, the RP family is a general-purpose method which can easily be defined in the general prediction framework. The main interest of the histogram framework is to provide general heuristics about RP, so that the practicioner can make the best possible use of RP in the general framework. A discussion on RP in the general prediction framework is provided in Section 7.2, including a general definition of RP.

Framework

Suppose we observe some data (X 1 , Y 1 ), . . . , (X n , Y n ) ∈ X × R, independent with common distribution P , where the feature space X is typically a compact set of R k . Let s denote the regression function, that is s

(x) = E [ Y | X = x ]. Then, Y i = s(X i ) + σ(X i )ǫ i (1)
where σ : X → R is the heteroscedastic noise-level and ǫ i are i.i.d. centered noise terms; the ǫ i possibly depend on X i , but they are have zero mean and unit variance conditionally on X i . The goal is to predict Y given X where (X, Y ) ∼ P is independent of the data. The quality of a predictor t : X → R is measured by the quadratic prediction loss P γ(t) := E (X,Y ) [ γ(t, (X, Y )) ], where (X, Y ) ∼ P and γ(t, (x, y)) := ( t(x) -y ) 2 is the least-squares contrast. Since P γ(t) is minimal when t = s, the excess loss is defined as

ℓ ( s, t ) := P γ ( t ) -P γ ( s ) = E (X,Y ) (t(X) -s(X)) 2 .
Given a particular set of predictors S m (called a model), the best predictor over S m is defined as

s m := arg min t∈Sm { P γ(t) } ,
with its empirical counterpart

s m := arg min t∈Sm { P n γ(t) }
(when it exists and is unique) where

P n = n -1 n i=1 δ (Xi,Yi)
is the empirical distribution. The estimator s m is the well-known empirical risk minimizer, also called least-squares estimator since γ is the least-squares contrast.

In this article, we mainly consider histogram models S m , that is of the following form. Let ( I λ ) λ∈Λm be some fixed partition of X . Then, S m denotes the set of functions X → R which are constant over I λ for every λ ∈ Λ m ; S m is a vector space of dimension D m = Card(Λ m ), spanned by the family (1 I λ ) λ∈Λm . The empirical risk minimizer s m over an histogram model S m is often called a regressogram.

Explicit computations are easier with regressograms because (1 I λ ) λ∈Λm is an orthogonal basis of L 2 (µ) for any probability measure µ on X . In particular,

s m = λ∈Λm β λ 1 I λ and s m = λ∈Λm β λ 1 I λ ,
where

β λ := E P [ Y | X ∈ I λ ] , β λ := 1 n p λ Xi∈I λ Y i and p λ := P n (X ∈ I λ ).
Note that s m is uniquely defined if and only if each I λ contains at least one of the X i , that is min λ∈Λm p λ > 0.

Let us assume that a collection of models (S m ) m∈Mn is given. Model selection consists in selecting some data-dependent m ∈ M n such that ℓ s, s m is as small as possible. General penalization procedures can be described as follows.

Let pen : M n → R + be some penalty function, possibly data-dependent, and define m ∈ arg min

m∈Mn { P n γ ( s m ) + pen(m) } . (2)
Since the goal is to minimize the loss P γ ( s m ), the ideal penalty is

pen id (m) := (P -P n )γ ( s m ) , (3)
and we would like pen(m) to be as close to pen id (m) as possible for every m ∈ M n . In the histogram framework, note that s m is not uniquely defined when min λ∈Λm p λ = 0; then, we consider that the model S m cannot be chosen, which is formally equivalent to add +∞1 min λ∈Λm p λ =0 to the penalty pen(m). When S m is the histogram model associated with some partition ( I λ ) λ∈Λm of X , the ideal penalty (3) can be computed explicitly:

pen id (m) = (P -P n )γ(s m ) + P ( γ ( s m ) -γ ( s m ) ) + P n ( γ ( s m ) -γ ( s m ) ) = (P -P n )γ(s m ) + λ∈Λm p λ β λ -β λ 2 + p λ β λ -β λ 2 (4)
where p λ := P ( X ∈ I λ ). The ideal penalty pen id (m) is unknown because it depends on the true distribution P ; therefore, resampling is a natural method for estimating pen id (m).

The resampling heuristics

Let us recall briefly the resampling heuristics, which has been introduced by Efron [START_REF] Efron | Bootstrap methods: another look at the jackknife[END_REF] in the context of variance estimation. Basically, it says that one can mimic the relationship between P and P n by drawing a n-sample with common distribution P n , called the "resample"; let P W n denote the empirical distribution of the resample. Then, the conditional distribution of the pair (P n , P W n ) given P n should be close to the distribution of the pair (P, P n ). Hence, the expectation of any quantity of the form F (P, P n ) can be estimated by E W F (P n , P W n ) . The expectation E W [ • ] means that we integrate with respect to the resampling randomness only. Let us emphasize that pen id (m) has the form F (P, P n ).

Later on, this heuristics has been generalized to other resampling schemes, with the exchangeable weighted bootstrap [START_REF] Mason | A rank statistics approach to the consistency of a general bootstrap[END_REF][START_REF] Praestgaard | Exchangeably weighted bootstraps of the general empirical process[END_REF]. The empirical distribution of the resample then has the general form

P W n := 1 n n i=1 W i δ (Xi,Yi)
where W ∈ R n is an exchangeable3 weight vector independent of the data and such that ∀i, E W [ W i ] = 1. In this article, W is also assumed to satisfy ∀i,

W i ≥ 0 a.s. and E W [W 2 i ] < ∞.
We mainly consider the following weights, which include the more classical resampling schemes:

1. Efron (M ), M ∈ N\{0} (Efr): ((M/n)W i ) 1≤i≤n is a multinomial vector with parameters (M ; n -1 , . . . , n -1 ). A classical choice is M = n. 2. Rademacher (p), p ∈ (0; 1) (Rad): (pW i ) are independent, with a Bernoulli (p) distribution. A classical choice is p = 1/2. 3. Poisson (µ), µ ∈ (0, ∞) (Poi): (µW i ) are independent, with a Poisson (µ) distribution. A classical choice is µ = 1. 4.
Random hold-out (q), q ∈ {1, . . . , n} (Rho): W i = (n/q)1 i∈I where I is a uniform random subset of cardinality q of {1, . . . , n}. A classical choice is q = n/2. 5. Leave-one-out (Loo) = Rho (n -1).

In the following, Efr, Rad, Poi, Rho and Loo respectively denote the above resampling weight vector distributions with the "classical" value of the parameter. Remark 1. The above terminology explicitly links the weight vector distributions with some classical resampling schemes. See [START_REF] Mason | A rank statistics approach to the consistency of a general bootstrap[END_REF][START_REF] Hall | On general resampling algorithms and their performance in distribution estimation[END_REF][START_REF] Van Der | Weak convergence and empirical processes[END_REF] for more details about classical resampling weight names, as well as other classical examples.

• The name "Efron" comes from the classical choice M = n for which Efron weights actually are the bootstrap weights. When M < n, Efron(M ) is the M out of n bootstrap, used for instance by Shao [START_REF] Shao | Bootstrap model selection[END_REF]. [START_REF] Van Der | Weak convergence and empirical processes[END_REF]Chapter 3.5] and [START_REF] Fromont | Model selection by bootstrap penalization for classification[END_REF]). They are known to be efficient for estimating several non-smooth functionals (see [START_REF] Barbe | The weighted bootstrap[END_REF]Chapter 3] and [START_REF] Mammen | When does bootstrap work? Asymptotic results and simulations[END_REF]Section 1.4]). • The Random hold-out (q) weights can also be called "delete-(n -q) jackknife", as well as the Leave-one-out weights also refer to the jackknife (sometimes called cross-validation). They are both resampling schemes without replacement [66, Example 3.6.14], more often called subsampling weights (see for instance the book by Politis, Romano and Wolf [START_REF] Politis | Subsampling. Springer Series in Statistics[END_REF] on subsampling). They are close to the idea of splitting the data into a training set and a validation set (for instance, leave-one-out, hold-out and crossvalidation). Indeed, if one defines the training set as

{ (X i , Y i ) s.t. W i = 0 }
and the validation set as its complement, there is a one-to-one correspondence between subsampling weights and data splitting.

Resampling Penalization

Applying directly the resampling heuristics of Section 2.2 for estimating the ideal penalty (3), we would get the penalty

E W P n γ s W m -P W n γ s W m , (5)
where s W m := arg min

t∈Sm P W n γ(t) = λ∈Λm β W λ 1 I λ , β W λ := 1 n p W λ Xi∈I λ W i Y i , p W λ := P W n (X ∈ I λ ) = p λ W λ and W λ := 1 n p λ Xi∈I λ W i .
Two problems have to be solved before defining properly the Resampling Penalization procedure. Here, we focus on the histogram framework; the general framework will be considered in Section 7.2. First, (5) is not well-defined because s W m is not unique if min λ∈Λm p W λ = 0. Hence, even when min λ∈Λm p λ > 0, the problem occurs as soon as W λ = 0 for some λ ∈ Λ m , which has a positive probability (except when D m = 1) for most of the resampling schemes since P W ( ∀i ≥ 2, W i = 0 ) > 0. In order to make [START_REF] Arcones | On the bootstrap of M -estimators and other statistical functionals[END_REF] well-defined, let us rewrite the resampling penalty as the resampling estimate of (4), that is

E W P n γ s W m -P W n γ s W m = p 0 (m) + p 1 (m) + p 2 (m)
where

p 0 (m) := E W (P n -P W n )γ( s m ) = 1 n n i=1 ( E W [ 1 -W i ] γ ( s m ; (X i , Y i ) ) ) = 0
D(W ) Efr(M ) Rad(p) Poi(µ) Rho(q) Loo C W M/n p/(1 -p) µ q/(n -q) n -1 because E W [W i ] = 1 for every i, p 1 (m) := λ∈Λm E W p λ β W λ -β λ 2 and p 2 (m) := λ∈Λm E W p W λ β W λ -β λ 2 . With the convention p W λ ( β W λ -β λ ) 2 = 0 when p W λ = 0, p 2 (m) is well-defined since β W
λ is well-defined when p W λ > 0. It remains to define properly p 1 (m). We suggest to replace the expectation over all the resampling weights by an expectation conditional on W λ > 0, separately for each m ∈ M n and λ ∈ Λ m , which ensures that we only remove a small proportion of the possible resampling weights. To summarize, ( 5) is replaced by

λ∈Λm E W p λ β W λ -β λ 2 W λ > 0 + E W p W λ β W λ -β λ 2 . (6)
Second, ( 6) is strongly biased as an estimate of pen id when var(W 1 ) is small, because P W n is then much closer to P n than P n is close to P . Assuming the S m to be histogram models, we will prove in Section 3.4.1 (see Propositions 1 and 2) that the bias can be corrected by multiplying (6) by a constant C W which only depends on the distribution of W . The values of C W for the classical weights are reported in Table 1. Remark that C W = 1 in the bootstrap case (Efr), as well as for Rad, Poi and Rho.

We are now in position to define properly the Resampling Penalization (RP) procedure for selecting among histogram models. See Section 7.2 for the definition of RP in the general framework (Procedure 3).

Procedure 1 (Resampling Penalization for histograms).

1. Replace M n by

M n = m ∈ M n s.t. min λ∈Λm {n p λ } ≥ 3 .
2. Choose a resampling scheme D(W ). 3. Choose a constant C ≥ C W where C W is defined in Table 1. 4. Define, for each m ∈ M n , the resampling penalty pen(m) as

C λ∈Λm E W p λ β W λ -β λ 2 W λ > 0 + E W p W λ β W λ -β λ 2 . (7)
5. Select m ∈ arg min m∈ Mn { P n γ ( s m ) + pen(m) }.

Remark 2. 1. At step 1, we remove more models than those for which s m is not uniquely defined. When n p λ = 1 for some λ ∈ Λ m , estimating the quality of estimation of β λ with only one data-point is hopeless with no assumption on the noise-level σ. The reason why we remove also models for which min λ∈Λm { n p λ } = 2 is that the oracle inequalities of Section 3 require it for some of the weights; nevertheless, such models generally have a poor prediction performance, so that step 1 is reasonable. 2. At step 3, C can be larger than C W because overpenalizing can be fruitful from the non-asymptotic point of view, in particular when the sample size n is small or the noise level σ is large. The simulation study of Section 5 provides experimental evidence for this fact (see also Section 6.3.2). 3. RP (Procedure 1) generalizes several model selection procedures. With a bootstrap resampling scheme (Efr) and C = 1, RP is Efron's bootstrap penalization [START_REF] Efron | Estimating the error rate of a prediction rule: improvement on cross-validation[END_REF], which has also been called EIC in the log-likelihood framework [START_REF] Ishiguro | Bootstrapping log likelihood and EIC, an extension of AIC[END_REF]. With an M out of n bootstrap resampling scheme (Efr(M )) and C = 1, RP has been proposed and studied by Shao [START_REF] Shao | Bootstrap model selection[END_REF] in the context of model identification. Note that C W = 1 for Efr(M ) weights if M = n; this crucial point will be discussed in Section 3.4.1. RP with a (non-exchangeable) V -fold subsampling scheme has also been proposed recently in [START_REF] Arlot | V -fold cross-validation improved: V -fold penalization[END_REF]. 4. When W are the "leave-one-out" weights, RP is not the classical leaveone-out model selection procedure. Nevertheless, according to [START_REF] Arlot | V -fold cross-validation improved: V -fold penalization[END_REF], when C = n -1, it is identical to Burman's n-fold corrected cross-validation [START_REF] Burman | A comparative study of ordinary cross-validation, v-fold cross-validation and the repeated learning-testing methods[END_REF], hence close to the uncorrected one.

Main results

In this section, we state some non-asymptotic properties of Resampling Penalization (Procedure 1) for model selection. First, Theorem 1 is an oracle inequality with leading constant close to 1. In particular, Theorem 1 implies the asymptotic optimality of RP. Second, Theorem 2 is an adaptivity result for an estimator built upon RP, when the regression function belongs to some Hölderian ball. A remarkable point is that both results remain valid under mild assumptions on the distribution of the noise, which can be non-Gaussian and highly heteroscedastic.

Throughout this section, we assume the existence of non-negative constants α M , c M , c rich such that:

(P1) Polynomial size of M n : Card(M n ) ≤ c M n αM . (P2) Richness of M n : ∃m 0 ∈ M n s.t. D m0 ∈ [ √ n; c rich √ n ]. (P3)
The weight vector W is chosen among Efr, Rad, Poi, Rho and Loo (defined in Section 2.2, with the classical value of their parameter).

(P1) is a natural restriction since RP plugs an estimator of the ideal penalty into (2). When Card(M n ) is larger, say proportional to e an for some a > 0, Birgé and Massart [START_REF] Birgé | Minimal penalties for Gaussian model selection[END_REF] proved that penalties estimating the ideal penalty cannot be asymptotically optimal. (P2) is merely technical. (P3) can be relaxed, as explained in Section 4.2.

Oracle inequality

Theorem 1. Assume that the data (X i , Y i ) 1≤i≤n satisfy the following:

(Ab) Bounded data: Y i ∞ ≤ A < ∞.
(An) Noise-level bounded from below: σ(X i ) ≥ σ min > 0 a.s.

(Ap) Polynomially decreasing bias: there exist

β 1 ≥ β 2 > 0 and C + b , C - b > 0 such that ∀m ∈ M n , C - b D -β1 m ≤ ℓ ( s, s m ) ≤ C + b D -β2 m . (Ar X ℓ )
Lower regularity of the partitions for D(X):

there exists c X r,ℓ > 0 such that ∀m ∈ M n , D m min λ∈Λm p λ ≥ c X r,ℓ .
Let m be defined by Procedure 1 (under restrictions (P1 -3), with C = C W ). Then, there exist a constant K 1 > 0 and an absolute sequence ε n converging to zero at infinity such that, with probability at least 1 -

K 1 n -2 , ℓ s, s m ≤ ( 1 + ε n ) inf m∈Mn { ℓ ( s, s m ) } . (8)
Moreover,

E ℓ s, s m ≤ ( 1 + ε n ) E inf m∈Mn { ℓ ( s, s m ) } + A 2 K 1 n 2 . ( 9
)
The constant K 1 may depend on constants in (Ab), (An), (Ap), (Ar X ℓ ) and (P1 -3) but not on n. The term ε n is smaller than ( ln(n) )

-1/5 ; ε n can also be made smaller than n -δ for any 0 < δ < δ 0 (β 1 , β 2 ) at the price of enlarging K 1 .

Theorem 1 is proved in Section 8.3. The non-asymptotic oracle inequality (8) implies that Procedure 1 is a.s. asymptotically optimal in this framework if lim n→∞ (C/C W ) = 1. When W are Efr weights, the asymptotic optimality of RP was proved by Shibata [START_REF] Shibata | Bootstrap estimate of Kullback-Leibler information for model selection[END_REF] for selecting among maximum likelihood estimators, assuming that the distribution P belongs to some parametric family of densities (see also Remark 6 in Section 3.4.1).

Resampling Penalization yields an estimator with an excess loss as small as the one of the oracle without requiring any knowledge about P such as the smoothness of s or the variations of the noise-level σ. Therefore, RP is a naturally adaptive procedure. Note that [START_REF] Arlot | Technical appendix to "Model selection by resampling penalization[END_REF] is even stronger than an adaptivity result because of the leading constant close to one, whereas adaptive estimators only achieve the correct estimation rate up to a possibly large absolute constant. Hence, one can expect that an estimator obtained with RP and a well chosen collection of models is almost optimal.

We now comment on the assumptions of Theorem 1:

1. The constant C can differ from C W . For instance, when a constant η > 1 exists such that C ∈ [ C W ; ηC W ], the oracle inequalities ( 8) and ( 9) hold with leading constant 2η -1 + ε n instead of 1 + ε n . 2. (Ab) and (An) are rather mild and neither A nor σ min need to be known by the statistician. In particular, quite general heteroscedastic noises are allowed; (Ab) and (An) can even be relaxed as explained in Section 3.3.2. 3. When X has a lower bounded density with respect to Leb, (Ar X ℓ ) is satisfied for "almost piecewise regular" histograms, including all those considered in the simulation study of Section 5. 4. The upper bound in (Ap) holds with β = 2αk -1 when (I λ ) λ∈Λm is regular on X ⊂ R k and s is α-Hölderian with α > 0. The lower bound in (Ap) is discussed extensively in Section 3.3.1.

An adaptive estimator

A natural framework in which Theorem 1 can be applied is when X is a compact subset of R k , X has a lower bounded density with respect to the Lebesgue measure and s is α-Hölderian with α ∈ (0, 1]. Indeed, the latter condition ensures that regular histograms can approximate s well. In this subsection, we show that Resampling Penalization can be used to build an estimator adaptive to the smoothness of s in this framework. We first define the estimator. For the sake of simplicity4 , X is assumed to be a closed ball of (R k , • ∞ ), say [0, 1] k .

Procedure 2 (Resampling Penalization with regular histograms). For every T ∈ N\ { 0 }, let S m(T ) be the model of regular5 histograms with T k bins, that is the histogram model associated with the partition

( I λ ) λ∈Λ m(T ) := k i=1 j i T ; j i + 1 T 0≤j1,...,j k ≤T -1
.

Then, define (S m ) m∈Mn := S m(T ) 1≤T ≤n

(Ab) Bounded data: Y i ∞ ≤ A < ∞.
(An) Noise-level bounded from below: σ(X i ) ≥ σ min > 0 a.s. (Ad ℓ ) Density bounded from below:

∃c min X > 0, ∀I ⊂ X , P (X ∈ I) ≥ c min X Leb(I).
(Ah) Hölderian regression function: there exist α ∈ (0; 1] and R > 0 such that

s ∈ H(α, R) that is ∀x 1 , x 2 ∈ X , |s(x 1 ) -s(x 2 )| ≤ R x 1 -x 2 α ∞ .
Let s be the estimator defined by Procedure 2 and σ max := sup X |σ| ≤ 2A. Then, there exist positive constants K 2 and K 3 such that,

E [ ℓ ( s, s ) ] ≤ K 2 R 2k 2α+k n -2α 2α+k σ 4α 2α+k max + K 3 A 2 n -2 . ( 10
)
If moreover the noise-level is smooth, that is

(Aσ) σ is piecewise K σ -Lipschitz with at most J σ jumps,
then, assumption (An) can be removed and (10) holds with σ max replaced by

σ L 2 (Leb) := [(Leb(X )) -1 X σ 2 (t)dt] 1/2
. For both results, K 2 may only depend on α and k. The constant K 3 may only depend on k, A, c min X , R, α (and σ min for (10); K σ and J σ for the latter result). Theorem 2 is proved in Section 8.5. The upper bounds given by Theorem 2 coincide with several classical minimax lower bounds on the estimation of functions in H(α, R) with α ∈ (0, 1], up to an absolute constant. In the homoscedastic case, lower bounds have been proved by Stone [START_REF] Stone | Optimal rates of convergence for nonparametric estimators[END_REF] and generalized by several authors among which Korostelev and Tsybakov [START_REF] Korostelëv | Minimax theory of image reconstruction[END_REF] and Yang and Barron [START_REF] Yang | Information-theoretic determination of minimax rates of convergence[END_REF]. Up to a multiplicative factor independent of n, R and σ the best achievable rate is R

2k 2α+k n -2α 2α+k σ 4α 2α+k .
Hence, [START_REF] Arlot | Some nonasymptotic results on resampling in high dimension, I: confidence regions[END_REF] shows that Procedure 2 achieves the right estimation rate in terms of n, R and σ, without using the knowledge of α, R or σ. Moreover, [START_REF] Arlot | Some nonasymptotic results on resampling in high dimension, I: confidence regions[END_REF] still holds in a wide heteroscedastic framework, without using any information on the noise-level σ(•). Then, up to a multiplicative constant independent of n and R (but possibly of the order of some power of σ max /σ min ), the upper bound [START_REF] Arlot | Some nonasymptotic results on resampling in high dimension, I: confidence regions[END_REF] is the best possible estimation rate.

Minimax lower bounds proved in the heteroscedastic case (see for instance [START_REF] Efromovich | Sharp-optimal and adaptive estimation for heteroscedastic nonparametric regression[END_REF][START_REF] Galtchouk | Adaptive asymptotically efficient estimation in heteroscedastic nonparametric regression via model selection[END_REF] and references therein) show that when k = α = 1 and the noise-level is smooth enough, the best achievable estimation rate depends on σ through the multiplicative factor σ 4α 2α+k L 2 (Leb) . Therefore, the upper bound given by Theorem 2 under assumption (Aσ) is tight, even through its dependence on the noise-level. Up to our best knowledge, such an upper bound had never been obtained when α ∈ (0, 1) and k > 1, even with estimators using the knowledge of α, σ and R.

Theorem 2 shows that Procedure 2 defines an adaptive estimator, uniformly over distributions such that s belongs to some Hölderian ball H(α, R) with α ∈ (0, 1] and the noise-level σ is not too pathological. This result is quite strong. Although similar properties have already been proved for "ad hoc" estimators (see [START_REF] Efromovich | Sharp-optimal and adaptive estimation for heteroscedastic nonparametric regression[END_REF][START_REF] Galtchouk | Adaptive asymptotically efficient estimation in heteroscedastic nonparametric regression via model selection[END_REF] and Section 7.1.3), Resampling Penalization has not been designed specifically to have such a property. Therefore, exchangeable resampling penalties are naturally adaptive to the smoothness of s and to the heteroscedasticity of the data. Remark 3.

1. The proof of Theorem 2 shows that s m achieves the minimax rate of estimation on an event of probability larger than 1 -K ′ 3 n -2 . In particular, with probability one,

lim sup n→∞ ℓ ( s, s ) R -2k 2α+k n 2α 2α+k σ -4α 2α+k L 2 (Leb) ≤ K 2 (α, k).
2. If s is piecewise α-Hölderian with at most J s jumps (each jump of height bounded by 2A), then [START_REF] Arlot | Some nonasymptotic results on resampling in high dimension, I: confidence regions[END_REF] holds with K 3 depending also on J s . 3. As for Theorem 1, the boundedness of the data and the lower bound on the noise level can be replaced by other assumptions (see Section 3.3.2).

Discussion on some assumptions

The aim of this subsection is to discuss some of the main assumptions made in Theorems 1 and 2. We first tackle the lower bound in (Ap) which is required in Theorem 1. Then, two alternative assumption sets to Theorems 1 and 2 are provided, allowing the noise level to vanish or the data to be unbounded.

Lower bound in (Ap)

The lower bound

ℓ ( s, s m ) ≥ C - b D -β1
m in (Ap) may seem unintuitive because it means that s is not too well approximated by the models S m . Assuming that inf m∈Mn ℓ ( s, s m ) > 0 is classical for proving the asymptotic optimality of Mallows' C p [START_REF] Shibata | An optimal selection of regression variables[END_REF][START_REF] Li | Asymptotic optimality for C p , C L , cross-validation and generalized cross-validation: discrete index set[END_REF][START_REF] Birgé | Minimal penalties for Gaussian model selection[END_REF].

Let us explain why (Ap) is used for proving Theorem 1. According to Remark 8 in Section 8.2, when the lower bound in (Ap) is no longer assumed, ( 8) holds with two modifications on its right-hand side: the infimum is restricted to models of dimension larger than ( ln(n) )

γ1 and a remainder term ( ln

(n) ) γ2 n -1
is added (where γ 1 and γ 2 are absolute constants). This is essentially the same as ( 8) unless there exists a model of small dimension with a small bias; the lower bound in (Ap) is sufficient to ensure this does not happen. Note that assumption (Ap) was made in the density estimation framework [START_REF] Stone | An asymptotically optimal histogram selection rule[END_REF][START_REF] Burman | Estimation of equifrequency histograms[END_REF] for the same technical reasons.

As showed in [START_REF] Arlot | Technical appendix to "Model selection by resampling penalization[END_REF], (Ap) is at least satisfied with

β 1 = k -1 + α -1 -(k -1)k -1 α -1 and β 2 = 2αk -1
in the following case: (I λ ) λ∈Λm is "regular" (as defined in Procedure 2 below), X has a lower-bounded density with respect to the Lebesgue measure Leb on X ⊂ R k and s is non-constant and α-Hölderian (with respect to • ∞ ).

The general formulation of (Ap) is crucial to make Theorem 1 valid whatever the distribution of X which can be useful in some practical problems. Indeed, when X has a general distribution, a collection ( S m ) m∈Mn satisfying (P1), (P2), (Ar X ℓ ) and (Ap) can always be chosen either thanks to prior knowledge on D(X) or to unlabeled data. In the latter case, classical density estimation procedures can be applied for estimating D(X) from unlabeled data (see for instance [START_REF] Devroye | Combinatorial methods in density estimation[END_REF] on density estimation). Assumption (Ap) then means that the collection of models has good approximation properties, uniformly over some appropriate function space (depending on D(X)) to which s belongs.

Two alternative assumption sets

Theorems 1 and 2 are corollaries of a more general result, called Lemma 7 in Section 8.2. The assumptions of Theorems 1 and 2, in particular (Ab) and (An) on the distribution of the noise σ(X)ǫ, are only sufficient conditions for the assumptions of Lemma 7 to hold. The following two alternative sufficient conditions are proved to be valid in Section 8.4.

First, one can have

σ min = 0 in (An) if moreover E σ(X) 2 > 0, X ⊂ R k is bounded and (Ar d u ) Upper regularity of the partitions for • ∞ : ∃c d r,u , α d > 0 such that ∀m ∈ M n , max λ∈Λm { diam(I λ ) } ≤ c d r,u D -α d m .
(Ar u ) Upper regularity of the partitions for Leb: ∃c r,u > 0 such that

∀m ∈ M n , max λ∈Λm { Leb(I λ ) } ≤ c r,u D -1 m .
(Aσ) σ is piecewise K σ -Lipschitz with at most J σ jumps.

Second, the Y i can be unbounded (assuming now that σ min > 0 in (An)) if moreover X ⊂ R is bounded measurable and (A gauss ) The noise is sub-Gaussian:

∃c gauss > 0 such that ∀q ≥ 2, ∀x ∈ X , E [ |ǫ| q | X = x ] 1/q ≤ c gauss √ q.
(Aσ max ) Noise-level bounded from above:

σ 2 (X) ≤ σ 2 max < +∞ a.s. (As max ) Bound on the regression function: s ∞ ≤ A. (Al) s is B-Lipschitz, piecewise C 1 and non-constant: ±s ′ ≥ B 0 > 0 on some interval J ⊂ X with Leb(J) ≥ c J > 0.
(Ar ℓ,u ) Regularity of the partitions for Leb: ∃c r,ℓ , c r,u > 0 such that

∀m ∈ M n , ∀λ ∈ Λ m , c r,ℓ D -1 m ≤ Leb(I λ ) ≤ c r,u D -1 m .
(Ad ℓ ) Density bounded from below: ∃c min X > 0, ∀I ⊂ X , P(X ∈ I) ≥ c min X Leb(I). Third, it is possible to have simultaneously σ min = 0 in (An) and unbounded data, see [START_REF] Arlot | Technical appendix to "Model selection by resampling penalization[END_REF] for details.

The above results mean that Theorem 1 holds for most "reasonably" difficult problems. Actually, Proposition 3 and Remark 7 show that the resampling penalties are much closer to E [ pen id (m) ] than pen id (m) itself, provided that the concentration inequalities for pen id are tight (Proposition 10). Therefore, up to differences within ε n , RP with C = C W and the "ideal" deterministic penalization procedure E [ pen id (m) ] perform equally well on a set of probability 1 -K 1 n -2 . For every assumption set such that the proof of Theorem 1 gives an oracle inequality for the penalty E [ pen id (m) ], the same proof gives a similar oracle inequality for RP.

Probabilistic tools

Theorems 1 and 2 rely on several probabilistic tools of independent interest: precise computation of the expectations of resampling penalties (Propositions 1 and 2), concentration inequalities for resampling penalties (Proposition 3) and bounds on expectations of the inverses of several classical random variables (Lemma 4-6). Their originality comes from their non-asymptotic nature: explicit bounds on the deviations or the remainder terms are provided for finite sample sizes.

Expectations of resampling penalties

Using only the exchangeability of the weights, the resampling penalty can be computed explicitly (Lemma 16 in Section 8.8). This can be used to compare the expectations of the resampling penalties and the ideal penalty. First, Proposition 1 is valid for general exchangeable weights.

Proposition 1. Let S m be the model of histograms associated with some partition (I λ ) λ∈Λm of X and W ∈ [0, ∞) n be an exchangeable random vector independent of the data. Define pen id (m) by (3) and pen(m) by [START_REF] Arlot | Suboptimality of penalties proportional to the dimension for model selection in heteroscedastic regression[END_REF].

Let E Λm [ • ] denote expectations conditionally on (1 Xi∈I λ ) 1≤i≤n, λ∈Λm . Then, if min λ∈Λm p λ > 0, E Λm [ pen id (m) ] = 1 n λ∈Λm 1 + p λ p λ σ 2 λ (11) E Λm [ pen(m) ] = C n λ∈Λm ( R 1,W (n, p λ ) + R 2,W (n, p λ ) ) σ 2 λ ( 12
)
with σ 2 λ :=E ( Y -s(X) ) 2 X ∈ I λ , R 1,W (n, p λ ) :=E (W 1 -W λ ) 2 W 2 λ X 1 ∈ I λ , W λ > 0 , ( 13
) and R 2,W (n, p λ ) :=E (W 1 -W λ ) 2 W λ X 1 ∈ I λ . ( 14
)
In particular,

E [ pen id (m) ] = 1 n λ∈Λm ( 2 + δ n,p λ ) σ 2 λ ( 15
)
where δ n,p only depends on (n, p) and satisfies

|δ n,p | ≤ L 1 (np) -1/4 for some absolute constant L 1 .
Proposition 1 is proved in Section 8.8. Remark 4.

• In order to make the expectation in [START_REF] Barbe | The weighted bootstrap[END_REF] well-defined, a convention for pen id (m) has to be chosen when min λ∈Λm p λ = 0. See Section 8.1 for details.

• Combining Proposition 1 with [6, Lemma 8.4], a similar result holds for non-exchangeable weights (with only a modification of the definitions of R 1,W and R 2,W ).

In the general heteroscedastic framework (1), Proposition 1 shows that resampling penalties take into account the fact that σ 2 λ actually depends on λ ∈ Λ m . This is a major difference with the classical Mallows' C p penalty pen Mallows (m) := 2E σ(X) 2 D m n which does not take into account the variability of the noise level over X . A more detailed comparison with Mallows' C p is made in Section 7.1.1.

If R 1,W (n, p λ ) + R 2,W (n, p λ ) does not depend too much on p λ (at least when n p λ is large), Proposition 1 shows that pen(m) estimates unbiasedly pen id (m) as soon as6

C = C W ≈ 2 R 1,W (n, 1) + R 2,W (n, 1) = 1 E ( W 1 -1 ) 2 .
In particular, all the examples of resampling weights given in Section 2.2 satisfy that R 1,W (n, p λ ) ≈ R 2,W (n, p λ ) does not depend on p λ when n p λ is large, which leads to Proposition 2 below (see Table 2 for exact expressions of R 2,W and C W ).

Proposition 2. Let W be an exchangeable resampling weight vector among Efr(M n ), Rad(p), Poi(µ), Rho(⌊n/2⌋) and Loo, and define C W as in Table 2.

D(W ) Efr(M ) Rad(p) Poi(µ) Rho(q) Loo R 2,W (n, p λ ) n M 1 -1 n p λ 1 p -1 1 µ 1 -1 n p λ n q -1 1 n-1 C W M/n p/(1 -p) µ q/(n -q) n -1
Let S m be the model of histograms associated with some partition ( I λ ) λ∈Λm of X and pen(m) be defined by [START_REF] Arlot | Suboptimality of penalties proportional to the dimension for model selection in heteroscedastic regression[END_REF]. Then, there exist real numbers δ (penW) n, p λ depending only on n, p λ and the resampling scheme D(W ) such that

E Λm [ pen(m) ] = C C W n λ∈Λm 2 + δ (penW) n, p λ σ 2 λ . ( 16
)
If M n n -1 ≥ B > 0 (Efr), p ∈ (0; 1) (Rad) or µ > 0 (Poi), then, ∀n ∈ N\ { 0 } , ∀ p λ ∈ (0, 1], δ (penW) n, p λ ≤ L 2 ( n p λ ) -1/4 ,
where L 2 > 0 is an absolute constant (for Rho(⌊n/2⌋) and Loo) or depends respectively on B (Efr ), p (Rad ) or µ (Poi). More precise bounds for each weight distribution are given by ( 62)-( 66) in Section 8.9.

Proposition 2 is proved in Section 8.9. Remark 5. Proposition 2 can also be generalized to Rho(q n ) weights with 0 < B -≤ q n n -1 ≤ B + < 1, but the bound on δ (penW) n, p λ only holds for n p λ ≥ L(B -, B + ) and L 2 depends on B -, B + (see Section 8.9). Remark 6. Combined with the explicit expressions of C W for several resampling weights (Table 2), Proposition 2 helps to understand several known results.

• In the maximum likelihood framework, Shibata [START_REF] Shibata | Bootstrap estimate of Kullback-Leibler information for model selection[END_REF] showed the asymptotical equivalence of two bootstrap penalization methods. The first penalty, denoted by B 1 , is Efron's bootstrap penalty [START_REF] Efron | Estimating the error rate of a prediction rule: improvement on cross-validation[END_REF], which is defined by [START_REF] Arcones | On the bootstrap of M -estimators and other statistical functionals[END_REF] with Efr weights. The second penalty, denoted by B 2 , was proposed by Cavanaugh and Shumway [START_REF] Cavanaugh | A bootstrap variant of AIC for state-space model selection[END_REF]; it transposes

2 p 1 (m) = 2E W P n γ( s W m ) -γ( s m )
into the maximum likelihood framework. In the least-squares regression framework (with histogram models), the proofs of Propositions 1 and 2 show that

E Λm [ 2 p 1 (m) ] = 2 n λ∈Λm R 1,W (n, p λ )σ 2 λ ≈ E Λm [ pen(m) ]
for several resampling schemes, including Efron's bootstrap (for which C W = 1). The concentration results of Section 8.10 show that this remains true without expectations.

• With Efron (M n ) weights (and a bootstrap selection procedure close to RP, but with C = 1), Shao [START_REF] Shao | Bootstrap model selection[END_REF] showed that M n = n leads to an inconsistent model selection procedure for identification. On the contrary, when M n → ∞ and M n ≪ n, Shao's bootstrap selection procedure is model consistent. Proposition 2 shows that these assumptions on M n can be rewritten

C = 1 ≫ C W = M n /n.
Therefore, the rationale behind Shao's result may mostly be that identification needs overpenalization within a factor tending to infinity with n.

Concentration inequalities for resampling penalties

From ( 4), the ideal penalty can be written

pen id (m) = (P -P n )γ ( s m ) + λ∈Λm p λ + p λ ( n p λ ) 2 Xi∈I λ ( Y i -β λ ) 2 .
Hence, pen id (m) is a U-statistics of order 2 conditionally on (1 Xi∈I λ ) (i,λ∈Λm) , which is sufficient to prove that resampling yields a consistent estimate of pen id (m) (Arcones and Giné [START_REF] Arcones | On the bootstrap of M -estimators and other statistical functionals[END_REF] considered the bootstrap case; Hušková and Janssen [START_REF] Hušková | Consistency of the generalized bootstrap for degenerate U -statistics[END_REF] extended it to the exchangeable weighted bootstrap).

In the non-asymptotic framework, that is when the models S m can depend on n, the following concentration inequality is needed. Proposition 3. Let γ > 0, A n ≥ 2 and W be an exchangeable weight vector. Let S m be the model of histograms associated with some partition (I λ ) λ∈Λm of X and pen(m) be defined by [START_REF] Arlot | Suboptimality of penalties proportional to the dimension for model selection in heteroscedastic regression[END_REF]. Assume that two positive constants a ℓ and ξ ℓ exist such that for every q ≥ 2,

D m λ∈Λm m 4 q,λ λ∈Λm m 2 2,λ ≤ a ℓ q ξ ℓ where m q,λ := (E [|Y -s m (X)| q | X ∈ I λ ]) 1/q .
Let Ω m (A n ) denote the event { min λ∈Λm { n p λ } ≥ A n }. Then, there exist constants K 4 , K 5 > 0 and an event of probability at least 1 -K 4 n -γ on which

pen(m) -E Λm [ pen(m) ] 1 Ωm(An) ≤ CK 5 × sup np≥An { R 1,W (n, p) + R 2,W (n, p) } ( ln(n) ) ξ ℓ +1 √ A n D m E [ p 2 (m) ]
where R 1,W and R 2,W are defined by [START_REF] Baraud | Model selection for regression on a fixed design[END_REF] and [START_REF] Baraud | Model selection for regression on a random design[END_REF]. The constant K 4 is absolute and K 5 may only depend on a ℓ , ξ ℓ and γ.

If moreover W satisfies the assumptions of the second part of Proposition 2 and C

W is defined as in Table 2, then a constant K W > 0 exists such that pen(m) -E Λm [pen(m)] 1 Ωm(An) ≤ CK 5 K W ( ln(n) ) ξ ℓ +1 C W √ A n D m E [ p 2 (m) ] . ( 17
)
For the Rad(p) weights, K W is smaller than (1 -p) -1 multiplied by an absolute constant. For the other weights, K W is an absolute constant.

Proposition 3 is proved in Section 8.10.1. Note that the moment condition holds under the assumptions of Theorem 1 as well as the alternative assumptions of Section 3.3.2. It is here stated in its most general form.

Remark 7. Since the A -1/2 n
factor should tend to infinity with n for most reasonable models, Proposition 3 gives better bounds for resampling penalties than what could be obtained for ideal penalties with Proposition 10 in the same framework.

Although we do not know how tight are the bounds of Proposition 3, such a phenomenon is classical with bootstrap and can be understood from the asymptotic point of view through Edgeworth expansions [START_REF] Hall | The bootstrap and Edgeworth expansion[END_REF]. In a non-asymptotic Gaussian framework, [10, Section 2.3] shows the same property for resampling estimators, which concentrate at the rate N -1 instead of N -1/2 (N being the amount of data). Since A n plays the role of N , the gain A -1/2 n can reasonably be conjectured to be unimprovable without some more assumptions.

Let us emphasize that if resampling penalties estimate E [ pen id (m) ] instead of pen id (m), RP with C = C W cannot take into account the fact that pen id (m) may be far from its expectation.

Expectations of inverses

For any non-negative random variable Z, we define

e + Z = e + D(Z) := E [ Z ] E Z -1 Z > 0 .
This quantity appears in the explicit formulas for R 1,W when W is among the examples of resampling weights of Section 2.2 (see Lemma 17). Therefore, in order to prove Proposition 2, non-asymptotic bounds on e + Z are needed when Z has a binomial, hypergeometric or Poisson distribution.

Former results concerning e + Z can be found in papers by Lew [START_REF] Lew | Bounds on negative moments[END_REF] (for general Z), by Jones and Zhigljavsky [START_REF] Jones | Approximating the negative moments of the Poisson distribution[END_REF] (for the Poisson case) and by Žnidarič [START_REF] Marko | Asymptotic expansions for inverse moments of binomial and poisson distributions[END_REF] (for the binomial and Poisson case), but they are either asymptotic or not precise enough. Lemmas 4-6 solve this issue.

In the rest of the paper, for any a, b ∈ R, a ∧ b denotes the minimum of a and b and a ∨ b denotes the maximum of a and b.

Binomial case

Lemma 4. For any n ∈ N\ { 0 } and p ∈ (0; 1], B(n, p) denotes the binomial distribution with parameters (n, p), κ 1 := 5.1 and κ 2 := 3.2. Then, if np ≥ 1,

κ 2 ∧ 1 + κ 1 (np) -1/4 ≥ e + B(n,p) ≥ 1 -e -np (18
)

and 2 + 3 × 10 -4 ≥ e + B( n, 1 2 ) ≥ 1 n≥3 . ( 19
)
The first bounds [START_REF] Peter | Local Rademacher complexities[END_REF] were first stated in [9, Lemma 3] where they are proved. The second ones [START_REF] Peter | Local complexities for empirical risk minimization[END_REF] are proved in Section 8.11.1. Lemma 4 implies in particular that e + B(n,p) → 1 when np → ∞, which can be derived from [START_REF] Marko | Asymptotic expansions for inverse moments of binomial and poisson distributions[END_REF].

Hypergeometric case Recall that an hypergeometric random variable X ∼ H(n, r, q) is defined by

∀k ∈ { 0, . . . , q ∧ r } , P(X = k) = r k n-r q-k n q
.

Lemma 5. Let n, r, q ∈ N such that n ≥ r ≥ 1 and n ≥ q ≥ 1.

General lower-bound:

e + H(n,r,q) ≥ 1 -1 r≤n-q exp -qr n .

2. General upper-bound: let ǫ ∈ (0; 1) and κ 3 (ǫ) := 0.9

+ 1.4 × ǫ -2 . If r ≥ 2 and n q ≤ (1 -ǫ) 2r 2 + 3(r + 1) ln(r)
Then,

1 + κ 3 (ǫ) n q ln(r) r ≥ e + H(n,r,q) . ( 20
) 3. "Rho" case: if n ≥ 2, 14.3 ≥ sup r≥1 e + H(n,r,⌊ n 2 ⌋) and 3 ≥ sup r≥26 e + H(n,r,⌊ n 2 ⌋) . (21)
4. "Loo" case:

1 + 1 r≥2 n(r -1) ≥ e + H(n,r,n-1) = 1 + 1 n (n -1)r n(r -1) 1 r≥2 -1 ≥ 1 - 1 r=1 n . (22)

"Lpo" case

: if n ≥ r ≥ n -q + 1 ≥ 2, r r -n + q × n n-q n(n -1) • • • (q + 1)
≥ e + H(n,r,q) ≥ 1.

Lemma 5 is proved in Section 8.11.2. It implies in particular that

e + H(n k ,r k ,q k ) ----→ k→∞ 1 if n k ≥ r k ----→ k→∞ +∞ and sup k n k q -1 k < +∞.
Poisson case Lemma 6. For every µ > 0, P(µ) denotes the Poisson distribution with parameter µ. Then,

2 -2e -2µ ∧ 1 + 2(1 + e -3 ) (µ -2)1 µ>2 ≥ e + P(µ) ≥ 1 -1 µ<1.61 e -µ .
Lemma 6 is proved in Section 8.11.3. It implies in particular that e + P(µ) → 1 when µ → ∞, which can be derived from [START_REF] Jones | Approximating the negative moments of the Poisson distribution[END_REF][START_REF] Marko | Asymptotic expansions for inverse moments of binomial and poisson distributions[END_REF].

Comparison of the weights

We investigate in this section how the loss of the final estimator may depend on the distribution of the exchangeable weight vector W . First, we consider in Section 4.1 the most classical ones, that is Efr, Rad, Poi, Rho and Loo. Then, we discuss in Section 4.2 whether Theorem 1 can be extended to general exchangeable weights.

Comparison of the classical weights

According to Theorem 1, any resampling scheme among Efr, Rad, Poi, Rho and Loo leads to an asymptotically optimal procedure. Even from the nonasymptotic point of view, it is not quite clear to distinguish between these weights with the results of Section 3. Indeed, the resampling penalties are equal in expectation at first order (Proposition 2), and their deviations are negligible in front of their expectations (Proposition 3). Therefore, differences between these weights can only come from second-order terms, either in the expectations or in the sizes of the deviations of resampling penalties. As a first step, we compare in this subsection second-order terms in the expectations of the penalties (that is, differences between second-order terms in [START_REF] Barbe | The weighted bootstrap[END_REF] and ( 16)), for a fixed sample size. Asymptotic considerations can be found in the book by Barbe and Bertail [15,Chapter 2] where Edgeworth expansions are used to compare the accuracy of estimation with many exchangeable weights. The asymptotic results mentioned in Section 3.4.3 may also be useful.

Propositions 1 and 2 show that pen id (m) and pen(m) have the same expectation, up to the small terms δ n,p λ and δ

(penW) n, p λ . More precisely, E [ pen(m) -pen id (m) ] = 1 n λ∈Λm δ (penW) n,p λ -δ n,p λ (σ λ ) 2 with δ (penW) n,p λ := E δ (penW) n, p λ p λ > 0 .
Using the explicit expressions of δ n,p and δ ). It follows that Loo weights are the most accurate ones, even when np is small. On the contrary, Rho (n/2) and Rad tend to overestimate pen id since δ (penW) n,p > δ n,p (except when np is small, where the inequality is reversed). It also seems that the bias of Rho (q) is a decreasing function of q, as illustrated by Figures 34. Finally, Efr and Poi are strongly underestimating the ideal penalty, mostly because of the 1 -

(n p λ ) -1 term in R 1,W (n, p λ ) and R 2,W (n, p λ ).
This can be summed up as follows: where ">>" means a comparatively large gap, but still negligible at first order. Hence, we can expect that the Loo penalty is the most efficient, closely followed by Rad and by Rho. However, from the non-asymptotic point of view, it turns out that smaller prediction loss is obtained by overpenalizing slightly (and sometimes strongly, see the simulations of Section 5 and the discussion of Section 6.3.2). Then, the ordering of (23) may also be the one of the prediction performances of RP, the best performances being obtained with Rad and Rho. This is confirmed by the simulation study of Section 5.

penRad ≈ penRho > penLoo ≈ pen id >> penEfr ≈ penPoi, (23)
Another interesting point is that δ

(penRho) n,p
∝ δ n,p when np is large enough. Then, provided that histograms with too small bins are removed from the collection, penLoo and penRho are almost equivalent, up to the choice of the factor C. If a wise tuning of C is possible, it remains to choose between Loo and Rho according to computational issues (see the discussion of Section 6.2).

Other exchangeable weights

The oracle inequality of Theorem 1 is only stated for the five "classical" exchangeable weights of Section 2.2. Nevertheless, replacing the threshold 3 by some T ≥ 2 at step 1 of Procedure 1, the proof of Theorem 1 can be extended to any resampling weight vector W satisfying:

1. W is exchangeable, 2. R 1,W (n, p)+R 2,W (n, p) ≈ 2C W
for np large enough (with a non-asymptotic control on the ratio between these two quantities, as in the proof of Proposition 2), 3. R 1,W (n, p)+R 2,W (n, p) > (1+ǫ)C W for some ǫ > 0, as soon as np ≥ T ≥ 2 (as in Lemma 15).

In particular, the first two conditions hold for all the exchangeable weights considered in Proposition 2. The third one is satisfied for most of them as soon as T is large enough (see Lemma 15 in Section 8.6).

Simulation study

As an illustration of the results of Section 3, the prediction performances of Procedure 1 (with several resampling schemes), Mallows' C p and V -fold crossvalidation are compared on some simulated data.

Experimental setup

We consider four experiments, called S1, S2, HSd1 and HSd2. Data are generated according to

Y i = s(X i ) + σ(X i )ǫ i
where ( X i ) 1≤i≤n are independent with uniform distribution over X = [0; 1] and ( ǫ i ) 1≤i≤n are independent standard Gaussian variables independent of ( X i ) 1≤i≤n . The experiments differ from the regression function s (smooth for S, see Figure 7; smooth with jumps for HS, see Figure 8), the noise type (homoscedastic for S1 and HSd1, heteroscedastic for S2 and HSd2) and the sample size n (see Table 3). Instances of data sets are plotted on Figures 9-12 The collections of histogram models also differ according to the experiments. Define

∀k, k 1 , k 2 ∈ N\ { 0 } , ( I λ ) λ∈Λ k = j k ; j + 1 k 0≤j≤k-1
and

( I λ ) λ∈Λ (k 1 ,k 2 ) = j 2k 1 ; j + 1 2k 1 0≤j≤k1-1 ∪ 1 2 + j 2k 2 ; 1 2 + j + 1 2k 2 0≤j≤k2-1
.

For every m ∈ ( N\ { 0 } )∪( N\ { 0 } ) 2 , let S m be the histogram model associated with the partition ( I λ ) λ∈Λm . Then, for each experiment, the collection of models is ( S m ) Mn with different index sets M n : S1 regular histograms with 1 ≤ D ≤ n ( ln(n) )

-1 pieces, that is

M n = 1, . . . , n ln(n) . S2 histograms regular on [ 0; 1/2 ] (resp. on [ 1/2; 1 ]), with D 1 (resp. D 2 ) pieces, 1 ≤ D 1 , D 2 ≤ n ( 2 ln(n) ) -1 . The model of constant functions is added to M n , that is M n = { 1 } ∪ 1, . . . , n 2 ln(n) 2 .
HSd1 dyadic regular histograms with 2 k pieces, 0

≤ k ≤ ln 2 (n) -1, that is M n = 2 k s.t. 0 ≤ k ≤ ln 2 (n) -1 .
HSd2 dyadic histograms regular on [ 0; 1/2 ] (resp. on [ 1/2; 1 ]) with bin sizes 2 -k1 (resp.

2 -k2 ), 0 ≤ k 1 , k 2 ≤ ln 2 (n) -2 (dyadic version of S2
). The model of constant functions is added to M n , that is

M n = { 1 } ∪ 2 k s.t. 0 ≤ k ≤ ln 2 (n) -2 2 .
Note that the collections of models used in experiments S2 and HSd2 can adapt to s and σ(•). Therefore, the oracle model is generally quite efficient so that the model selection problem is more challenging.

The following procedures7 are compared:

Mal Mallows' C p penalty: pen(m) = 2 σ 2 D m n -1 where σ 2 is the classical variance estimator defined as

σ 2 = d 2 Y 1...n , S ⌊n/2⌋ n -⌊n/2⌋ , (24)
where

Y 1...n = (Y i ) 1≤i≤n ∈ R n , S ⌊n/2⌋ is any model of dimension ⌊n/2⌋
(only assumed to have a bias negligible in front of σ 2 ) and d is the Euclidean distance on R n . The non-asymptotic validity of this model selection procedure in homoscedastic regression has been assessed by Baraud [13]. E [ pen id ] Expectation of the ideal penalty: pen(m) = E [ pen id (m) ], which witnesses what is a good performance in each experiment. VFCV V -fold cross-validation, with V ∈ {2, 5, 10, 20} (defined as in [START_REF] Arlot | V -fold cross-validation improved: V -fold penalization[END_REF]). LOO Leave-one-out (that is VFCV with V = n). penEfr Efron (n) penalty [START_REF] Arlot | Suboptimality of penalties proportional to the dimension for model selection in heteroscedastic regression[END_REF] with C = C W = 1. penRad Rademacher (1/2) penalty [START_REF] Arlot | Suboptimality of penalties proportional to the dimension for model selection in heteroscedastic regression[END_REF] with C = C W = 1. penRho Random hold-out (n/2) penalty [START_REF] Arlot | Suboptimality of penalties proportional to the dimension for model selection in heteroscedastic regression[END_REF] with C = C W = 1. penLoo Leave-one-out penalty [START_REF] Arlot | Suboptimality of penalties proportional to the dimension for model selection in heteroscedastic regression[END_REF] with

C = C W = n -1.
For each of these, the same penalties multiplied by 5/4 are also considered (and they are denoted by a + symbol added after the shortened names). This intends to test for overpenalization (the choice of the factor 5/4 being arbitrary and certainly not optimal, see Section 6.3.2).

In each experiment, for each simulated data set, first the models with 2 data points or less in one piece of their associated partition are removed. Then, the least-squares estimators s m are computed for each m ∈ M n . Finally, m ∈ M n is selected using each procedure and its true excess loss ℓ s, s m is computed as well as the excess loss of the oracle inf m∈Mn ℓ ( s, s m ). N = 1000 data sets are simulated, thanks to which the model selection performance of each procedure is estimated through the two following benchmarks:

C or = E ℓ s, s m E [ inf m∈Mn ℓ ( s, s m ) ] C path-or = E ℓ s, s m inf m∈Mn ℓ ( s, s m )
Basically, C or is the constant that should appear in an oracle inequality like [START_REF] Arlot | V -fold cross-validation improved: V -fold penalization[END_REF], and C path-or corresponds to a pathwise oracle inequality like [START_REF] Arlot | Technical appendix to "Model selection by resampling penalization[END_REF]. Since C or and C path-or approximatively give the same rankings between procedures, Table 3 only reports C or ; the values of C path-or are reported in [START_REF] Arlot | Technical appendix to "Model selection by resampling penalization[END_REF].

Results and comments

First, the above experiments show the interest of both Resampling Penalization (RP) and VFCV in several difficult frameworks, with relatively small sample sizes. Although RP and VFCV cannot compete with simple procedures such as Mallows' C p from the computational point of view, they are much more efficient when the noise is heteroscedastic (S2 and HSd2). In these difficult frameworks, the prediction performances of RP and VFCV are comparable to those of E [ pen id ]. Note that in HSd2, penRad and penRho give smaller losses than any penalty proportional to the dimension of the models (see Section 7.1.2). Moreover, penRad and penRho perform slighlty worse than Mallows' C p for the easiest problems (S1 and HSd1), which can be interpretated as the unavoidable price for robustness. Second, in the four experiments, the best procedures always are the overpenalizing ones: many of them even beat the perfectly unbiased E [ pen id ], showing the crucial need to overpenalize. This phenomenon disappears for small σ and large n [8, Experiments S0.1 and S1000], hence it is certainly due to the small signal-to-noise ratio. We would like to insist on the importance of the overpenalization phenomenon, which is seldom mentioned in theoretical papers because it vanishes in the asymptotic framework, and it is quite hard to find from theoretical results.

Let us now compare RP and VFCV. According to the four experiments of Table 3, RP with Rad or Rho resampling schemes clearly outperforms VFCV for any V , even without overpenalizing. The only exception to this is HSd1 where 2-fold cross-validation yields a particularly good model selection performance.

This can be interpretated thanks to the non-asymptotic study of the performance of V -fold cross-validation provided in [START_REF] Arlot | V -fold cross-validation improved: V -fold penalization[END_REF]. In short, VFCV overpenalizes within a factor 1 + 1/(2(V -1)), while the V -fold criterion has a variance decreasing with V .

Then, when overpenalization is necessary (for instance in S1, S2 or HSd1), small values of V can outperform the leave-one-out (V = n). Nevertheless, RP with the right overpenalization level C/C W leads to a smaller prediction loss than VFCV, because RP provides a less variable model selection criterion than VFCV. The reason why penRad and penRho also perform slightly better without overpenalization is that they naturally overpenalize when C = C W = 1 (see Section 4).

Let us now consider the model selection performance of RP with several exchangeable resampling schemes. The two best ones are Rad and Rho in the four experiments, with or without overpenalization. Then, Loo performs slightly worse (but not always significantly) and Efr much worse. Looking carefully at the values of the penalties, it appears that Rad and Rho slightly overpenalize, Loo is exactly at the right level, and Efr underpenalizes (as well as Poi, which has performances quite similar to the ones of Efr, see [START_REF] Arlot | Technical appendix to "Model selection by resampling penalization[END_REF]). Note that this comparison can also be derived from theoretical computations (see Section 4). Since overpenalization is benefic in the four experiments of Table 3, this explains why penRad and penRho slightly outperform penLoo. In the case of Efron's boostrap penalty, underpenalizing implies overfitting which explains the comparatively bad performances reported in Table 3.

We conclude this section with remarks concerning some particular points of the simulation study.

• On the same data sets, Mallows' C p and its overpenalized version Mal+ were performed with the true mean variance E σ 2 (X) instead of σ 2 (which would not be possible on a real data set). It yielded worse model selection performance for all experiments but S2, in which C or (Mal) = 2.657 ± 0.06 and C or (Mal+) = 2.437 ± 0.05. Therefore, overpenalization is crucial in experiment S2, more than the shape8 of the penalty itself.

Moreover, the overpenalization level being fixed, resampling penalties remain significantly better than Mallows' C p . Hence, the performances of Mallows' C p in Table 3 are not only due to a bad estimation of the mean noise-level (see also Section 7.1). • Eight additional experiments are reported in [START_REF] Arlot | Technical appendix to "Model selection by resampling penalization[END_REF], showing similar results with various n, σ and s (although the assumptions of Theorem 1 are not always satisfied). • Resampling penalties with a V -fold subsampling scheme have also been studied in [9, Section 4] on the same simulated data: exchangeable resampling schemes always give better model selection performance than nonexchangeable ones (significantly when V is small), except for Efr and Poi which tend to underestimate the ideal penalty.

Practical implementation

This section tackles three main issues for using Procedure 1 in practice: how to compute the resampling penalty (7)? how to choose the weights W ? how to choose the constant C?

Computational cost

An exact computation of resampling penalties with exchangeable weights (without using formula (50) for histograms) would be either impossible or computationally expensive. We suggest two possible ways to fix this problem. First, one can use a classical Monte-Carlo approximation, that is draw a small number B of independent weight vectors instead of considering each element of the support of D(W ). Practical Monte-Carlo methods for the boostrap are proposed for instance by Hall Second, it is possible to use non-exchangeable weight vectors W such that the cardinality of the support of D(W ) is much smaller than n. A case-example is V -fold subsampling: given a partition ( B j ) 1≤j≤V of { 1, . . . , n } and J a uniform random variable over { 1, . . . , V } independent of the data, we define

∀i ∈ { 1, . . . , n } , W i = V V -1 1 i / ∈BJ .
The resulting resampling penalties -called V -fold penalties-have been introduced and studied in [START_REF] Arlot | V -fold cross-validation improved: V -fold penalization[END_REF]. They are computationally similar to VFCV while being more flexible, since the overpenalization factor is decoupled from the choice of V ; hence, like resampling penalties, V -fold penalties select an estimator with smaller prediction loss than the one selected by VFCV. Both Monte-Carlo approximation of RP and V -fold penalization have been tested on the simulated data of Section 5. The detailed results are given in [START_REF] Arlot | Technical appendix to "Model selection by resampling penalization[END_REF].

Choice of the weights

The influence of the weights has been investigated from the theoretical point of view in Section 4 with focus on second-order terms in expectation. However, deviations of pen(m) around its expectation are likely to depend on the weight vector W since the upper bound in [START_REF] Peter | Model selection and error estimation[END_REF] may not be tight. The simulation study of Section 5 allows to take into account both phenomena in the comparison between the resampling weights.

In terms of model selection efficiency, Table 3 shows that the best weights (for accuracy of prediction and for the variability9 of this accuracy) are Rho and Rad, whereas Loo perform slightly worse. On the contrary, from both accuracy and variability points of view, Efron's bootstrap weights perform worse than Rho, Rad and Loo, mainly because they lead to underpenalization.

Note however that this comparison strongly depends on the precise definition10 of C W , which makes all penalties unbiased at first order but possibly under or over-penalizing at second order. Then, different prediction performances may be observed on data which do not require overpenalization. Nevertheless, the computations of Section 4 show that Efron's bootstrap weights have a real drawback which cannot be fixed only by changing C W .

When computing the penalties exactly, Loo weights are the only computationally tractable ones, while being almost as accurate as Rho and Rad. Hence, we suggest their use, enlarging the constant C when needed (see Section 6.3.2 on overpenalization).

However, computing n empirical risk minimizers (or the outputs of computationally more expensive algorithms) for each model is not always possible. In such a case, one should avoid using the Leave-one-out with a Monte-Carlo approximation, which would give a large importance to a small number of data points. Rho or Rad weights are much safer in this situation. Alternatively, one may consider the use of V -fold penalties [START_REF] Arlot | V -fold cross-validation improved: V -fold penalization[END_REF] as a good alternative when the computational power is limited.

Let us emphasize that this analysis and the subsequent advices should be considered with caution. First, the deviations of resampling penalties around their expectations should be understood much better, because they can be comparable or even larger than the second-order terms in expectations. Second, the optimal choice of V for V -fold cross-validation is known to be different between least-squares regression and binary classification [9, Section 2.3]. Such differences are expected to arise for choosing between exchangeable resampling weights.

Remark that the bias of the bootstrap penalty has already been noticed by Efron [START_REF] Efron | Estimating the error rate of a prediction rule: improvement on cross-validation[END_REF][START_REF] Efron | How biased is the apparent error rate of a prediction rule?[END_REF] who proposed several ways to correct it, including a double bootstrap procedure and the .632 bootstrap. The novelty of the approach of this paper is to propose the use of other exchangeable resampling schemes instead of the boostrap so that the bias of resampling penalties no longer has to be corrected.

Choice of the constant C

Optimal constant for bias

From the asymptotic point of view, the optimal C = C ⋆ for prediction is generally the one for which pen estimates the ideal penalty pen id unbiasedly (at least for collections of models of polynomial size). This is how C W is defined in the histogram framework and Theorem 1 implies that C = C W is asymptotically optimal for prediction. Hence 11 , C ⋆ is asymptotically equivalent to C W .

As showed by Arlot and Massart [START_REF] Arlot | Data-driven calibration of penalties for least-squares regression[END_REF], C ⋆ can also be estimated directly from data for general penalties, in particular for RP. Hence, the knowledge of C W is not necessary, which can be useful in the general prediction framework (see Section 7.2).

Overpenalization

A careful look at the proof of Theorem 1 shows that a similar oracle inequality holds for any C > 4C W /5, the leading constant remaining close to one when C ∼ C W asymptotically. In other words, when the sample size n is small, the optimal constant C ⋆ may not be exactly equal to C W . The simulations of Section 5 also support this fact: Overpenalization, that is, taking C = C ov C W with C ov > 1, can improve the prediction performance of s m when n is small, when σ is large or when s is non-smooth.

This problem would appear even if the "optimal" constant C ⋆ such that pen is non-asymptotically unbiased was known. On Figure 13, the estimated model selection performance of the penalty C ov E [ pen id (m) ] is plotted as a function of C ov , for experiment S2 of Section 5. It appears that the optimal overpenalization constant C ⋆ ov ∈ (1.5; 2.35) for this particular problem. More generally, the drawback of using C = C ⋆ is that it does not take into account the deviations of pen id (m) around its expectation. To avoid the possible overfit induced by these deviations, the constant C must be slightly enlarged. A major issue remains: How to estimate C ⋆ ov from data only, since it strongly depends on n, on σ, on the smoothness of s and on the number of models in M n ?

One can think of choosing C ov by V -fold cross-validation, but this would lead to a computationally intractable procedure. An alternative idea is to use resampling for building a simultaneous confidence region on ( pen id (m) ) m∈Mn instead of estimating E [ pen id (m) ] only (see [START_REF] Arlot | Some nonasymptotic results on resampling in high dimension, I: confidence regions[END_REF] on confidence regions built with general exchangeable resampling schemes). Then, the uncertainty on the estimation of pen id (m) can be taken into account for choosing a model, similarly to model selection procedures built upon relative bounds [START_REF] Audibert | Théorie Statistique de l'Apprentissage: une approche PAC-Bayésienne[END_REF][START_REF] Catoni | Pac-Bayesian Supervised Classification: The Thermodynamics of Statistical Learning[END_REF]. Finally, the choice of the overpenalization factor would be replaced by the choice of a confidence level which should be made by the practicioner. See also [START_REF] Arlot | Resampling and Model Selection[END_REF]Section 11.3.3] for a discussion on a data-driven choice of the overpenalization factor.

11 See the proof of Theorem 1 in [START_REF] Arlot | V -fold cross-validation improved: V -fold penalization[END_REF] to prove that asymptotic optimality requires C ⋆ /C W ----→ n→∞ 1 as soon as there are enough models close to the oracle.

Discussion

Comparison with other procedures

In this article, the Resampling Penalization (RP) family of model selection procedures is defined and showed to satisfy some optimality properties under mild assumptions on the data (Theorems 1 and 2). In particular, RP is robust to the heteroscedasticity of the noise according to both theoretical and experimental results. The price for robustness is that the computational cost of RP is generally larger than simple procedures like Mallows' C p , even with the suggestions of Section 6.1. The purpose of this subsection is to identify the "easy" problems, for which the computational cost of RP can be reduced by using C p -like penalties without enlarging the prediction loss too much.

Mallows' C p

Mallows' C p penalty is equal to 2σ 2 D m n -1 for a model S m of dimension D m , when the noise-level σ is constant. Non-asymptotic results about C p -like penalties can be found in [START_REF] Barron | Risk bounds for model selection via penalization[END_REF][START_REF] Baraud | Model selection for regression on a fixed design[END_REF][START_REF] Baraud | Model selection for regression on a random design[END_REF][START_REF] Birgé | Minimal penalties for Gaussian model selection[END_REF]. They imply that Mallows' C p is asymptotically optimal in the homoscedastic framework, when the size of M n is polynomial in n.

When the mean noise-level is unknown, it must be estimated. A classical estimator of E σ 2 (X) is defined by [START_REF] Catoni | Pac-Bayesian Supervised Classification: The Thermodynamics of Statistical Learning[END_REF]. Baraud [START_REF] Baraud | Model selection for regression on a fixed design[END_REF][START_REF] Baraud | Model selection for regression on a random design[END_REF] showed that the resulting data-driven model selection procedure satisfies a non-asymptotic oracle inequality with leading constant close to one.

Assume for the sake of simplicity that n is even and let S n/2 be a model such that each piece of the associated partition contains exactly two data points.

Reordering the (X

i , Y i ) according to X i , pen Mallows (m) = 2D m n 2 n/2 i=1 (Y 2i -Y 2i-1 ) 2 so that E Λm [ pen Mallows (m) ] ≈ 2 n λ∈Λm ( D m p λ ) (σ r λ ) 2 + 2D m n 2 n/2 i=1 ( s(X 2i ) -s(X 2i-1 ) ) 2 (25)
where (σ r λ )

2 := E σ(X) 2 X ∈ I λ .
This should be compared with the result of Proposition 1:

E Λm [ pen id (m) ] ≈ 2 n λ∈Λm (σ r λ ) 2 + σ d λ 2 (26)
where

σ d λ 2 := E ( s(X) -s m (X) ) 2 X ∈ I λ .
Although both Mallows' C p and the ideal penalty are in expectation the sum of a "variance" term (involving the (σ r λ )

2 ) and a "bias" term (involving the variations of s through (s(X 2i ) -s(X 2i-1 )) 2 or (σ d λ ) 2 ), they differ on at least two points.

First, when s is smooth and min λ∈Λm { n p λ } is large, the "bias" term in ( 25) is negligible in front of the one of [START_REF] Devroye | Combinatorial methods in density estimation[END_REF], which means that Mallows' C p underpenalizes when the "bias" component of pen id is large. Second, the "variance" component of pen id , which is the main one in general, is distorted in Mallows' C p : the part of the penalty corresponding to I λ is multiplied by D m p λ which is not close to 1 when the partition ( I λ ) λ∈Λm is not regular with respect to D(X). This happens for instance in experiments S2 and HSd2 of Section 5. Therefore, there are at least three possibly "hard" problem classes:

• heteroscedastic noise, with irregular histograms and X uniform (for instance S2, HSd2 in Section 5, or Svar2 in [START_REF] Arlot | Technical appendix to "Model selection by resampling penalization[END_REF]), • heteroscedastic noise, with regular histograms and X highly non-uniform on X , • regression function s with jumps (such as HeaviSine12 ) or large non-smooth areas (such as Doppler in [START_REF] Arlot | Technical appendix to "Model selection by resampling penalization[END_REF]).

In either of these cases, one should avoid the use of C p -like penalties, and we suggest resampling penalties as an efficient alternative. As explained in Section 7.1.2 below, the first class of problems can make any penalty proportional to the dimension D m suboptimal.

Linear penalties

Mallows' C p is simple because it is a linear function of the dimension D m of S m :

pen(m) = KD m ( 27
)
and K is the only constant to determine. Depending on what is known on the mean variance level, the constant K Mallows can be defined as

2E σ(X) 2 n -1 or 2 σ 2 n -1 .
Refined versions of Mallows' C p have also been proposed [START_REF] Barron | Risk bounds for model selection via penalization[END_REF][START_REF] Baraud | Model selection for regression on a random design[END_REF][START_REF] Birgé | Minimal penalties for Gaussian model selection[END_REF] but they are still linear or very close to linearity. However, according to [START_REF] Arlot | Data-driven calibration of penalties for least-squares regression[END_REF], the ideal penalty is not linear in general, even in expectation. Moreover, there exist some frameworks in which any penalty of the form ( 27) is suboptimal when data are heteroscedastic [START_REF] Arlot | Suboptimality of penalties proportional to the dimension for model selection in heteroscedastic regression[END_REF], that is, it cannot satisfy any oracle inequality with leading constant smaller than some absolute constant κ > 1. In other words, the optimal linear penalization procedure pen opt,lin (m) := K ⋆ D m is suboptimal, where

K ⋆ ∈ arg min K>0 P γ s m(K) and ∀K > 0, m(K) ∈ arg min m∈Mn { P n γ ( s m ) + KD m } .
As showed by Theorem 1, RP does not suffer from this drawback. On the one hand, the optimal linear penalization procedure has a better model selection performance than RP for S1, S2 and HSd1, which is not surprising for the "easy" problems where Mallows' C p is almost optimal (S1, HSd1). It is less intuitive for S2 where data are heteroscedastic. Considering that pen opt,lin uses the knowledge of the true distribution P , one can understand that it is sufficient to keep a good performance for "intermediate" problems.

On the other hand, in experiment HSd2, the optimal linear penalization has a model selection performance C or = 1.18 ± 0.01, which is worse than the one of RP (C or ≤ 1.11). Thus, the most difficult problem of Section 5 (with a large collection of models, heteroscedastic data and bias) gives an example where linear penalties are definitely not adapted, in addition to the ones of [START_REF] Arlot | Suboptimality of penalties proportional to the dimension for model selection in heteroscedastic regression[END_REF].

Ad hoc procedures

One of the main advances with Theorems 1 and 2 is that RP is proved to work in the heteroscedastic framework contrary to Mallows' C p . Nevertheless, in a framework such as the one of experiment S2, Mallows' C p can be adapted to heteroscedasticity by splitting X into several parts where σ is almost constant, and performing the histogram selection procedure with Mallows' C p separately on each part of X .

More generally, Efromovich and Pinsker [START_REF] Efromovich | Sharp-optimal and adaptive estimation for heteroscedastic nonparametric regression[END_REF] and Galtchouk and Pergamenschikov [START_REF] Galtchouk | Adaptive asymptotically efficient estimation in heteroscedastic nonparametric regression via model selection[END_REF] (among several others) defined estimators of s that are minimax adaptive in the heteroscedastic framework, the latter by model selection. In the Gaussian regression framework, Gendre [START_REF] Gendre | Simultaneous estimation of the mean and the variance in heteroscedastic Gaussian regression[END_REF] proposed a model selection method for estimating simultaneously the regression function and the noise level.

All these procedures may perform slightly better than RP in terms of prediction loss. They are called "ad hoc" because they have been specially designed for the heteroscedastic framework (and a particular collection of estimators for [START_REF] Galtchouk | Adaptive asymptotically efficient estimation in heteroscedastic nonparametric regression via model selection[END_REF][START_REF] Gendre | Simultaneous estimation of the mean and the variance in heteroscedastic Gaussian regression[END_REF]). On the contrary, RP is a general-purpose device: It was neither built to be adaptive to heteroscedasticity nor to take advantage of a specific model, and RP has exactly the same definition in the general prediction framework (see Section 7.2).

When no information is available on the data or when no model selection procedure is known for using such information, we suggest the use of RP. Moreover, available information can be partial or wrong. Then, using an ad hoc procedure would be disastrous whereas a general device like RP would still work. In short, choose RP if you have no useful information or if you do not trust them.

Other model selection procedures by resampling

The most well-known resampling-based model selection procedure is cross-validation. For practical reasons, it is often used in its V -fold version which can have some tricky behavior, in particular for choosing V [START_REF] Yang | Consistency of cross validation for comparing regression procedures[END_REF][START_REF] Arlot | V -fold cross-validation improved: V -fold penalization[END_REF]. This can also be showed in the simulation experiments of Section 5 (see Table 3): In HSd1, V = 2 performs better than V ∈ { 5, 10, 20}, a phenomenon explained in [START_REF] Arlot | V -fold cross-validation improved: V -fold penalization[END_REF] by analyzing how the bias of the V -fold criterion depends on V .

V -fold penalization, that is, RP with a V -fold subsampling scheme, was proposed in [START_REF] Arlot | V -fold cross-validation improved: V -fold penalization[END_REF] where it was showed to improve significantly the model selection performance of VFCV. In this paper and in [START_REF] Arlot | Technical appendix to "Model selection by resampling penalization[END_REF], RP with several exchangeable resampling schemes -generalizing the V = n case-is proved to perform at least as well as V -fold penalization and often better.

Several penalization procedures use the bootstrap for estimating the ideal penalty [START_REF] Efron | Estimating the error rate of a prediction rule: improvement on cross-validation[END_REF][START_REF] Cavanaugh | A bootstrap variant of AIC for state-space model selection[END_REF][START_REF] Shibata | Bootstrap estimate of Kullback-Leibler information for model selection[END_REF]. As noticed in Remark 6, the penalization procedures studied by Shibata [START_REF] Shibata | Bootstrap estimate of Kullback-Leibler information for model selection[END_REF] are quite close to RP, although they are restricted to bootstrap weights, which are the worst ones in the framework of the present paper (see Sections 4.1 and 6.2). Moreover, they do not consider useful to multiply the penalty by a factor C possibly different from one, contrary to what is suggested in RP. The factor C is crucial because it disconnects the choice of the weights from the overpenalization problem.

In order to select the correct model asymptotically with probability one, Shao [START_REF] Shao | Bootstrap model selection[END_REF] proposed to use RP with the M n out of n bootstrap and provided a sufficient condition on M n to achieve model consistency. Thanks to the unified approach for all the exchangeable resampling weights provided in this paper, Shao's condition can be rewritten as C = 1 ≫ C W (see Remark 6), which corresponds to the known fact that model consistency requires overpenalization within a factor tending to infinity with n [START_REF] Aerts | Testing the fit of a parametric function[END_REF]. Hence, we conjecture that RP with a constant C ≫ C W is model consistent for most exchangeable W , which may improve Shao's penalties since Efr(M n ) weights are probably not the best weights in terms of accuracy (see Section 4) and variability13 .

Resampling Penalization in the general prediction framework

As mentioned in Section 2.1, Resampling Penalization is a general-purpose method which is definitely not restricted to the histogram selection problem. The purpose of this subsection is to define properly RP in the general prediction framework and to discuss briefly what differences can be expected compared to the histogram selection framework.

Framework

Suppose we observe some data (X 1 , Y 1 ), . . . , (X n , Y n ) ∈ X × Y independent with common distribution P . The goal is to predict Y given X where (X, Y ) ∼ P is independent of the data. The quality of a predictor t : X → Y is measured by the prediction loss P γ(t) := E (X,Y ) [ γ(t, (X, Y )) ] where (X, Y ) ∼ P and γ is a given contrast function. Typically, γ(t, (x, y)) measures the discrepancy between t(x) and y. The excess loss is defined as ℓ ( s, t ) := P γ ( t )inf t:X →Y P γ ( t ), even if s = arg min t { P γ ( t ) } is not well-defined. Classical examples are least-squares regression where Y = R and γ(t, (x, y)) = (t(x) -y) 2 and binary supervised classification where Y = { 0, 1 } and γ(t, (x, y)) = 1 t(x) =y is the 0-1 contrast.

A general prediction algorithm s is then defined as a function associating a predictor to any data sample. In order to simplify the presentation, algorithms are assumed to depend only on the empirical distribution P n = n -1 n i=1 δ (Xi,Yi) as an input 14 . For instance, the empirical risk minimizer over a set S m of predictors is defined as s m (P n ) := arg min t∈Sm P n γ ( t ), provided the minimum in S m exists and is unique.

Let us assume that a collection of algorithms ( s m ) m∈Mn is given. The goal is to select some data-dependent m ∈ M n minimizing the prediction loss P γ ( s m (P n ) ). The penalization method consists in selecting m ∈ arg min

m∈Mn { P n γ ( s m ( P n ) ) + pen(m) } ,
where pen : M n → R is a penalty function, possibly data-dependent. Since the goal is to minimize the prediction loss, the ideal penalty is pen id (m) := (P -P n )γ ( s m (P n ) ) = F m (P, P n ) which cannot be used because it depends on the unknown distribution P . When M n is not too large (for instance, when Card(M n ) ≤ Cn α for some positive constants C, α), a natural strategy is to define pen(m) as an estimator of pen id (m) with a bias as small as possible.

Definition of Resampling Penalization

As detailed in Section 2.2, the resampling heuristics can be used for estimating E [ pen id (m) ] = E [ F m (P, P n ) ], leading to the following procedure.

Procedure 3 (Resampling Penalization).

1. Replace M n by

M n = {m ∈ M n s.t. s m (P n ) is well-defined } .
2. Choose a resampling scheme, that is the distribution D(W ) of a weight vector W . 3. Choose a constant C ≥ C W . 4. Compute the following resampling penalty for each m ∈ M n :

pen(m) = CE W P n γ s m P W n -P W n γ s m P W n , (28)
where

P W n := n -1 n i=1 W i δ (Xi,Yi) . 5. Select m ∈ arg min m∈ Mn { P n γ ( s m ( P n ) ) + pen(m) }.
As for the histogram selection problem, two possible problems have to be solved. First, s m (P W n ) may not be well-defined for a.e. W even if m ∈ M n . A way to define properly the resampling penalty for every m ∈ M n such that s m (P W n ) is well-defined for every W ∈ (0, +∞) n is suggested in [6, Section

. This assumption is satisfied by regressograms (hence, in the framework of the rest of the paper) for which the suggest of [6, Section 8.1] yields exactly the penalty [START_REF] Arlot | Suboptimality of penalties proportional to the dimension for model selection in heteroscedastic regression[END_REF].

Second, the constant C W such that (28) estimates unbiasedly pen id (m) when C = C W is required in Procedure 3. For the histogram selection problem, the explicit expression of C W follows from Propositions 1 and 2. In general, the asymptotic theory of exchangeable bootstrap empirical processes [66, Theorem 3.6.13] suggests that C W = 1 if var(W 1 ) ≪ 1, which holds for the classical weights Efr, Rad, Poi and Rho; nevertheless, asymptotic control on the bias is not sufficient when the collection of algorithms is allowed to depend on the sample size n, as in the histogram selection problem. Therefore, further theoretical investigations would be useful to compute the theoretical value of C W to be used in Procedure 3. From the practical point of view, the data-driven calibration algorithm of [START_REF] Arlot | Data-driven calibration of penalties for least-squares regression[END_REF] can be used for choosing the constant C in front of the resampling penalty.

Model selection properties of Resampling Penalization

The theoretical validity of Procedure 3 is only proved for histogram model selection in this paper, because precise non-asymptotic controls of the ideal penalty and its resampling counterpart are needed. To our knowledge, the only known result about model selection with Resampling Penalization was that RP with the classical bootstrap weights (Efr) is asymptotically optimal for selecting among maximum likelihood estimators in [START_REF] Shibata | Bootstrap estimate of Kullback-Leibler information for model selection[END_REF], assuming that the distribution P belongs to some parametric family of densities.

RP can be conjectured to enjoy adaptivity properties for a wide class of model selection problems for two main reasons. First, RP relies on the resampling idea which is known to be robust in a wide variety of frameworks; Theorems 1 and 2 have confirmed the robustness of RP to heteroscedasticity, whereas RP has not been designed specifically for least-squares regression with heteroscedastic data. Second, several of the key concentration inequalities used to prove Theorems 1 and 2 have been extended in [START_REF] Arlot | Data-driven calibration of penalties for least-squares regression[END_REF]Propositions 8 and 10] to a general framework including bounded regression and binary classification.

As mentioned at the end of Section 7.2.1, Procedure 3 should be restricted to choosing among a number of algorithms at most polynomial in n. Indeed, when Card(M n ) is larger, estimating unbiasedly pen id can yield strong overfitting [START_REF] Birgé | Minimal penalties for Gaussian model selection[END_REF]. Therefore, RP must be modified for large collections M n . We suggest to group algorithms according to some modelling complexity index C m , such as the dimension of S m if s m is the empirical risk minimizer over some vector space S m ; then, for every

C ∈ C n = { C m s.t. m ∈ M n }, define s C := s m(C)
where m(C) ∈ arg min Cm=C P n γ ( s m (P n ) ); finally, apply Procedure 3 to the collection ( s C ) C∈Cn , assuming that Card ( C n ) is at most polynomial in n.

Related penalties for classification

In the classification framework, RP should be compared to several classical resampling-based penalization methods. First, RP with Efr weights was first introduced by Efron [START_REF] Efron | Estimating the error rate of a prediction rule: improvement on cross-validation[END_REF] and called bootstrap penalization; its main drawback is its bias (as for the histogram selection problem), which can be corrected in several ways, using for instance the double bootstrap penalization or the .632 bootstrap [START_REF] Efron | Estimating the error rate of a prediction rule: improvement on cross-validation[END_REF]. Nevertheless, the computational cost of the double bootstrap is heavy and the general validity of the .632 bootstrap is questionable because of its poor theoretical grounds.

Second, the global Rademacher complexities were introduced in order to obtain theoretically validated model selection procedures in classification [START_REF] Koltchinskii | Rademacher penalties and structural risk minimization[END_REF][START_REF] Peter | Model selection and error estimation[END_REF]. They are resampling estimates of pen id,g (m) := sup t∈Sm

{ (P -P n )γ(t) } ≥ (P -P n )γ ( s m (P n ) ) = pen id (m),
with Rad weights; more recently, Fromont [START_REF] Fromont | Model selection by bootstrap penalization for classification[END_REF] generalized global Rademacher complexities to a wide family of exchangeable resampling weights and obtained non-asymptotic oracle inequalities. Nevertheless, global complexities (that is, estimates of pen id,g ) are too large compared to pen id so that they cannot achieve fast rates of estimation when the margin condition [START_REF] Mammen | Smooth discrimination analysis[END_REF] holds.

Therefore, localized penalties taking into account the closeness between s m (P n ) and s have been introduced, in particular local Rademacher complexities [START_REF] Lugosi | Complexity regularization via localized random penalties[END_REF][START_REF] Peter | Local Rademacher complexities[END_REF][START_REF] Peter | Local complexities for empirical risk minimization[END_REF][START_REF] Koltchinskii | Local Rademacher complexities and oracle inequalities in risk minimization[END_REF]; these papers proved sufficiently tight oracle inequalities to ensure that the final prediction loss can achieve fast rates. Nevertheless, local Rademacher complexities are computationally heavy and depend on several constants which are difficult to calibrate.

RP aims at combining the advantages of these three approaches in classification. From the practical point of view, RP is computationally tractable (see Section 6.1) and reasonably easy to calibrate (see Section 6.3). Compared to global Rademacher complexities, resampling penalties estimate directly pen id , so that RP should be able to achieve fast rates of estimation when the margin condition holds. Finally, contrary to the bootstrap penalty, RP can be used with several resampling weights including i.i.d. Rademacher weights (Rad), so that the bias of RP may not have to be corrected.

Conclusion

This article intends to help the practicioner to answer the following question: When should Resampling Penalization be used? To sum up, we list below the advantages and drawbacks of RP vs. the classical methods.

Advantages of RP

• generality: well-defined in almost any framework.

• robustness and versatility: designed for the cautious user.

• adaptivity to several properties, in particular heteroscedasticity and smoothness of the target. • flexibility: possibility of overpenalization, either for non-asymptotic prediction or for identification.

Drawbacks of RP

• computation time: one may prefer V -fold procedures such as V -fold crossvalidation or V -fold penalties [START_REF] Arlot | V -fold cross-validation improved: V -fold penalization[END_REF]. • possibly outperformed by Mallows' C p (for easy problems) or ad hoc procedures (in some particular frameworks, when some information on the data is available).

Proofs

Notation

Before starting the proofs, we introduce some additional notation and conventions:

• The letter L denotes "some positive absolute constant, possibly different from some place to another". In the same way, a positive constant which depends on c 1 , . . . , c k is denoted by L c1,...,c k ; if (A) denotes a set of assumptions, L (A) denotes any positive constant depending on the parameters appearing in (A).

• By convention, ∞1 E and 1 E /0 are both equal to zero when the event E does not hold. • For any x ∈ R, x + := x ∨ 0 = max(x, 0) and x -:= (-x) ∨ 0.

• For any non-negative random variable Z, e 0 D(Z)

:= E [ Z ] E Z -1 1 Z>0 . • For any model m ∈ M n , p 1 (m) := P ( γ( s m ) -γ(s m ) ) p 2 (m) := P n ( γ(s m ) -γ( s m ) )
δ(m) := (P n -P ) ( γ(s m ) -γ(s) ) .

• Histogram-specific notation: for any q > 0, m ∈ M n , λ ∈ Λ m and any random variable Z,

E Λm [ Z ] := E Z | ( 1 Xi∈I λ ) 1≤i≤n, λ∈Λm Z (Λm) q := E Λm [ |Z| q ] 1/q m q,λ := Y -s m (X) q,λ := (E [|Y -s m (X)| q | X ∈ I λ ]) 1/q S λ,1 := Xi∈I λ ( Y i -β λ ) and S λ,2 := Xi∈I λ (Y i -β λ ) 2 .
• Conventions for p 1 and p 2 when s m is not well-defined (in the histogram framework):

p 1 (m) := p 1 (0) (m) + λ∈Λm p λ (σ λ ) 2 1 p λ =0 with p 1 (0) (m) := λ∈Λm p λ 1 p λ >0 (n p λ ) 2 S 2 λ,1 and p 2 (m) := p 2 (m) + 1 n λ∈Λm (σ λ ) 2 1 n p λ =0
Note that p 1 (m) = p 1 (0) (m) = p 1 (m) and p 2 (m) = p 2 (m) are well-defined when s m is uniquely defined, and other models are always removed from M n . The above convention is only important when writing expectations, so it is merely technical. In the following, p 1 (resp. p 2 ) will often be written simply p 1 (resp. p 2 ).

Using the above notations, p 1 (m) and p 2 (m) can now be computed explicitly for histogram models. For any m ∈ M n such that min λ∈Λm p λ > 0,

p 1 (m) = λ∈Λm p λ β λ -β λ 2 = 1 n λ∈Λm p λ p λ S 2 λ,1 n p λ ( 29
)
p 2 (m) = λ∈Λm p λ β λ -β λ 2 = 1 n λ∈Λm 1 n p λ >0 S 2 λ,1 n p λ (30)
since β λ -β λ = S λ,1 /(n p λ ).

General framework

The main results (Theorems 1 and 2) actually are corollaries of a more general oracle inequality (Lemma 7). First, two different assumption sets under which Lemma 7 holds are stated in this subsection. The first one (Bg) deals with bounded data, the second one (Ug) with unbounded data.

Bounded assumption set (Bg)

There is some noise:

σ(X) 2 > 0. (P1) Polynomial size of M n : Card(M n ) ≤ c M n αM . (P2) Richness of M n : ∃m 0 ∈ M n s.t. D m0 ∈ [ √ n; c rich √ n ]. (P3)
The weight vector W is exchangeable, among Efr, Rad, Poi, Rho and Loo. (P4) The constant C is well chosen:

ηC W ≥ C ≥ C W . (Ab) Bounded data: Y i ∞ ≤ A < ∞.
(A m,ℓ ) Local moment assumption: there exist a ℓ , ξ ℓ , D 0 ≥ 0 such that for every q ≥ 2, for every m ∈ M n such that D m ≥ D 0 ,

P ℓ m (q) := D m λ∈Λm m 4 q,λ λ∈Λm m 2 2,λ
≤ a ℓ q ξ ℓ .

(Ap) Polynomially decreasing bias: there exist

β 1 ≥ β 2 > 0 and C + b , C - b > 0 such that, for every m ∈ M n , C - b D -β1 m ≤ ℓ ( s, s m ) ≤ C + b D -β2 m .
(A Q ) There exist c - Q > 0 and D 0 ≥ 0 such that for every m ∈ M n with D m ≥ D 0 ,

Q (p) m := nE [ p 2 (m) ] D m = 1 D m λ∈Λm σ 2 λ ≥ c - Q > 0.
(Ar X ℓ ) Lower regularity of the partitions for D(X): there exists c X r,ℓ > 0 such that for every m ∈ M n , D m min λ∈Λm p λ ≥ c X r,ℓ .

Unbounded assumption set (Ug)

(Ab) is replaced in (Bg) by (Aσ max ) Noise-level bounded from above: σ 2 (X) ≤ σ 2 max < ∞ a.s. (As max ) Bound on the target function: s ∞ ≤ A < ∞.

(A g,ǫ ) Global moment assumption for the noise: there exist a gǫ , ξ gǫ ≥ 0 such that for every q ≥ 2, P gǫ (q) := ǫ q ≤ a gǫ q ξgǫ .

(Aδ) Global moment assumption for the bias: there exists c g ∆,m > 0 such that for every m ∈ M n with D m ≥ D 0 ,

s -s m ∞ ≤ c g ∆,m s(X) -s m (X) 2 .

General result

Lemma 7. Let n ∈ N\ { 0 }, γ 0 > 0 and m be defined by Procedure 1. Assume that either (Bg) or (Ug) holds with constants independent of n.

Then, there exists a constant K 1 (that depends on γ 0 and all the constants in (Bg) (resp. (Ug)), but not on n) such that ℓ s, s m ≤ 2η -1 + ( ln(n) )

-1/5 inf m∈Mn { ℓ ( s, s m ) } ( 31
)
holds with probability at least 1 -K 1 n -γ0 .

Lemma 7 is proved in Section 8.7. Remark 8. If the lower bound in (Ap) is removed from the assumption set, then there exist constants γ 1 , γ 2 > 0 (depending only on ξ ℓ , resp. on ξ ℓ and ξ gǫ ) and an event of probability at least 1 -K 1 n -γ0 on which

ℓ s, s m ≤ 2η -1 + ( ln(n) ) -1/5 inf m∈Mn Dm≥( ln(n) ) γ 1 { ℓ ( s, s m ) } + ( ln(n) ) γ2 n . (32)
This assertion is proved in Section 8.7.3.

Remark 9. In the infimum in [START_REF] Efron | How biased is the apparent error rate of a prediction rule?[END_REF], s m may not be well-defined for some m ∈ M n . By convention ℓ ( s, s m ) is defined as +∞ for these m.

From the proof of Lemma 7, there exists a constant c > 0 (depending on α M , γ 0 and c X r,ℓ ) such that every model of dimension smaller than cn ( ln(n) )

-1

belongs to M n on the event where (31) holds. For each of these models,

ℓ ( s, s m ) = ℓ ( s, s m ) + p 1 (0) (m) = ℓ ( s, s m ) + p 1 (m)
so that the infimum can be restricted to models of dimension smaller than cn ( ln(n) ) -1 with any of these conventions for ℓ ( s, s m ).

The main results of the paper (Theorems 1 and 2) can now be proved, which is done in Sections 8.3-8.5.

First, the assumptions of Theorem 1 imply (Bg). Second, the alternative assumption sets stated in Section 3.3.2 imply (Bg). Third, the assumptions of Theorem 2 imply (Bg) except the lower bound in (Ap), so that Remark 8 can be used instead of Lemma 7.

Proof of Theorem 1

Lemma 7 is applied with γ 0 = 2. In order to deduce [START_REF] Arlot | Technical appendix to "Model selection by resampling penalization[END_REF], it remains to show that (A m,ℓ ) and (A Q ) are satisfied. Both hold with D 0 = 1 since for every m ∈ M n ,

P ℓ m (q) = λ∈Λm m 4 q,λ √ D m Q (p) m ≤ Y -s m (X) 2 ∞ Q (p) m ≤ 4A 2 Q (p) m (33)
Q (p) m := 1 D m λ∈Λm ( σ r λ ) 2 + σ d λ 2 ≥ σ 2 min .
Let Ω n be the event on which (8) holds true. Then,

E ℓ s, s m = E ℓ s, s m 1 Ωn + E ℓ s, s m 1 Ω c n ≤ [ 2η -1 + ε n ] E inf m∈Mn { ℓ ( s, s m ) } + A 2 K 1 P ( Ω c n )
which proves [START_REF] Arlot | V -fold cross-validation improved: V -fold penalization[END_REF]. Following Remark 9, (9) also holds with M n replaced by

m ∈ M n s.t. D m ≤ c(α M , c X r,ℓ )n ( ln(n) ) -1
and the convention p 1 (m) = p 1 (0) (m).

Proof of Theorem 1: alternative assumptions

In this section, the statements of Section 3.3.2 are proved.

No uniform lower bound on the noise-level

When σ min = 0 in (An), Lemma 8 below proves that (A Q ) also holds with D 0 = L (Bg) . Therefore, using [START_REF] Fromont | Model selection by bootstrap penalization for classification[END_REF], (A m,ℓ ) holds with the same D 0 .

Lemma 8. Let X ⊂ R k , m ∈ M n , and assume that positive constants c d r,u , α d , c r,u , K σ , J σ exist such that

(Ar d u ) max λ∈Λm { diam(I λ ) } ≤ c d r,u D -α d m diam(X), (Ar u ) max λ∈Λm { Leb(I λ ) } ≤ c r,u D -1
m and (Aσ) σ is piecewise K σ -Lipschitz with at most J σ jumps.

Then,

Q (p) m ≥ Leb(X ) σ 2 L 2 (Leb) 2c r,u - K 2 σ c d r,u 2 diam(X ) 2 D 2α d m - J σ σ(X) 2 ∞ 2D m .
Lemma 8 is proved in the technical appendix [START_REF] Arlot | Technical appendix to "Model selection by resampling penalization[END_REF]. Remark 10. Since σ(X) 2 > 0 and σ is piecewise Lipschitz, σ L 2 (Leb) > 0.

Thus, the lower bound on Q (p) m is positive when D m is large enough.

Unbounded data

We still use Lemma 7, but the proof is a little longer and requires the following Lemma 9 which is proved in the technical appendix [START_REF] Arlot | Technical appendix to "Model selection by resampling penalization[END_REF].

Lemma 9. Assume that X ⊂ R is bounded and the following:

(Al) ∃B, B 0 , c J > 0 such that s : X → R is B-Lipschitz, piecewise C 1 and nonconstant (that is, ±s ′ ≥ B 0 on some interval J ⊂ X with Leb(J) ≥ c J ). (Ar ℓ,u ) Regularity of the partitions for Leb: ∃c r,ℓ , c r,u > 0 such that

∀m ∈ M n , ∀λ ∈ Λ m , c r,ℓ D -1 m ≤ Leb(I λ ) ≤ c r,u D -1 m .
(Ad ℓ ) Density bounded from below: ∃c min X > 0, ∀I ⊂ X , P (X ∈ I) ≥ c min X Leb(I). Then, (Aδ) holds true, that is, for every model

S m of dimension D m ≥ D 0 , s -s m ∞ ≤ c g ∆,m s(X) -s m (X) 2 with c g ∆,m = c r,u c r,ℓ 3/2 B √ 24 B 0 c min X c J and D 0 := 4c r,u c -1 J .
Pathwise oracle inequality We prove that (8) holds with probability 1 -K 1 n -γ0 for a general γ 0 , since it will be required for proving a classical oracle inequality below. First, (A m,ℓ ), (A Q ) and (A g,ǫ ) hold since for every m ∈ M n

P ℓ m (q) = λ∈Λm m 4 q,λ √ D m Q (p) m ≤ 2A + c gauss √ qσ max 2 Q (p) m ≤ qL cgauss,σmax,A Q (p) m Q (p) m ≥ σ 2 min P gǫ (q) ≤ σ max c gauss √ q.
Second, Lemma 9 (with (Al), (Ar ℓ,u ) and (Ad ℓ )) shows that (Aδ) holds with c g ∆,m = L (Ug) and D 0 = L (Ug) .

Classical oracle inequality Let Ω n be the event on which (8) holds true with γ 0 = 6 + α M . As in the bounded case, it suffices to upper bound

E Λm ℓ s, s m 1 Ω c n ≤ P(Ω c ) E Λm ℓ s, s m 2 by Cauchy-Schwarz ≤ K 1 n -γ0/2 E Λm 2 s 2 ∞ + 2p 1 ( m) 2 ≤ L (Ug) n -γ0/2   1 + E Λm m∈Mn p 1 (m) 2 1 m∈ Mn   .
For every m ∈ M n , a bound on E Λm [(p 1 (m)) 2 ] is required. Starting from ( 29),

E Λm p 1 (m) 2 = 1 n 2 λ∈Λm p λ p λ 2 E Λm S 4 λ,1 (n p λ ) 2 + 1 n 2 λ =λ ′ p λ p λ p λ ′ p λ ′ m 2 2,λ m 2 2,λ ′ ≤ λ∈Λm E Λm S 4 λ,1 (n p λ ) 2 + λ =λ ′ σ 2 max + (2A) 2 2 ≤ D 2 m L (Ug) ≤ n 2 L (Ug) since E Λm S 4 λ,1 (n p λ ) 2 = E Λm Xi∈I λ (Y i -β λ ) 4 (n p λ ) 2 = m 4 4,λ n p λ + 6(n p λ -1)m 4 2,λ n p λ and D m λ∈Λm m 4 q,λ ≤ a ℓ q ξ ℓ 2 σ 2 max + (2A) 2 2 .
Hence, using that Card(M n ) ≤ c M n αM ,

E Λm ℓ s, s m 1 Ω c n ≤ L (Ug) n 1+(αM-γ0)/2
which proves (9).

Proof of Theorem 2

In this proof, (H) denotes the set of assumptions made in Theorem 2. (H) implies all the assumptions of Theorem 1 except maybe the lower bound in (Ap); indeed, (Ad ℓ ) and the fact that all the models are "regular" imply (Ar X ℓ ). Therefore, we can start from [START_REF] Efron | Improvements on cross-validation: the .632+ bootstrap method[END_REF] in Remark 8 below Lemma 7 which does not require the lower bound in (Ap) to hold. The constants γ i are absolute because the data are bounded.

Let m(T 0 ) ∈ M n be the model of dimension

T k 0 closest to R 2k 2α+k n k 2α+k σ -2k 2α+k
max . By definition of T 0 and M n ,

2 -1 R 2 2α+k n 1 2α+k σ -2 2α+k max ≤ T 0 ≤ 2R 2 2α+k n 1 2α+k σ -2 2α+k max .
If n ≥ L (H),c , T k 0 is larger than ( ln(n) ) γ1 and smaller than cn ( ln(n) ) -1 . Hence, from the proof of Lemma 7, m(T 0 ) ∈ M n and m(T 0 ) has a finite excess loss on the large probability event of Lemma 7. Moreover,

ℓ s, s m(T0) ≤ ℓ s, s m(T0) + LE p 1 (0) (m(T 0 )) when n ≥ L (H) . Since ℓ s, s m(T0) ≤ R 2 T -2α 0 and E p 1 (0) (m(T 0 )) ≤ sup np≥0 e 0 B(n,p) 1 n λ∈Λ m(T 0 ) (σ r λ ) 2 + σ d λ ≤ 2R 2 T 1-2α 0 n + 2σ 2 max D m(T0) n
(the bound e 0 B(n,p) ≤ 2 coming from [START_REF] Györfi | A distribution-free theory of nonparametric regression[END_REF]Lemma 4.1]), an event of probability at least 1 -K ′ 1 n -2 exists on which

ℓ s, s m ≤ K 2 R 2k 2α+k n -2α 2α+k σ 4α 2α+k max + ( ln(n) ) γ2 n ,
where K 2 may only depend on k and α. Note that the constant K 1 has been replaced by K ′ 1 ≥ K 1 so that the probability bound 1 -K ′ 1 n -2 is nonpositive when n is too small. Enlarging K ′ 1 once more, the term ( ln(n) ) γ2 n -1 can be dropped off by adding 1 to the constant K 2 . Then, taking expectations as in the proof of Theorem 1, (10) holds. When (Aσ) holds, σ max can be replaced by σ L 2 (Leb) in the definition of m(T 0 ). Then, for every λ ∈ Λ m(T0) such that σ does not jump on I λ , (σ r λ ) 2 ≤ max

I λ σ 2 ≤ K σ T 0 + X σ 2 (t) Leb(dt) 2 ≤ 1 + θ -1 K 2 σ T 2 0 + (1 + θ) X σ 2 (t) Leb(dt)
for every θ > 0 (since Leb(X ) = 1). If σ jumps on I λ (and there exist at most

J σ such λ), max I λ σ 2 ≤ σ 2 max . Hence, taking θ = T -1 0 , E p 1 (0) (m(T 0 )) ≤ 2 n   R 2 T 1-2α 0 + λ∈Λ m(T 0 ) (σ r λ ) 2   ≤ 2R 2 T 1-2α 0 n + 2D m(T0) σ 2 L 2 (Leb) n + L (H) n
and the end of the proof does not change. In this second case, (An) can also be removed because all the assumptions stated in the first part of Section 3.3.2 are satisfied.

Additional probabilistic tools

Several probabilistic results are needed in addition to the ones of Section 3.4 for proving Lemma 7. First, Proposition 10 below deals with concentration properties of p 1 and p 2 . Remark that concentration inequalities for p 2 can be obtained in a general framework [START_REF] Arlot | Data-driven calibration of penalties for least-squares regression[END_REF]Proposition 10]. On the contrary, we do not know any other non-asymptotic bound on the two-sided deviations of p 1 .

Proposition 10. Let γ > 0 and S m be the model of histograms associated with some partition (I λ ) λ∈Λm of X . Assume that min λ∈Λm { np λ } ≥ B n and that positive constants a ℓ , ξ ℓ exist such that (A m,ℓ ) ∀q ≥ 2, P ℓ m (q) ≤ a ℓ q ξ ℓ . Then, if B n ≥ 1, an event of probability at least 1 -Ln -γ exists on which

p 1 (m) ≥ E [ p 1 (m) ] -L a ℓ ,ξ ℓ ,γ ( ln(n) ) ξ ℓ +2 √ D m + e -LBn E [ p 2 (m) ] p 1 (m) ≤ E [ p 1 (m) ] + L a ℓ ,ξ ℓ ,γ ( ln(n) ) ξ ℓ +2 √ D m + D m e -LBn E [ p 2 (m) ] (34) |p 2 (m) -E[p 2 (m)]| ≤ L a ℓ ,ξ ℓ ,γ ( ln(n) ) ξ ℓ +1 √ D m E [ p 2 (m) ] .
Moreover, if B n > 0, an event of probability at least 1 -Ln -γ exists on which

p 1 (m) ≥ 1 2 + (γ+1) ln(n) Bn -L a ℓ ,ξ ℓ ,γ ( ln(n) ) ξ ℓ +2 √ D m + e -LBn E [ p 2 (m) ] . ( 35
)
Proposition 10 is proved in [START_REF] Arlot | Technical appendix to "Model selection by resampling penalization[END_REF]. Second, Lemmas 11 and 12 below provide concentration inequalities for δ(m), when the data are either bounded or unbounded.

Lemma 11. Assume that Y

∞ ≤ A < ∞. Recall that for every m ∈ M n , δ(m) = (P n -P ) ( γ ( s m ) -γ ( s ) ).
Then for every x ≥ 0, an event of probability at least 1 -2e -x exists on which

∀η > 0, δ(m) ≤ ηℓ ( s, s m ) + 4 η + 8 3 A 2 x n . (36)
In particular,

δ(m) ≤ ℓ ( s, s m ) √ D m + 20 3 A 2 Q (p) m E Λm [p 2 (m)] √ D m x. ( 37
)
Proof of Lemma 11. (36)

(A g,ǫ ) ∀q ≥ 2, P gǫ (q) ≤ a gǫ q ξgǫ , (Aσ max ) σ(X) ∞ ≤ σ max , (Aδ) s -s m ∞ ≤ c g ∆,m s(X) -s m (X) 2 .
Then, for every x ≥ 0, an event of probability at least 1 -e -x exists on which

δ(m) ≤ L agǫ,ξgǫ,c g ∆,m x ξgǫ+1/2 √ D m ℓ ( s, s m ) + σ 2 max Q (p) m E [ p 2 (m) ] . (38)
Moreover, if (A g,ǫ ) and (Aσ max ) holds true, but (Aδ) is replaced by (As max ) s ∞ ≤ A, then, for every x ≥ 0, an event of probability at least 1 -e -x exists on which δ(m) ≤ L agǫ,ξgǫ,A,σmax n -1/2 x ξgǫ+1/2 . (

) 39
Lemma 12 is proved in Section 8.10. Third, Lemma 13 ensures that empirical frequencies n p λ are not too far from the expected ones np λ . Lemma 13. Let (p λ ) λ∈Λm be non-negative real numbers of sum 1, (n p λ ) λ∈Λm be a multinomial vector of parameters (n; (p λ ) λ∈Λm ) and γ > 0. Assume that Card(Λ m ) ≤ n and min λ∈Λm { np λ } ≥ B n > 0. Then, an event of probability at least 1 -Ln -γ exists on which

min λ∈Λm { n p λ } ≥ min λ∈Λm { np λ } 2 -2(γ + 1) ln(n). ( 40
)
Proof of Lemma 13. First, for every λ ∈ Λ m , Bernstein's inequality [55, Proposition 2.9] applied to n p λ shows that an event of probability at least 1-2n -(γ+1) exists on which

n p λ ≥ np λ -2np λ (γ + 1) ln(n) - (γ + 1) ln(n) 3 .
Since 2np λ (γ + 1) ln(n) ≤ (np λ )/2 + (γ + 1) ln(n), [START_REF] Hall | On general resampling algorithms and their performance in distribution estimation[END_REF] holds on an event of probability at least 1

-2 Card(Λ m )n -(γ+1) ≥ 1 -2n -γ .
Finally, Lemmas 14 and 15 below are useful to compare the expectations of p 1 and p 2 on the one hand, and the expectations of pen and pen id for possibly large models on the other hand.

Lemma 14 (Lemma 7 of [START_REF] Arlot | V -fold cross-validation improved: V -fold penalization[END_REF]).

If min λ∈Λm { np λ } ≥ B ≥ 1, 1 -e -B E [ p 2 (m) ] ≤ E p 1 (0) (m) ≤ E [ p 1 (m) ] ≤ 1 + sup np≥B δ n,p E [ p 2 (m) ]
where δ n,p is the same as in [START_REF] Barbe | The weighted bootstrap[END_REF]. A similar result holds with p 2 instead of p 2 inside the expectation.

Lemma 15. Assume that W is a weight vector among Efr, Rad, Poi, Rho and Loo. Let S m be the model of histograms associated with the partition (I λ ) λ∈Λm , p 2 (m) = P n ( γ(s m ) -γ( s m ) ) and pen(m) be defined by [START_REF] Arlot | Suboptimality of penalties proportional to the dimension for model selection in heteroscedastic regression[END_REF] with C = C W (see Table 2). Then, if min λ∈Λm { n p λ } ≥ 3,

E Λm [ pen(m) ] ≥ 5 4 E Λm [ p 2 (m) ] . (41)
If min λ∈Λm { n p λ } ≥ T for some positive T , (41) still holds for weight vectors among:

• Efr(M n ) when M n n -1 ≥ -T -1 ln(3/4 -2/T ) • Rad(p) when T ≥ p -1 ln[8/(3(1 -p))] • Poi(µ) when T ≥ 3 and µT ≥ 1.61 • Rho(q n ) when T ≥ nq -1 n ln[(4n)/(3(n -q n ))
]. Lemma 15 is proved in Section 8.9.

Proof of Lemma 7

We first give the complete proof in the bounded case. Then, we will explain how it can be extended to the unbounded case.

Bounded case

For every m ∈ M n , define

pen ′ id (m) := p 1 (m) + p 2 (m) -δ(m) = pen id (m) -(P -P n )γ(s).
By definition of pen ′ id and m, for every m ∈ M n ,

ℓ s, s m -( pen ′ id ( m) -pen( m) ) ≤ ℓ ( s, s m ) + ( pen(m) -pen ′ id (m) ) . ( 42
)
The proof of Lemma 7 is divided into three main parts:

1. With a large probability, penpen ′ id is negligible in front of ℓ ( s, s m ) uniformly over models S m of "intermediate" dimension, that is ( ln(n) ) γ1 ≤ D m ≤ cn ( ln(n) )

-1 for some constants c, γ 1 > 0. This relies on the concentration inequalities and comparisons of expectations stated in Sections 3.4 and 8.6. 2. The model m selected by Resampling Penalization has an "intermediate" dimension. In order to prove this, a lower bound on crit ′′ (m) := P n γ ( s m ) + pen(m) -P n γ ( s ) is proved for large and small models, and this bound is showed to be larger than crit ′′ (m 0 ), where S m0 is the model of intermediate dimension belonging to the collection ( S m ) m∈Mn according to assumption (P2). Lemma 15 is crucial at this point. 3. The oracle model (that is the one minimizing ℓ ( s, s m )) is also of "intermediate" dimension, which is proven similarly to point 2 with crit ′′ (m) replaced by ℓ ( s, s m ).

For every m ∈ M n , define

A n (m) := min λ∈Λm { n p λ } and B n (m) = min λ∈Λm { np λ } .
Let Ω n,γ0 be the event on which the concentration inequalities of Propositions 3 and 10 and Lemmas 11 and 13 hold for every m ∈ M n with γ = α M + γ 0 (or similarly x = (α M + γ 0 ) ln(n) in Lemma 11). Using assumption (P1), the union bound gives P ( Ω n,γ0 ) ≥ 1 -L cM n -γ0 .

1. pen is close to pen ′ id for intermediate models Let c, γ 1 > 0 be two constants to be chosen later, and consider M n , the set of m ∈ M n such that ( ln

(n) ) γ1 ≤ D m ≤ cn ( ln(n) ) -1 . According to (Ar X ℓ ), for every m ∈ M n , B n (m) ≥ c X r,ℓ c -1 ln(n) so that (40) ensures that A n (m) ≥ ln(n) on Ω n,γ0 if c ≤ L c X r,ℓ ,αM,γ0 . In particular, M n ⊂ M n on Ω n,γ0 . Assume also that n ≥ exp(D 0 ), so that D m ≥ D 0 for every m ∈ M n if γ 1 ≥ 1. Now, using both bounds on D m , max {| p 1 (m) -E [ p 1 (m) ]| , |p 2 (m) -E [ p 2 (m) ]| , δ(m) , pen(m) -E Λm [ pen(m) ] is smaller than L (Bg) ( ln(n) ) -1 ( ℓ ( s, s m ) + E [ p 2 (m) ] ) on Ω n,γ0 provided that c ≤ L c X r,ℓ ,γ (to ensure that B n (m) is large enough) and γ 1 ≥ 2ξ ℓ + 6. Fix now c = L c X r,ℓ
,γ > 0 and γ 1 = L ξ ℓ satisfying these conditions. Using Proposition 2, Lemma 14 and the lower bound on B n (m), we have for every

m ∈ M n -L (Bg) ( ln(n) ) 1/4 ℓ ( s, s m ) ≤ (pen -pen ′ id )(m) ≤ 2(η -1) + L (Bg) ( ln(n) ) 1/4 ℓ ( s, s m ) .
as soon as n ≥ L (Bg) (this restriction is necessary because the bounds are in terms of ℓ ( s, s m ) instead of ℓ ( s, s m ) + E [ p 2 ]). Combined with [START_REF] Hušková | Consistency of the generalized bootstrap for degenerate U -statistics[END_REF], this gives:

if n ≥ L (Bg) ℓ s, s m 1 m∈ Mn ≤ 2η -1 + L (Bg) ( ln(n) ) 1/4 inf m∈ Mn { ℓ ( s, s m ) } . (43)
′′ (m 0 ) ≤ ℓ ( s, s m0 ) + δ(m 0 ) + pen(m 0 ) ≤ L (Bg) n -β2/2 + n -1/2 . (44)
Therefore, it remains to provide lower bounds on crit ′′ (m) for m / ∈ M n . On the one hand, on Ω

n,γ0 if D m < ( ln(n) ) γ1 , crit ′′ (m) ≥ ℓ ( s, s m ) -δ(m) -p 2 (m) ≥ C - b ( ln(n) ) -γ1β1 -L A,γ0 ln(n) n -L (Bg) ( ln(n) ) 1+ξ ℓ +γ1 n . (45)
On the other hand, if D m > cn ( ln(n) ) -1 and m ∈ M n , by Lemma 15,

E Λm [ pen(m) -p 2 (m) ] ≥ E Λm [ p 2 (m) ] /4. Therefore, we have pen(m)-p 2 (m) ≥ (1 -L (Bg) n -1/4 )E [ p 2 (m) ] on Ω n,γ0 , so that crit ′′ (m) ≥ pen(m) -p 2 (m) -δ(m) ≥ L (Bg) ( ln(n) ) -1 (46)
when n ≥ L (Bg) . Comparing ( 44), ( 45) and ( 46), it follows that any minimizer m of crit over M n belongs to M n on Ω n,γ0 , provided that n ≥ L (Bg) .

3. the oracle has an "intermediate" dimension It remains to prove that the infimum can be extended to M n on the right-hand side of ( 43), with the convention ℓ ( s, s m ) = +∞ if A n (m) = 0. Using similar arguments as above (as well as the definition of Ω n,γ0 , in particular [START_REF] Galtchouk | Adaptive asymptotically efficient estimation in heteroscedastic nonparametric regression via model selection[END_REF] for large models), we have ℓ ( s, s m0 ) ≤ L (Bg) n -β2/2 + n -1/2 on Ω n,γ0 . Moreover, for every m / ∈ M n , either D m < ( ln(n) )

γ1 and ℓ ( s, s

m ) ≥ ℓ ( s, s m ) ≥ L (Bg) ( ln(n) ) -γ1β1 or D m > cn ( ln(n) ) -1 and ℓ ( s, s m ) ≥ p 1 (m) ≥ L (Bg) ( ln(n) ) -2
on Ω n,γ0 by ( 35) as soon as n ≥ L (Bg) . Hence, if n ≥ L (Bg) , m / ∈ M n cannot contribute to the infimum in the right-hand side of [START_REF] Ishiguro | Bootstrapping log likelihood and EIC, an extension of AIC[END_REF]. This concludes the proof of (31) in the bounded case.

Unbounded case

The proof of the bounded case has to be slightly modified. In the definition of Ω n,γ0 , the concentration inequalities of Lemma 11 are replaced by those of Lemma 12. Then, γ 1 has to be chosen such that γ 1 ≥ 2ξ gǫ + 3. The rest of the proof of ( 43) is unchanged.

In order to prove that m ∈ M n , (45) has to be slightly changed because of the use of (39) instead of [START_REF] Geisser | The predictive sample reuse method with applications[END_REF] to bound δ(m). The final part of the proof is then modified similarly.

Proof of Remark 8

We now prove the assertion made in Remark 8 below Lemma 7. Starting from [START_REF] Ishiguro | Bootstrapping log likelihood and EIC, an extension of AIC[END_REF], we can prove in the same way that D m ≤ cn ( ln(n) )

-1 , but D m < ( ln(n) ) γ1 cannot be excluded.

Let m ∈ M n such that D m < ( ln(n) ) γ1 . Assume first that ℓ ( s, s m ) ≥ 2η -1 + ε n 1 -( ln(n) ) -1 inf m∈ Mn { ℓ ( s, s m ) } + ( ln(n) ) ξ ℓ +γ1+2 1 -( ln(n) ) -1 n , (47)
where ε n ≤ L (Bg) ( ln(n) ) -1/4 comes from [START_REF] Arlot | Technical appendix to "Model selection by resampling penalization[END_REF]. Then, on Ω n,γ0 , using [START_REF] Geisser | The predictive sample reuse method with applications[END_REF] with η = ( ln(n) ) -1 and (47),

crit ′′ (m) ≥ ℓ ( s, s m ) -δ(m) -p 2 (m) ≥ (2η -1 + ε n ) inf m∈ Mn { ℓ ( s, s m ) } + ( ln(n) ) ξ ℓ +γ1+1 ln(n) -L (Bg) n ≥ (2η -1 + ε n ) inf m∈ Mn { ℓ ( s, s m ) } + ( ln(n) ) ξ ℓ +γ1+2 2n , (48)
where R 1,W and R 2,W are defined by [START_REF] Baraud | Model selection for regression on a fixed design[END_REF] and [START_REF] Baraud | Model selection for regression on a random design[END_REF], that is

R 1,W (n, p λ ) := E (W 1 -W λ ) 2 W 2 λ X 1 ∈ I λ , W λ > 0 and R 2,W (n, p λ ) := E (W 1 -W λ ) 2 W λ X 1 ∈ I λ .
Proof of Lemma 16. First, as pen id (m) was split into p 1 (m) and p 2 (m) (plus a centered term), the resampling penalty (without the constant C) is split into two terms:

p 1 (m) = λ∈Λm E W p λ β W λ -β λ 2 W λ > 0 ( 51
)
p 2 (m) = λ∈Λm E W p W λ β W λ -β λ 2 . (52)
A key quantity to compute is the following: for every λ ∈ Λ m and W λ > 0,

E W p λ β W λ -β λ 2 W λ = E W   p λ 1 n p λ Xi∈I λ (Y i -β λ ) 1 - W i W λ 2 W λ   = 1 n 2 p λ Xi∈I λ (Y i -β λ ) 2 E W 1 - W i W λ 2 W λ (53) + 1 n 2 p λ i =j Xi∈I λ ,Xj ∈I λ (Y i -β λ )(Y j -β λ )E W 1 - W i W λ 1 - W j W λ W λ .
Since the weights are exchangeable, (W i ) Xi∈I λ is also exchangeable conditionally on W λ and (X i ) 1≤i≤n . Hence, the "variance" term

R V (n, n p λ , W λ , D(W )) := E W W i -W λ 2 W λ
does not depend on i (provided that X i ∈ I λ ) and the "covariance" term

R C (n, n p λ , W λ , D(W )) := E W W i -W λ W j -W λ W λ
does not depend on (i, j) (provided that i = j and X i , X j ∈ I λ ). Moreover,

0 = E W   Xi∈I λ W i -W λ 2 W λ  
Then, the quantity

R V (n, n p λ , W λ , D(W )) = R V ( W λ ) = E W i -W λ 2 W λ
appearing both in R 1,W and R 2,W is the variance of the weight W i conditionally on W λ .

Exchangeable subsampling weights A subsampling weight is defined as any resampling weight W such that W i ∈ {0, κ} a.s. for every i. Such weights can be written W i = κ1 i∈I for some random I ⊂ {1, . . . , n}. Rad and Rho are the two main examples of such weights and they are both exchangeable. This kind of weights are called "bootstrap without replacement weights" in [66, Example 3.6.14]. First, when W is an exchangeable subsampling weight, (60) implies

W λ = E W W i | W λ = κP W i = κ | W λ so that D W i | W λ = κB(κ -1 W λ ) and R V ( W λ ) = W λ (κ -W λ ).
Then, this result is applied to Rad with κ = p -1 and D( W λ ) = (n p λ p) -1 × B(n p λ , p) which proves [START_REF] Praestgaard | Exchangeably weighted bootstraps of the general empirical process[END_REF]. In the Rho case, κ = (n/q) and D( W λ ) = (q p λ ) -1 × H ( n, n p λ , q ) so that (59) follows. The Loo is a particular case of Rho (with q = n -1) and e + H(n,n p λ ,n-1) can be computed with [START_REF] Burman | A comparative study of ordinary cross-validation, v-fold cross-validation and the repeated learning-testing methods[END_REF] in Lemma 5.

Efron Efron weights can also be written

W i = n M Card { 1 ≤ j ≤ M s.t. U j = i } (61)
with (U j ) 1≤j≤M a sequence of independent random variables with uniform distribution over {1, . . . , n}. Therefore, D( W λ ) = (M p λ ) -1 B(M, p λ ) and

D W i | W λ = n M B M p λ W λ , 1 n p λ so that R V ( W λ ) = n M W λ 1 - 1 n p λ
and (56) follows.

Poisson One can check that the weights defined by ( 61) with M = N n ∼ P(µn) independent of the (U j ) j≥1 , are actually Poisson (µ) weights; this is the classical poissonization trick [START_REF] Van Der | Weak convergence and empirical processes[END_REF]Chapter 3.5]. Moreover, conditionally on W λ and N n = M , the same reasoning as for Efron(M ) (with a multiplicative constant µ -1 instead of n/M ) leads to [START_REF] Sauvé | Histogram selection in non Gaussian regression[END_REF].

Concentration inequalities

In this subsection, concentration inequalities are proved for the resampling penalty (Proposition 3) and for δ(m) with unbounded data (Lemma 12).

Proof of Proposition 3

According to [START_REF] Lugosi | Complexity regularization via localized random penalties[END_REF], pen(m) is a U-statistics of order 2 conditionally on (1 Xi∈I λ ) (i,λ) . Then, [9, Lemma 5] with Conditional concentration inequalities follow from the classical link between moments and concentration [6, Lemma 8.10], with a probability bound 1n -γ . Since 1 -n -γ is deterministic, this implies unconditional concentration inequalities.

a λ = R 1
The second statement follows from the proof of Proposition 2 where nonasymptotic upper bounds on 2 + δ (penW) n, p λ = C W × ( R 1,W (n, p λ ) + R 2,W (n, p λ ) ) can be found.

Proof of Lemma 12

From [6, Lemma 8.18] which is stated and proved in [START_REF] Arlot | Technical appendix to "Model selection by resampling penalization[END_REF],

δ(m) q ≤ 2 √ κ √ q √ n F m -E[F m ] q with F m := (Y -s m (X)) 2 -(Y -s(X)) 2
= (s m (X) -s(X)) 2 -2ǫσ(X)(s m (X) -s(X)).

Note that ǫσ(X)(s m (X) -s(X)) is centered conditionally on X ∈ I λ for every λ ∈ Λ m . Hence,

δ(m) q ≤ 2 √ κ √ q √ n s -s m 2 ∞ + 2σ max s -s m ∞ ǫ q . ( 67
)
Using now assumptions (A g,ǫ ) and (Aδ), for every q ≥ 2, δ(m) q ≤ 2 √ κ √ q (c g ∆,m ) 2 ℓ ( s, s m ) + 2c g ∆,m ℓ ( s, s m )P gǫ (q)σ max , [START_REF] Györfi | A distribution-free theory of nonparametric regression[END_REF] follows from the classical link between moments and concentration inequalities [START_REF] Arlot | Resampling and Model Selection[END_REF]Lemma 8.10]. For the second statement, start back from (67) and use that s -s m ∞ ≤ 2A.

Expectations of inverses

This subsection is devoted to the proofs of the lemmas of Section 3.4.3. Note that [9, Section 2 of the Technical appendix] explains how to generalize [START_REF] Peter | Local Rademacher complexities[END_REF] to a wide class of random variables. Two useful results can be found in [9, Technical appendix]: first, the general lower bound e + Z ≥ P(Z > 0), [START_REF] Yang | Consistency of cross validation for comparing regression procedures[END_REF] comes from Jensen inequality. Second, defining

e 0 D(Z) := E [ Z ] E Z -1 1 Z>0 = e + Z P(Z > 0), (69)
the following upper bound holds as soon as P(c Z > Z > 0) = 0:

∀α > 0, e 0 Z = E Z -1 1 αE[Z]>Z>0 E[Z] + E Z -1 1 Z≥αE[Z] E[Z] ≤ P ( αE[Z] > Z > 0 ) E[Z]c -1 Z + α -1 . (70)
8.11.1. Binomial case (proof of [START_REF] Peter | Local complexities for empirical risk minimization[END_REF] in Lemma 4)

When n ≥ 9, the upper bound follows from (69) together with Lemma 4.1 of [START_REF] Györfi | A distribution-free theory of nonparametric regression[END_REF] (showing that e 0 B(n,p) ≤ 2n/(n + 1)). When n ≤ 8, e + B(n,1/2) ≤ 1.21 (see for instance [START_REF] Arlot | Resampling and Model Selection[END_REF]Section 8.7]). For the lower bound, the crucial point is that Z ∼ B n, 1 2 is nonnegative and symmetric, that is, D(Z) = D(n -Z). Using only this property and defining p 0 = P(Z = 0) = P(Z = n) = 2 -n , we have

e + Z = P ( Z = n | Z > 0 ) 2 + E 1 Z 0 < Z < 2 n 2 P(0 < Z < n) P(Z > 0) = p 0 2(1 -p 0 ) + 1 -2p 0 1 -p 0 n 2 E 1 2 1 Z + 1 n -Z 0 < Z < n = p 0 2(1 -p 0 ) + 1 -2p 0 1 -p 0 1 + n 2 E Z -n 2 2 Z(n -Z) 0 < Z < n . ( 71
)
Since Z is binomial with parameters (n, 1/2)

n(1 -2p 0 ) 2 E Z -n 2 2 Z(n -Z) 0 < Z < n ≥ P (Z = 1 or Z = n -1) (n -2) 2 4(n -1)
if n ≥ 3. Putting this into (71), we obtain:

e + B( n, 1 2 ) ≥ 1 1 -2 -n 2 -n-1 + 1 -2 1-n + n(n -2) 2 2 n+1 (n -1)
≥ 1.

Hypergeometric case (proof of Lemma 5)

Let Z ∼ H(n, r, q). It has an expectation E [Z] = (qr)/n.

General lower bound It follows from [START_REF] Yang | Consistency of cross validation for comparing regression procedures[END_REF],

P (Z = 0) ≤ 1 - r n q ≤ exp - qr n
and the fact that if r ≥ n -q + 1, P(Z > 0) = 1.

A general upper bound According to [START_REF] Yang | Information-theoretic determination of minimax rates of convergence[END_REF] and the lower bound for P(Z > 0) above, an upper bound on e + H(n,r,q) can be derived from an upper bound on e 0 H(n,r,q) . Recall the following concentration result by Hush and Scovel [START_REF] Hush | Concentration of the hypergeometric distribution[END_REF]: for every x ≥ 2,

P (E(Z) -Z > x) < exp -2(x -1) 2 1 r + 1 + 1 n -r + 1 ∨ 1 q + 1 + 1 n -q + 1 .
Combined with the above concentration inequality, [START_REF] Marko | Asymptotic expansions for inverse moments of binomial and poisson distributions[END_REF] with c Z = 1, E[Z] = qrn -1 and α = 1 -nβ q for any q n > β ≥ 2 r yields e 0 H(n,r,q) ≤ qr n exp -2(βr -1) 2 r + 1 + 1 1 -nβ q .

Therefore, e + H(n,r,q) ≤ inf q n >β≥ 2 holds for every n ≥ r, q ≥ 1.

End of the proof of (20) With the additional conditions on n, r and q, β can be taken equal to Using [START_REF] Yang | Information-theoretic determination of minimax rates of convergence[END_REF] and the upper bound on P (Z = 0), [START_REF] Birgé | Gaussian model selection[END_REF] follows since r ≥ 2 and κ 3 (ǫ) = 0.9 + 1.4 × ǫ -2 ≥ 1.02 × K(ǫ) + 0.03.

"Rho" case Assume now that q = ⌊ n 2 ⌋ so that n q = 2 + 1 ⌊ n 2 ⌋ ≤ 3 and tends to 2 when n tends to infinity.

For r ≥ 6, β = 2 r in (72) yields e + H(n,6,q) ≤ 9.68 e + H(n,7,q) ≤ 7.61 e + H(n,8,q) ≤ 7.46 e + H(n,9,q) ≤ 7.32

For r ≥ 10, β = 1 4 + 1 r in (72) yields sup r≥10 e + H(n,r,q) ≤ 7.49 sup r≥26 e + H(n,r,q) ≤ 3.

Small values of r must be treated appart. For r = 1, it is easy to compute e + H(n,1,q) = qn -1 ≤ 1. When n = r, we have e + H(n,n,q) = 1. Otherwise, using the fact that for every n ≥ r + 1, n! (n-r)! ≥ (r+1)! (r+1) r n r , e 0 H(n,r,q) ≤ r R (r + 1) r (r + 1)!R r r k=1 r k (R -1) r-k k with R = n q ∈ [1; +∞). For r = 2, this upper bound is lower than 1.6. If n q ≤ 3 (which holds in the "Rho" case), e + H(n,3,q) ≤ 4.67 e + H(n,4,q) ≤ 8.15 e + H(n,5,q) ≤ 14.29.

"Loo" case Assume now q = n-1. On the one hand, if r = 1, the conditioning makes Z deterministic and equal to 1 so that where the last equality holds if x > 0 and a(0) = 1/2. Then, g(u) = H(u)/h(u) satisfies the following ordinary differential equation: g(0) = 0 ∀u ≥ 0, g ′ (u) = 1 -a(u)g(u).

Since ∀u ≥ 0, 1 2 ≤ a(u) ≤ 1 and lim u→+∞ a(u) = 1,

g satisfies a differential inequation 1 - g 2 ≤ g ′ ≤ 1 -g g(0) = 0.
Then, for every x ≥ x 0 ≥ 0, 2 1 -e 2(x0-x) 1 -g(x 0 ) 2 ≥ g(x) ≥ 1 + (g(x 0 ) -1)e x0-x .

(73)

Contents 1

 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 The Resampling Penalization procedure . . . . . . . . . . . . . . . . . 2.1 Framework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 The resampling heuristics . . . . . . . . . . . . . . . . . . . . . . 2.3 Resampling Penalization . . . . . . . . . . . . . . . . . . . . . . . 3 Main results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1 Oracle inequality . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 An adaptive estimator . . . . . . . . . . . . . . . . . . . . . . . .

  (penW) n, p λ , δ n,p and δ (penW) n,p have been computed numerically as a function of np for several resampling schemes, with n = 200. The results are given on Figures 1-6 (with straight lines for δ n,p and dots for δ (penW) n,p

Fig 1 .Fig 2 .

 12 Fig 1. δn,p > 0 > δ (penEfr(n)) n,p .

Fig 3 .

 3 Fig 3. δn,p > δ (penRho(n/2)) n,p for np ≥ 6.

  δ(n,pl) or E[δ W (n,phl) | phl>0] H.-o. a. (floor(n/4)) δ(n,pl) E[δ W (n,phl) | phl>0]

Fig 4 .

 4 Fig 4. δn,p > δ (penRho(n/4)) n,p for np ≥ 9.

  δ(n,pl) or E[δ W (n,phl) | phl>0] L.o.o. δ(n,pl) E[δ W (n,phl) | phl>0]

Fig 5 .

 5 Fig 5. δn,p ≈ δ (penLoo) n,p .

Fig 6 .

 6 Fig 6. δn,p > δ (penRad(1/2)) n,p for np ≥ 6.

  .

Fig 7 .Fig 8 .Fig 9 .Fig 10 .Fig 11 .Fig 12 .

 789101112 Fig 7. s(x) = sin(πx).

Fig 13 .

 13 Fig 13. The non-asymptotic need for overpenalization: the prediction performance Cor (defined in Section 5.1) of the model selection procedure (2) with pen(m) = Cov E [ pen id (m) ] is represented as a function of Cov . Data and models are the ones of experiment S2: n = 200, σ(x) = x, s(x) = sin(πx). See Section 5 for details.

2 .

 2 m has an "intermediate" dimension The penalized empirical criterion crit(m) = P n γ ( s m ) + pen(m) has the same minimizers as crit ′′ (m) = ℓ ( s, s m ) + pen(m)pen ′ id (m) = ℓ ( s, s m ) + pen(m) -p 2 (m) + δ(m) over M n . According to (P2), there exists m 0 ∈ M n such that √ n ≤ D m0 ≤ c rich √ n. If n ≥ L (Bg) , m 0 ∈ M n so that (using (Ap) and the same inequalities as in the first part of the proof) crit

2 mA{

 2 ,W (n, p λ ) + R 2,W (n, p λ ) n(n p λ -1) b λ = -( R 1,W (n, p λ ) + R 2,W (n, p λ ) ) n 2 p λ (n p λ -1) , implies that for every q ≥ 2 pen(m) -E Λm [pen(m)] (Λm) q ≤ L a ℓ ,ξ ℓ D -1/R 1,W (n, p) + R 2,W (n, p) } q ξ ℓ +1 E [ p 2 (m) ] .

ℓ

  ( s, s m ) + L agǫ,ξgǫ,c g ∆,m q ξgǫ+1/2 σ

- 1 ..

 1 On the other hand, if r ≥ 2, Z > 0 holds a.s. since it only take two values:P ( Z = r -1 ) = r n and P ( Z = r ) = n -The lower bound is straightforward since n ≥ r."Lpo" case As noticed in Lemma 17,∀r ≥ p + 1, e + H(n,r,n-p) ≥ 1.Moreover, when r ≥ p + 1 the support of H(n, r, n -p) is {r -p, . . . , r} and e + H(n,r,n-p) = (n -More precisely, the k-th term of the sum is equal to(n -,r,n-p) ≤ rn p (r -p)n • • • (n -p + 1).The result follows.Remark 11 (Asymptotics). If for some α > 0, q k r k ≥ r k → +∞, then e + H(n k ,r k ,q k ) → 1 when k → ∞. The upper bound is obtained by takingβ = 1 + (r k + 1) ln q k r k n k r k in (72), which is possible for k sufficiently large. The lower bound is straightforward.8.11.3. Poisson case (proof of Lemma 6)Let Z ∼ P(µ) and define g : [0; ∞) → R by g(0) = 0 and for every µ > 0g(µ) := e + P(µ) = µE Z -1 Z > 0 =The function g is continuous at 0 and has a first derivative g ′ (0) = 1. For everyx ≥ e x -1 -x x(e x -1) .

Table 1 C

 1 W for several resampling schemes (seeSection 3.4.1)

  Select m ∈ arg min m∈ Mn { P n γ ( s m ) + pen(m) }. 5. Define s := s m .

	4. Theorem 2. Let X = [0, 1] k . Assume that the data (X i , Y i ) 1≤i≤n satisfy the following:
	1/k .
	0. Replace M n by
	M n = m ∈ M n s.t. min λ∈Λm	{n p λ } ≥ 3 .
	1. Choose a resampling scheme D(W ) among Efr, Rad, Poi, Rho and Loo. 2. Take the constant C = C W as defined in Table 1.
	3. For each m ∈ M n , compute the resampling penalty pen(m) defined by (7).

Table 2 R

 2 2,W (n, p λ ) and C W for several resampling schemes. The formulas for R 2,W come fromLemma 17

Table 3

 3 Accuracy indices Cor for each procedure in four experiments, ± a rough estimate of uncertainty of the value reported (that is the empirical standard deviation divided by

	√	N ;

  [39, Appendix II]. Moreover, a non-asymptotic estimation of the accuracy of Monte-Carlo approximation can be obtained via McDiarmid's inequality (see Arlot, Blanchard and Roquain [10, Proposition 2.7] for a precise result using the same idea in another framework). This would provide a practical way of quantifying what is lost by making a Monte-Carlo approximation, and choose B consequently (at least for Rad, Rho and Loo weights).

Note that "complexity" here and in the following refers to the implicit modelization of a model or an algorithm, such as the number of estimated parameters. "Complexity" does not refer at all to the computational complexity of algorithms, which will always be called "computational complexity" in the following.

Shao's goal in[START_REF] Shao | Bootstrap model selection[END_REF] was not efficiency but model consistency.

W is said to be exchangeable when its distribution is invariant by any permutation of its coordinates.

If X has a smooth boundary, Procedure 2 can be modified so that the proof of Theorem 2 remains valid.

When X has a general shape, assume that both Leb(X ) and diam(X ) for • ∞ are finite. Then, a partition ( I λ ) λ∈Λm of X is regular with T k bins when Card(Λm) = T k and there exist positive constants c 1 , c 2 , c 3 , c 4 such that for every λ ∈ Λm,c 1 T -k ≤ Leb(I λ ) ≤ c 2 T -k and c 3 T -1 ≤ diam(I λ ) ≤ c 4 T -1 .

The definition of C W actually used in this paper is slightly different for Efron(M ) and Poisson(µ) weights (see Table2). We arbitrarily choosed the simplest possible expression making C W asymptotically equivalent to 1/E[( W 1 -1 ) 2 ]. The results of the paper also hold when C W = 1/E[( W 1 -1 ) 2 ].

The code used for computing resampling penalties is available on the author's webpage at http://www.di.ens.fr/ ∼ arlot/index.htm.

The shape of a penalty is defined as the way pen(m) depends on m up to a linear transformation.

The variability of the accuracy is more an indicator of the stability of the performance of RP than of the variance of the resampling penalty. However, it remains an interesting measure, since a procedure performing always equally well can be preferred to a procedure with better mean efficiency but poor performances on a small probability event.

However, it is quite unclear how to change C W in order to optimize each penalty in the general case. This is why C W has been chosen as "simple" as possible in Table2.

However, in experiment HSd1, Mallows' Cp still behaves quite well compared to RP. We do not know whether the non-smoothness of s can actually make Mallows' Cp fail.

Taking into account all the data for computing the resampling penalty with Efr(Mn) weights is computationally costly when n/Mn is large.

Otherwise, we can consider algorithms whose input is any weighted sample.

Acknowledgments

The author would like to thank gratefully Pascal Massart for several fruitful discussions. The author also acknowledges several suggestions from the anonymous referees that greatly improved the paper.

provided that n ≥ L (Bg) . In addition, let m 0 ∈ arg min m ′ ∈ Mn { ℓ ( s, s m ′ ) }.

Since m 0 ∈ M n , on Ω n,γ0 , crit ′′ (m 0 ) = ℓ ( s, s m0 ) + pen(m 0 )pen ′ id (m 0 ) ≤ ( 2η

and this upper bound is smaller than the lower bound in [START_REF] Lew | Bounds on negative moments[END_REF]. Hence, on Ω n,γ0 , if D m < ( ln(n) ) γ1 (47) cannot be satisfied with m = m.

Moreover, by [START_REF] Fromont | Model selection by bootstrap penalization for classification[END_REF], for every m ∈ M n such that D m ≤ cn ( ln(n) )

on Ω n,γ0 . Therefore,

γ1 , (31) holds on Ω n,γ0 which implies [START_REF] Li | Asymptotic optimality for C p , C L , cross-validation and generalized cross-validation: discrete index set[END_REF]. Hence, [START_REF] Li | Asymptotic optimality for C p , C L , cross-validation and generalized cross-validation: discrete index set[END_REF] holds on Ω n,γ0 . Finally, with the same arguments as in Section 8.7.1, the infimum on the right-hand side of ( 49) can be extended to the set of m ∈ M n such that D m ≥ ( ln(n) ) γ1 , with the convention ℓ ( s, s m ) = +∞ if A n (m) = 0. Enlarging the constant K 1 to remove the condition n ≥ L (Bg) , ( 32) is proved to hold with γ 2 = γ 1 + ξ ℓ + 3. The proof is quite similar in the unbounded case.

Expectations

Proof of Proposition 1. On the one hand, [START_REF] Arlot | Data-driven calibration of penalties for least-squares regression[END_REF] and [START_REF] Barbe | The weighted bootstrap[END_REF] are consequences of ( 29) and [START_REF] Efron | Estimating the error rate of a prediction rule: improvement on cross-validation[END_REF]; note that (15) holds whatever the convention taken for p 1 and p 2 in Section 8.1.

On the other hand, (12) follows from Lemma 16 below which is slighlty more geenral since W is allowed to depend on ( 1 Xi∈I λ ) (i,λ) .

Lemma 16. Let S m be the model of histograms adapted to some partition

Let pen(m) be defined by [START_REF] Arlot | Suboptimality of penalties proportional to the dimension for model selection in heteroscedastic regression[END_REF] and assume min λ∈Λm { n p λ } ≥ 1. Then,

and R V (n, 1, W λ , D(W )) = 0. Then, ( 53) and ( 54) imply

Finally, (50) follows from the combination of ( 51) and ( 52) with (55).

Resampling constants

Some results relative to the exchangeable weights introduced in Section 2.2 are proved in this subsection. First, Lemma 17 below provides explicit formulas for R 1,W (n, p λ ) and R 2,W (n, p λ ) which appear in the explicit formula [START_REF] Lugosi | Complexity regularization via localized random penalties[END_REF] for the resampling penalty.

Lemma 17. Let n ∈ N and p λ ∈ (0, 1] such that n p λ ∈ {1, . . . , n}. Then, for every M ∈ N\{0}, p ∈ (0; 1], µ > 0 and q ∈ { 1, . . . , n },

where B, P and H denote respectively the Binomial, Poisson and Hypergeometric distributions and Lemma 17. Since W is independent of the data, the observations with X i ∈ I λ can be assumed to be the n p λ first ones: (X 1 , Y 1 ), . . . , (X n p λ , Y n p λ ). The random vector (W i ) 1≤i≤n p λ is then exchangeable (since W is exchangeable).

Hence, by definition of

Proof of Proposition 2. From ( 50), ( 16) holds with

Combining Lemma 17 with Lemma 4 (for Efr and Rad), Lemma 5 (for Rho and Loo) and Lemma 6 (for Poi), the following non-asymptotic bounds are obtained:

1. Efron (M n ): let κ 1 = 5.1 and κ 2 = 3.2, then

2. Rademacher (p):

( n p λ )

4. Random hold-out (q n ): on the one hand,

where the lower bounds assume that 0 < B -≤ q n n -1 ≤ B + < ∞. On the other hand, under the same condition

n p λ provided that n p λ ≥ L B-,B+ . When q n = ⌊n/2⌋, this upper bound is combined with (21). 5. Leave-one-out:

Proof of Lemma 15. Lemma 15 is a byproduct of the proof of Proposition 2 (combined with Lemma 14).

Lower bound The general lower bound [START_REF] Yang | Consistency of cross validation for comparing regression procedures[END_REF] gives

which can be improved. Indeed, if g(x 0 ) ≥ 1, (73) shows that g(x) ≥ 1 for every x ≥ x 0 . Since g = H/h and for every u ≥ 0,

Then, g(1.61) ≥ 1, so that g(x) ≥ 1 for every x ≥ 1.61.

Upper bound Using (73) with x 0 = 0 gives ∀x ≥ 0, g(x) ≤ 2 -2e -2x ≤ 2.

Moreover, for every ǫ ∈ (0; 1), 1 -ǫ ≤ a(x) ≤ 1 as soon as x ≥ ǫ -1 . Then, on [ǫ -1 ; ∞), g satisfies the differential inequation

Integrating this between ǫ -1 and 2ǫ -1 ,

For every x > 2, ǫ = 2x -1 ∈ (0; 1) so that g(x) ≤ 1 + 2 + (x -4) exp -x 2 2(x-2)

x -2 ≤ 1 + 2(1 + e -3 ) x -2 .

The result follows.