Sylvain Arlot
email: sylvain.arlot@ens.fr

Alain Celisse
email: alain.celisse@math.univ-lille1.fr

A survey of cross-validation procedures for model selection

Used to estimate the risk of an estimator or to perform model selection, cross-validation is a widespread strategy because of its simplicity and its apparent universality. Many results exist on the model selection performances of cross-validation procedures. This survey intends to relate these results to the most recent advances of model selection theory, with a particular emphasis on distinguishing empirical statements from rigorous theoretical results. As a conclusion, guidelines are provided for choosing the best cross-validation procedure according to the particular features of the problem in hand.

Introduction

Many statistical algorithms, such as likelihood maximization, least squares and empirical contrast minimization, rely on the preliminary choice of a model, that is of a set of parameters from which an estimate will be returned. When several candidate models (thus algorithms) are available, choosing one of them is called the model selection problem.

Cross-validation (CV) is a popular strategy for model selection, and more generally algorithm selection. The main idea behind CV is to split the data (once or several times) for estimating the risk of each algorithm: Part of the data (the training sample) is used for training each algorithm, and the remaining part (the validation sample) is used for estimating the risk of the algorithm. Then, CV selects the algorithm with the smallest estimated risk.

Compared to the resubstitution error, CV avoids overfitting because the training sample is independent from the validation sample (at least when data are i.i.d.). The popularity of CV mostly comes from the generality of the data splitting heuristics, which only assumes that data are i.i.d.. Nevertheless, theoretical and empirical studies of CV procedures do not entirely confirm this "universality". Some CV procedures have been proved to fail for some model selection problems, depending on the goal of model selection: estimation or identification (see Section 2). Furthermore, many theoretical questions about CV remain widely open.

The aim of the present survey is to provide a clear picture of what is known about CV, from both theoretical and empirical points of view. More precisely, the aim is to answer the following questions: What is CV doing? When does CV work for model selection, keeping in mind that model selection can target different goals? Which CV procedure should be used for each model selection problem?

The paper is organized as follows. First, the rest of Section 1 presents the statistical framework. Although non exhaustive, the present setting has been chosen general enough for sketching the complexity of CV for model selection. The model selection problem is introduced in Section 2. A brief overview of some model selection procedures that are important to keep in mind for understanding CV is given in Section 3. The most classical CV procedures are defined in Section 4. Since they are the keystone of the behaviour of CV for model selection, the main properties of CV estimators of the risk for a fixed model are detailed in Section 5. Then, the general performances of CV for model selection are described, when the goal is either estimation (Section 6) or identification (Section 7). Specific properties of CV in some particular frameworks are discussed in Section 8. Finally, Section 9 focuses on the algorithmic complexity of CV procedures, and Section 10 concludes the survey by tackling several practical questions about CV.

Statistical framework

Assume that some data ξ 1 , . . . , ξ n ∈ Ξ with common distribution P are observed. Throughout the paper-except in Section 8.3-the ξ i are assumed to be independent. The purpose of statistical inference is to estimate from the data ( ξ i ) 1≤i≤n some target feature s of the unknown distribution P , such as the mean or the variance of P . Let S denote the set of possible values for s.

The quality of t ∈ S, as an approximation of s, is measured by its loss L ( t ), where L : S → R is called the loss function, and is assumed to be minimal for t = s. Many loss functions can be chosen for a given statistical problem.

Several classical loss functions are defined by

L ( t ) = L P ( t ) := E ξ∼P [ γ ( t; ξ ) ] , (1)
where γ : S × Ξ → [0, ∞) is called a contrast function. Basically, for t ∈ S and ξ ∈ Ξ, γ(t; ξ) measures how well t is in accordance with observation of ξ, so that the loss of t, defined by (1), measures the average accordance between t and new observations ξ with distribution P . Therefore, several frameworks such as transductive learning do not fit definition (1). Nevertheless, as detailed in Section 1.2, definition (1) includes most classical statistical frameworks. Another useful quantity is the excess loss ℓ ( s, t ) := L P ( t ) -L P ( s ) ≥ 0 , which is related to the risk of an estimator s of the target s by R( s ) = E ξ1,...,ξn∼P [ ℓ ( s, s ) ] .

Examples

The purpose of this subsection is to show that the framework of Section 1.1 includes several important statistical frameworks. This list of examples does not pretend to be exhaustive.

Density estimation aims at estimating the density s of P with respect to some given measure µ on Ξ. Then, S is the set of densities on Ξ with respect to µ. For instance, taking γ(t; x) =ln(t(x)) in (1), the loss is minimal when t = s and the excess loss ℓ ( s, t ) = L P ( t ) -L P ( s ) = E ξ∼P ln s(ξ) t(ξ) = s ln s t dµ is the Kullback-Leibler divergence between distributions tµ and sµ.

Prediction aims at predicting a quantity of interest Y ∈ Y given an explanatory variable X ∈ X and a sample of observations (X 1 , Y 1 ), . . . , (X n , Y n ). In other words, Ξ = X × Y, S is the set of measurable mappings X → Y and the contrast γ(t; (x, y)) measures the discrepancy between the observed y and its predicted value t(x). Two classical prediction frameworks are regression and classification, which are detailed below.

Regression corresponds to continuous Y, that is Y ⊂ R (or R k for multivariate regression), the feature space X being typically a subset of R ℓ . Let s denote the regression function, that is s

(x) = E (X,Y )∼P [ Y | X = x ], so that ∀i, Y i = s(X i ) + ǫ i with E [ ǫ i | X i ] = 0 .
A popular contrast in regression is the least-squares contrast γ ( t; (x, y) ) = (t(x) -y) 2 , which is minimal over S for t = s, and the excess loss is ℓ ( s, t ) = E (X,Y )∼P ( s(X) -t(X) )

2

.

Note that the excess loss of t is the square of the L 2 distance between t and s, so that prediction and estimation are equivalent goals.

Classification corresponds to finite Y (at least discrete). In particular, when Y = { 0, 1 }, the prediction problem is called binary (supervised) classification.

With the 0-1 contrast function γ(t; (x, y)) = 1l t(x) =y , the minimizer of the loss is the so-called Bayes classifier s defined by

s(x) = 1l η(x)≥1/2 ,
where η denotes the regression function η

(x) = P (X,Y )∼P ( Y = 1 | X = x ).
Remark that a slightly different framework is often considered in binary classification. Instead of looking only for a classifier, the goal is to estimate also the confidence in the classification made at each point: S is the set of measurable mappings X → R, the classifier x → 1l t(x)≥0 being associated to any t ∈ S. Basically, the larger |t(x)|, the more confident we are in the classification made from t(x). A classical family of losses associated with this problem is defined by (1) with the contrast γ φ ( t; (x, y) ) = φ ( -(2y -1)t(x) ) where φ : R → [0, ∞) is some function. The 0-1 contrast corresponds to φ(u) = 1l u≥0 . The convex loss functions correspond to the case where φ is convex, nondecreasing with lim -∞ φ = 0 and φ(0

) = 1. Classical examples are φ(u) = max { 1 + u, 0 } (hinge), φ(u) = exp(u)
, and φ(u) = log 2 ( 1 + exp(u) ) (logit). The corresponding losses are used as objective functions by several classical learning algorithms such as support vector machines (hinge) and boosting (exponential and logit).

Many references on classification theory, including model selection, can be found in the survey by [START_REF] Boucheron | Theory of classification: a survey of some recent advances[END_REF].

Statistical algorithms

In this survey, a statistical algorithm A is any (measurable) mapping A : n∈N Ξ n → S. The idea is that data D n = ( ξ i ) 1≤i≤n ∈ Ξ n will be used as an input of A, and that the output of A, A(D n ) = s A (D n ) ∈ S, is an estimator of s. The quality of A is then measured by L P s A (D n ) , which should be as small as possible. In the sequel, the algorithm A and the estimator s A (D n ) are often identified when no confusion is possible.

Minimum contrast estimators form a classical family of statistical algorithms, defined as follows. Given some subset S of S that we call a model, a minimum contrast estimator of s is any minimizer of the empirical contrast • Maximum likelihood estimators: take γ(t; x) =ln(t(x)) in the density estimation setting. A classical choice for S is the set of piecewise constant functions on a regular partition of Ξ with K pieces.

t → L Pn ( t ) = 1 n n i=1 γ ( t; ξ i ) , where P n = 1 n n i=1 δ ξi , over S.
• Least-squares estimators: take γ(t; (x, y)) = (t(x) -y) 2 the least-squares contrast in the regression setting. For instance, S can be the set of piecewise constant functions on some fixed partition of X (leading to regressograms), or a vector space spanned by the first vectors of wavelets or Fourier basis, among many others. Note that regularized least-squares algorithms such as the Lasso, ridge regression and spline smoothing also are leastsquares estimators, the model S being some ball of a (data-dependent) radius for the L 1 (resp. L 2 ) norm in some high-dimensional space. Hence, tuning the regularization parameter for the LASSO or SVM, for instance, amounts to perform model selection from a collection of models.

• Empirical risk minimizers, following the terminology of [START_REF] Vapnik | Estimation of dependences based on empirical data[END_REF]: take any contrast function γ in the prediction setting. When γ is the 0-1 contrast, popular choices for S lead to linear classifiers, partitioning rules, and neural networks. Boosting and Support Vector Machines classifiers also are empirical contrast minimizers over some data-dependent model S, with contrast γ = γ φ for some convex functions φ.

Let us finally mention that many other classical statistical algorithms can be considered with CV, for instance local average estimators in the prediction framework such as k-Nearest Neighbours and Nadaraya-Watson kernel estimators. The focus will be mainly kept on minimum contrast estimators to keep the length of the survey reasonable.

Model selection

Usually, several statistical algorithms can be used for solving a given statistical problem. Let ( s λ ) λ∈Λ denote such a family of candidate statistical algorithms. The algorithm selection problem aims at choosing from data one of these algorithms, that is, choosing some λ(D n ) ∈ Λ. Then, the final estimator of s is given by s b λ(Dn) (D n ). The main difficulty is that the same data are used for training the algorithms, that is, for computing ( s λ (D n ) ) λ∈Λ , and for choosing λ(D n ) .

The model selection paradigm

Following Section 1.3, let us focus on the model selection problem, where candidate algorithms are minimum contrast estimators and the goal is to choose a model S. Let ( S m ) m∈Mn be a family of models, that is, S m ⊂ S. Let γ be a fixed contrast function, and for every m ∈ M n , let s m be a minimum contrast estimator over model S m with contrast γ. The goal is to choose m(D n ) ∈ M n from data only.

The choice of a model S m has to be done carefully. Indeed, when S m is a "small" model, s m is a poor statistical algorithm except when s is very close to

S m , since ℓ ( s, s m ) ≥ inf t∈Sm { ℓ ( s, t ) } := ℓ ( s, S m ) .
The lower bound ℓ ( s, S m ) is called the bias of model S m , or approximation error. The bias is a nonincreasing function of S m .

On the contrary, when S m is "huge", its bias ℓ ( s, S m ) is small for most targets s, but s m clearly overfits. Think for instance of S m as the set of all continuous functions on [0, 1] in the regression framework. More generally, if S m is a vector space of dimension D m , in several classical frameworks,

E [ ℓ ( s, s m (D n ) ) ] ≈ ℓ ( s, S m ) + λD m (2)
where λ > 0 does not depend on m. For instance, λ = 1/(2n) in density estimation using the likelihood contrast, and λ = σ 2 /n in regression using the least-squares contrast and assuming var ( Y | X ) = σ 2 does not depend on X.

The meaning of ( 2) is that a good model choice should balance the bias term ℓ ( s, S m ) and the variance term λD m , that is solve the so-called bias-variance trade-off. By extension, the variance term, also called estimation error, can be defined by

E [ ℓ ( s, s m (D n ) ) ] -ℓ ( s, S m ) = E [ L P ( s m ) ] -inf t∈Sm L P ( t ) ,
even when (2) does not hold.

The interested reader can find a much deeper insight into model selection in the Saint-Flour lecture notes by [START_REF] Massart | Concentration inequalities and model selection[END_REF].

Before giving examples of classical model selection procedures, let us mention the two main different goals that model selection can target: estimation and identification.

Model selection for estimation

On the one hand, the goal of model selection is estimation when s b m(Dn) (D n ) is used as an approximation of the target s, and the goal is to minimize its loss. For instance, AIC and Mallows' C p model selection procedures are built for estimation (see Section 3.1).

The quality of a model selection procedure D n → m(D n ), designed for estimation, is measured by the excess loss of s b m(Dn) (D n ). Hence, the best possible model choice for estimation is the so-called oracle model S m ⋆ , defined by

m ⋆ = m ⋆ (D n ) ∈ arg min m∈Mn { ℓ ( s, s m (D n ) ) } . (3) Since m ⋆ (D n ) depends on the unknown distribution P of data, one cannot expect to select m(D n ) = m ⋆ (D n ) almost surely. Nevertheless, we can hope to select m(D n ) such that s b m(Dn)
is almost as close to s as s m ⋆ (Dn) . Note that there is no requirement for s to belong to m∈Mn S m .

Depending on the framework, the optimality of a model selection procedure for estimation is assessed in at least two different ways.

First, in the asymptotic framework, a model selection procedure m is called efficient (or asymptotically optimal) when it leads to m such that

ℓ s, s b m(Dn) (D n ) inf m∈Mn { ℓ ( s, s m (D n ) ) } a.s. ----→ n→∞ 1 .
Sometimes, a weaker result is proved, the convergence holding only in probability.

Second, in the non-asymptotic framework, a model selection procedure satisfies an oracle inequality with constant C n ≥ 1 and remainder term

R n ≥ 0 when ℓ s, s b m(Dn) (D n ) ≤ C n inf m∈Mn { ℓ ( s, s m (D n ) ) } + R n (4)
holds either in expectation or with large probability (that is, a probability larger than 1 -C ′ /n 2 , for some positive constant C ′ ). Note that if (4) holds on a large probability event with C n tending to 1 when n tends to infinity and

R n ≪ ℓ ( s, s m ⋆ (D n ) )
, then the model selection procedure m is efficient.

In the estimation setting, model selection is often used for building adaptive estimators, assuming that s belongs to some function space T α [START_REF] Barron | Risk bounds for model selection via penalization[END_REF].Then, a model selection procedure m is optimal when it leads to an estimator s b m(Dn) (D n ) (approximately) minimax with respect to T α without knowing α, provided the family ( S m ) m∈Mn has been well-chosen.

Model selection for identification

On the other hand, model selection can aim at identifying the "true model" S m0 , defined as the "smallest" model among ( S m ) m∈Mn to which s belongs. In particular, s ∈ m∈Mn S m is assumed in this setting. A typical example of model selection procedure built for identification is BIC (see Section 3.3).

The quality of a model selection procedure designed for identification is measured by its probability of recovering the true model m 0 . Then, a model selection procedure is called (model) consistent when

P ( m(D n ) = m 0 ) ----→ n→∞ 1 .
Note that identification can naturally be extended to the general algorithm selection problem, the "true model" being replaced by the statistical algorithm whose risk converges at the fastest rate (see for instance [START_REF] Yang | Consistency of cross validation for comparing regression procedures[END_REF].

Estimation vs. identification

When a true model exists, model consistency is clearly a stronger property than efficiency defined in Section 2.2. However, in many frameworks, no true model does exist so that efficiency is the only well-defined property.

Could a model selection procedure be model consistent in the former case (like BIC) and efficient in the latter case (like AIC)? The general answer to this question, often called the AIC-BIC dilemma, is negative: [START_REF] Yang | Can the strengths of AIC and BIC be shared? A conflict between model indentification and regression estimation[END_REF] proved in the regression framework that no model selection procedure can be simultaneously model consistent and minimax rate optimal. Nevertheless, the strengths of AIC and BIC can sometimes be shared; see for instance the introduction of a paper by [START_REF] Yang | Can the strengths of AIC and BIC be shared? A conflict between model indentification and regression estimation[END_REF] and a recent paper by [START_REF] Van Erven | Catching up faster by switching sooner: A prequential solution to the aic-bic dilemma[END_REF].

Overview of some model selection procedures

Several approaches can be used for model selection. Let us briefly sketch here some of them, which are particularly helpful for understanding how CV works.

Like CV, all the procedures considered in this section select

m(D n ) ∈ arg min m∈Mn { crit(m; D n ) } , (5)
where ∀m ∈ M n , crit(m; D n ) = crit(m) ∈ R is some data-dependent criterion.

A particular case of ( 5) is penalization, which consists in choosing the model minimizing the sum of empirical contrast and some measure of complexity of the model (called penalty) which can depend on the data, that is,

m(D n ) ∈ arg min m∈Mn { L Pn ( s m ) + pen(m; D n ) } . ( 6
)
This section does not pretend to be exhaustive. Completely different approaches exist for model selection, such as the Minimum Description Length (MDL) [START_REF] Rissanen | Universal Prior for Integers and Estimation by Minimum Description Length[END_REF], and the Bayesian approaches. The interested reader will find more details and references on model selection procedures in the books by [START_REF] Burnham | Model selection and multimodel inference[END_REF] or [START_REF] Massart | Concentration inequalities and model selection[END_REF] for instance.

Let us focus here on five main categories of model selection procedures, the first three ones coming from a classification made by [START_REF] Shao | An asymptotic theory for linear model selection[END_REF] in the linear regression framework.

The unbiased risk estimation principle

When the goal of model selection is estimation, many model selection procedures are of the form (5) where crit(m; D n ) unbiasedly estimates (at least, asymptotically) the loss L P ( s m ). This general idea is often called unbiased risk estimation principle, or Mallows' or Akaike's heuristics.

In order to explain why this strategy can perform well, let us write the starting point of most theoretical analysis of procedures defined by (5): By definition (5), for every m ∈ M n ,

ℓ ( s, s b m ) + crit( m) -L P ( s b m ) ≤ ℓ ( s, s m ) + crit(m) -L P ( s m ) . (7)
If E [ crit(m) -L P ( s m ) ] = 0 for every m ∈ M n , then concentration inequalities are likely to prove that ε

- n , ε + n > 0 exist such that ∀m ∈ M n , ε + n ≥ crit(m) -L P ( s m ) ℓ ( s, s m ) ≥ -ε - n > -1
with high probability, at least when Card(M n ) ≤ Cn α for some C, α ≥ 0. Then, (7) directly implies an oracle inequality like (4) with

C n = (1 + ε + n )/(1 -ε - n ). If ε + n , ε - n → 0 when n → ∞,
this proves the procedure defined by ( 5) is efficient. Examples of model selection procedures following the unbiased risk estimation principle are FPE (Final Prediction Error, [START_REF] Akaike | Statistical predictor identification[END_REF], several crossvalidation procedures including the Leave-one-out (see Section 4), and GCV (Generalized Cross-Validation, Craven and Wahba, 1979, see Section 4.3.3). With the penalization approach (6), the unbiased risk estimation principle is that E [ pen(m) ] should be close to the "ideal penalty" pen id (m) := L P ( s m ) -L Pn ( s m ) .

Several classical penalization procedures follow this principle, for instance:

• With the log-likelihood contrast, AIC (Akaike Information Criterion, Akaike, 1973) and its corrected versions [START_REF] Sugiura | Further analysis of the data by akaike's information criterion and the finite corrections[END_REF][START_REF] Hurvich | Regression and time series model selection in small samples[END_REF].

• With the least-squares contrast, Mallows' C p [START_REF] Mallows | Some comments on C p[END_REF] and several refined versions of C p (see for instance [START_REF] Baraud | Model selection for regression on a random design[END_REF].

• With a general contrast, covariance penalties [START_REF] Efron | The estimation of prediction error: covariance penalties and cross-validation[END_REF].

AIC, Mallows' C p and related procedures have been proved to be optimal for estimation in several frameworks, provided Card(M n ) ≤ Cn α for some constants C, α ≥ 0 (see the paper by Birgé and Massart, 2007, and references therein).

The main drawback of penalties such as AIC or Mallows' C p is their dependence on some assumptions on the distribution of data. For instance, Mallows' C p assumes the variance of Y does not depend on X. Otherwise, it has a suboptimal performance [START_REF] Arlot | Suboptimality of penalties proportional to the dimension for model selection in heteroscedastic regression[END_REF].

Several resampling-based penalties have been proposed to overcome this problem, at the price of a larger computational complexity, and possibly slightly worse performance in simpler frameworks; see a paper by [START_REF] Efron | Estimating the error rate of a prediction rule: improvement on cross-validation[END_REF] for bootstrap, and a paper by Arlot (2008a) and references therein for generalization to exchangeable weights.

Finally, note that all these penalties depend on multiplying factors which are not always known (for instance, the noise-level, for Mallows' C p ). [START_REF] Birgé | Minimal penalties for Gaussian model selection[END_REF] proposed a general data-driven procedure for estimating such multiplying factors, which satisfies an oracle inequality with C n → 1 in regression (see also [START_REF] Arlot | Data-driven calibration of penalties for leastsquares regression[END_REF].

Biased estimation of the risk

Several model selection procedures are of the form (5) where crit(m) does not unbiasedly estimate the loss L P ( s m ): The weight of the variance term compared to the bias in E [ crit(m) ] is slightly larger than in the decomposition (2) of L P ( s m ). From the penalization point of view, such procedures are overpenalizing.

Examples of such procedures are FPE α [START_REF] Bhansali | Some properties of the order of an autoregressive model selected by a generalization of Akaike's FPE criterion[END_REF] and GIC λ (Generalized Information Criterion, [START_REF] Nishii | Asymptotic properties of criteria for selection of variables in multiple regression[END_REF][START_REF] Shao | An asymptotic theory for linear model selection[END_REF] with α, λ > 2, which are closely related. Some cross-validation procedures, such as Leavep-out with p/n ∈ (0, 1) fixed, also belong to this category (see Section 4.3.1). Note that FPE α with α = 2 is FPE, and GIC λ with λ = 2 is close to FPE and Mallows' C p .

When the goal is estimation, there are two main reasons for using "biased" model selection procedures. First, experimental evidence show that overpenalizing often yields better performance when the signal-to-noise ratio is small (see for instance Arlot, 2007, Chapter 11).

Second, when the number of models Card(M n ) grows faster than any power of n, as in the complete variable selection problem with n variables, then the unbiased risk estimation principle fails. From the penalization point of view, [START_REF] Birgé | Minimal penalties for Gaussian model selection[END_REF] proved that when Card(M n ) = e κn for some κ > 0, the minimal amount of penalty required so that an oracle inequality holds with 1) is much larger than pen id (m). In addition to the FPE α and GIC λ with suitably chosen α, λ, several penalization procedures have been proposed for taking into account the size of M n [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é | Gaussian model selection[END_REF][START_REF] Sauvé | Histogram selection in non gaussian regression[END_REF]. In the same papers, these procedures are proved to satisfy oracle inequalities with C n as small as possible, typically of order ln(n) when Card(M n ) = e κn .

C n = O(

Procedures built for identification

Some specific model selection procedures are used for identification. A typical example is BIC (Bayesian Information Criterion, [START_REF] Schwarz | Estimating the dimension of a model[END_REF].

More generally, [START_REF] Shao | An asymptotic theory for linear model selection[END_REF] showed that several procedures identify consistently the correct model in the linear regression framework as soon as they overpenalize within a factor tending to infinity with n, for instance, GIC λn with λ n → +∞, FPE αn with α n → +∞ [START_REF] Shibata | Approximate efficiency of a selection procedure for the number of regression variables[END_REF], and several CV procedures such as Leave-p-out with p = p n ∼ n. BIC is also part of this picture, since it coincides with GIC ln(n) .

In another paper, [START_REF] Shao | Bootstrap model selection[END_REF] showed that m n -out-of-n bootstrap penalization is also model consistent as soon as m n ∼ n. Compared to Efron's bootstrap penalties, the idea is to estimate pen id with the m n -out-of-n bootstrap instead of the usual bootstrap, which results in overpenalization within a factor tending to infinity with n (Arlot, 2008a).

Most MDL-based procedures can also be put into this category of model selection procedures (see [START_REF] Grünwald | The Minimum Description Length Principle[END_REF]. Let us finally mention the Lasso [START_REF] Tibshirani | Regression Shrinkage and Selection via the Lasso[END_REF] and other ℓ 1 penalization procedures, which have recently attracted much attention (see for instance [START_REF] Hesterberg | Least angle and l1 penalized regression: A review[END_REF]. They are a computationally efficient way of identifying the true model in the context of variable selection with many variables.

Structural risk minimization

In the context of statistical learning, [START_REF] Vapnik | Teoriya raspoznavaniya obrazov. Statisticheskie problemy obucheniya. Izdat[END_REF] proposed the structural risk minimization approach (see also [START_REF] Vapnik | Estimation of dependences based on empirical data[END_REF][START_REF] Vapnik | Statistical learning theory. Adaptive and Learning Systems for Signal Processing, Communications, and Control[END_REF]. Roughly, the idea is to penalize the empirical contrast with a penalty (over)estimating

pen id,g (m) := sup t∈Sm { L P ( t ) -L Pn ( t ) } ≥ pen id (m) .
Such penalties have been built using the Vapnik-Chervonenkis dimension, the combinatorial entropy, (global) Rademacher complexities [START_REF] Koltchinskii | Rademacher penalties and structural risk minimization[END_REF]Bartlett et al., 2002), (global) bootstrap penalties [START_REF] Fromont | Model selection by bootstrap penalization for classification[END_REF], Gaussian complexities or the maximal discrepancy [START_REF] Bartlett | Rademacher and Gaussian complexities: risk bounds and structural results[END_REF]. These penalties are often called global because pen id,g (m) is a supremum over S m .

The localization approach (see [START_REF] Boucheron | Theory of classification: a survey of some recent advances[END_REF] has been introduced in order to obtain penalties closer to pen id (such as local Rademacher complexities), hence smaller prediction errors when possible [START_REF] Bartlett | Local Rademacher complexities[END_REF][START_REF] Koltchinskii | Local Rademacher complexities and oracle inequalities in risk minimization[END_REF]. Nevertheless, these penalties are still larger than pen id (m) and can be difficult to compute in practice because of several unknown constants.

A non-asymptotic analysis of several global and local penalties can be found in the book by [START_REF] Massart | Concentration inequalities and model selection[END_REF] for instance; see also [START_REF] Koltchinskii | Local Rademacher complexities and oracle inequalities in risk minimization[END_REF] for recent results on local penalties.

Ad hoc penalization

Let us finally mention that penalties can also be built according to particular features of the problem. For instance, penalties can be proportional to the ℓ p norm of s m (similarly to ℓ p -regularized learning algorithms) when having an estimator with a controlled ℓ p norm seems better. The penalty can also be proportional to the squared norm of s m in some reproducing kernel Hilbert space (similarly to kernel ridge regression or spline smoothing), with a kernel adapted to the specific framework. More generally, any penalty can be used, as soon as pen(m) is larger than the estimation error (to avoid overfitting) and the best model for the final user is not the oracle m ⋆ , but more like

arg min m∈Mn { ℓ ( s, S m ) + κ pen(m) }
for some κ > 0.

Where are cross-validation procedures in this picture?

The family of CV procedures, which will be described and deeply investigated in the next sections, contains procedures in the first three categories. CV procedures are all of the form (5), where crit(m) either estimates (almost) unbiasedly the loss L P ( s m ), or overestimates the variance term (see Section 2.1). In the latter case, CV procedures either belong to the second or the third category, depending on the overestimation level.

This fact has two major implications. First, CV itself does not take into account prior information for selecting a model. To do so, one can either add to the CV estimate of the risk a penalty term (such as s m p ), or use prior information to pre-select a subset of models M(D n ) ⊂ M n before letting CV select a model among ( S m ) m∈ f M(Dn) . Second, in statistical learning, CV and resampling-based procedures are the most widely used model selection procedures. Structural risk minimization is often too pessimistic, and other alternatives rely on unrealistic assumptions. But if CV and resampling-based procedures are the most likely to yield good prediction performances, their theoretical grounds are not that firm, and too few CV users are careful enough when choosing a CV procedure to perform model selection. Among the aims of this survey is to point out both positive and negative results about the model selection performance of CV.

Cross-validation procedures

The purpose of this section is to describe the rationale behind CV and to define the different CV procedures. Since all CV procedures are of the form (5), defining a CV procedure amounts to define the corresponding CV estimator of the risk of an algorithm A, which will be crit(•) in (5).

Cross-validation philosophy

As noticed in the early 30s by [START_REF] Larson | The shrinkage of the coefficient of multiple correlation[END_REF], training an algorithm and evaluating its statistical performance on the same data yields an overoptimistic result. CV was raised to fix this issue [START_REF] Mosteller | Data analysis, including statistics[END_REF][START_REF] Stone | Cross-validatory choice and assessment of statistical predictions[END_REF][START_REF] Geisser | The predictive sample reuse method with applications[END_REF], starting from the remark that testing the output of the algorithm on new data would yield a good estimate of its performance [START_REF] Breiman | Arcing classifiers[END_REF].

In most real applications, only a limited amount of data is available, which led to the idea of splitting the data: Part of the data (the training sample) is used for training the algorithm, and the remaining data (the validation sample) is used for evaluating its performance. The validation sample can play the role of new data as soon as data are i.i.d..

Data splitting yields the validation estimate of the risk, and averaging over several splits yields a cross-validation estimate of the risk. As will be shown in Sections 4.2 and 4.3, various splitting strategies lead to various CV estimates of the risk.

The major interest of CV lies in the universality of the data splitting heuristics, which only assumes that data are identically distributed and the training and validation samples are independent, two assumptions which can even be relaxed (see Section 8.3). Therefore, CV can be applied to (almost) any algorithm in (almost) any framework, for instance regression [START_REF] Stone | Cross-validatory choice and assessment of statistical predictions[END_REF][START_REF] Geisser | The predictive sample reuse method with applications[END_REF], density estimation [START_REF] Rudemo | Empirical Choice of Histograms and Kernel Density Estimators[END_REF][START_REF] Stone | An asymptotically optimal window selection rule for kernel density estimates[END_REF] and classification [START_REF] Devroye | Distribution-Free performance Bounds for Potential Function Rules[END_REF]Bartlett et al., 2002), among many others. On the contrary, most other model selection procedures (see Section 3) are specific to a framework: For instance, C p [START_REF] Mallows | Some comments on C p[END_REF] is specific to least-squares regression.

From validation to cross-validation

In this section, the hold-out (or validation) estimator of the risk is defined, leading to a general definition of CV.

Hold-out

The hold-out [START_REF] Devroye | Distribution-Free performance Bounds for Potential Function Rules[END_REF] or (simple) validation relies on a single split of data. Formally, let I (t) be a non-empty proper subset of { 1, . . . , n }, that is, such that both I (t) and its complement I (v) = I (t) c = { 1, . . . , n } \I (t) are non-empty. The hold-out estimator of the risk of A(D n ) with training set I (t) is defined by

L H-O A; D n ; I (t) := 1 n v i∈D (v) n γ A(D (t) n ); (X i , Y i ) , (8)
where

D (t) n := (ξ i ) i∈I (t)
is the training sample, of size n t = Card(I (t) ), and v) is called the validation set. The question of choosing n t , and I (t) given its cardinality n t , is discussed in the rest of this survey.

D (v) n := (ξ i ) i∈I (v) is the validation sample, of size n v = n -n t ; I (

General definition of cross-validation

A general description of the CV strategy has been given by [START_REF] Geisser | The predictive sample reuse method with applications[END_REF]: In brief, CV consists in averaging several hold-out estimators of the risk corresponding to different splits of the data. Formally, let B ≥ 1 be an integer and

I (t) 1 , . . . , I (t)
B be a sequence of non-empty proper subsets of { 1, . . . , n }. The CV estimator of the risk of A(D n ) with training sets

I (t) j 1≤j≤B
is defined by

L CV A; D n ; I (t) j 1≤j≤B := 1 B B j=1 L H-O A; D n ; I (t) j . ( 9
)
All existing CV estimators of the risk are of the form (9), each one being uniquely determined by the way the sequence

I (t) j 1≤j≤B
is chosen, that is, the choice of the splitting scheme.

Note that when CV is used in model selection for identification, an alternative definition of CV was proposed by [START_REF] Yang | Comparing learning methods for classification[END_REF][START_REF] Yang | Consistency of cross validation for comparing regression procedures[END_REF] and called CV with voting (CV-v). When two algorithms A 1 and

A 2 are compared, A 1 is selected by CV-v if and only if L H-O (A 1 ; D n ; I (t) j ) < L H-O (A 2 ; D n ; I (t)
j ) for a majority of the splits j = 1, . . . , B. By contrast, CV procedures of the form (9) can be called "CV with averaging" (CV-a), since the estimates of the risk of the algorithms are averaged before their comparison.

Classical examples

Most classical CV estimators split the data with a fixed size n t of the training set, that is, Card(I (t) j ) ≈ n t for every j. The question of choosing n t is discussed extensively in the rest of this survey. In this subsection, several CV estimators are defined. Two main categories of splitting schemes can be distinguished, given n t : exhaustive data splitting, that is considering all training sets I (t) of size n t , and partial data splitting.

Exhaustive data splitting

Leave-one-out (LOO, [START_REF] Stone | Cross-validatory choice and assessment of statistical predictions[END_REF][START_REF] Allen | The relationship between variable selection and data augmentation and a method for prediction[END_REF][START_REF] Geisser | The predictive sample reuse method with applications[END_REF] is the most classical exhaustive CV procedure, corresponding to the choice n t = n-1 : Each data point is successively "left out" from the sample and used for validation. Formally, LOO is defined by ( 9) with B = n and

I (t) j = { j } c for j = 1, . . . , n : L LOO ( A; D n ) = 1 n n j=1 γ A D (-j) n ; ξ j ( 10
)
where

D (-j) n = ( ξ i ) i =j .
The name LOO can be traced back to papers by [START_REF] Picard | Cross-validation of regression models[END_REF] and by [START_REF] Breiman | Submodel selection and evaluation in regression. the x-random case[END_REF], but LOO has several other names in the literature, such as delete-one CV (see [START_REF] Li | Asymptotic optimality for C p , C L , cross-validation and generalized cross-validation: discrete index set[END_REF], ordinary CV [START_REF] Stone | Cross-validatory choice and assessment of statistical predictions[END_REF][START_REF] Burman | A comparative study of ordinary cross-validation, vfold cross-validation and the repeated learning-testing methods[END_REF], or even only CV [START_REF] Efron | Estimating the error rate of a prediction rule: improvement on cross-validation[END_REF][START_REF] Li | Asymptotic optimality for C p , C L , cross-validation and generalized cross-validation: discrete index set[END_REF].

Leave-p-out (LPO, [START_REF] Shao | Linear model selection by cross-validation[END_REF] with p ∈ { 1, . . . , n } is the exhaustive CV with n t = n -p : every possible set of p data points are successively "left out" from the sample and used for validation. Therefore, LPO is defined by ( 9) with B = n p and (I (t) j ) 1≤j≤B are all the subsets of { 1, . . . , n } of size p. LPO is also called delete-p CV or delete-p multifold CV [START_REF] Zhang | Model selection via multifold cross validation[END_REF]. Note that LPO with p = 1 is LOO.

Partial data splitting

Considering n p training sets can be computationally intractable, even for small p, so that partial data splitting methods have been proposed.

V-fold CV (VFCV) with V ∈ { 1, . . . , n } was introduced by [START_REF] Geisser | The predictive sample reuse method with applications[END_REF] as an alternative to the computationally expensive LOO (see also Breiman et al., 1984, for instance). VFCV relies on a preliminary partitioning of the data into V subsamples of approximately equal cardinality n/V ; each of these subsamples successively plays the role of validation sample. Formally, let A 1 , . . . , A V be some partition of { 1, . . . , n } with Card ( A j ) ≈ n/V . Then, the VFCV estimator of the risk of A is defined by ( 9) with B = V and

I (t) j = A c j for j = 1, . . . , B, that is, L VF s; D n ; ( A j ) 1≤j≤V = 1 V V j=1   1 Card(A j ) i∈Aj γ s D (-Aj ) n ; ξ i   (11)
where

D (-Aj ) n = ( ξ i ) i∈A c j
. By construction, the algorithmic complexity of VFCV is only V times that of training A with n -n/V data points, which is much less than LOO or LPO if V ≪ n. Note that VFCV with V = n is LOO.

Balanced Incomplete CV (BICV, [START_REF] Shao | Linear model selection by cross-validation[END_REF] can be seen as an alternative to VFCV well-suited for small training sample sizes n t . Indeed, BICV is defined by ( 9) with training sets ( A c ) A∈T , where T is a balanced incomplete block designs (BIBD, [START_REF] John | Statistical design and analysis of experiments[END_REF], that is, a collection of B > 0 subsets of { 1, . . . , n } of size n v = n -n t such that:

1. Card { A ∈ T s.t. k ∈ A } does not depend on k ∈ { 1, . . . , n }. 2. Card { A ∈ T s.t. k, ℓ ∈ A } does not depend on k = ℓ ∈ { 1, . . . , n }.
The idea of BICV is to give to each data point (and each pair of data points) the same role in the training and validation tasks. Note that VFCV relies on a similar idea, since the set of training sample indices used by VFCV satisfy the first property and almost the second one: Pairs (k, ℓ) belonging to the same A j appear in one validation set more than other pairs. Repeated learning-testing (RLT) was introduced by [START_REF] Breiman | Classification and regression trees[END_REF] and further studied by [START_REF] Burman | A comparative study of ordinary cross-validation, vfold cross-validation and the repeated learning-testing methods[END_REF] and by [START_REF] Zhang | Model selection via multifold cross validation[END_REF] for instance. The RLT estimator of the risk of A is defined by (9) with any B > 0 and (I (t) j ) 1≤j≤B are B different subsets of { 1, . . . , n }, chosen randomly and independently from the data. RLT can be seen as an approximation to LPO with p = n -n t , with which it coincides when B = n p .

Monte-Carlo CV (MCCV, [START_REF] Picard | Cross-validation of regression models[END_REF] is very close to RLT: B independent subsets of { 1, . . . , n } are randomly drawn, with uniform distribution among subsets of size n t . The only difference with RLT is that MCCV allows the same split to be chosen several times.

Other cross-validation-like risk estimators

Several procedures have been introduced which are close to, or based on CV.

Most of them aim at fixing an observed drawback of CV.

Bias-corrected versions of VFCV and RLT risk estimators have been proposed by [START_REF] Burman | A comparative study of ordinary cross-validation, vfold cross-validation and the repeated learning-testing methods[END_REF][START_REF] Burman | Estimation of optimal transformations using v-fold cross validation and repeated learning-testing methods[END_REF], and a closely related penalization procedure called V -fold penalization has been defined by [START_REF] Arlot | V -fold cross-validation improved: V -fold penalization[END_REF], see Section 5.1.2 for details.

Generalized CV (GCV, [START_REF] Craven | Smoothing noisy data with spline functions. Estimating the correct degree of smoothing by the method of generalized cross-validation[END_REF] was introduced as a rotation-invariant version of LOO in least-squares regression, for estimating the risk of a linear estimator s = M Y where Y = (Y i ) 1≤i≤n ∈ R n and M is an n × n matrix independent from Y:

crit GCV (M, Y) := n -1 Y -M Y 2 ( 1 -n -1 tr(M ) ) 2 where ∀t ∈ R n , t 2 = n i=1 t 2 i .
GCV is actually closer to C L [START_REF] Mallows | Some comments on C p[END_REF] than to CV, since GCV can be seen as an approximation to C L with a particular estimator of the variance [START_REF] Efron | How biased is the apparent error rate of a prediction rule?[END_REF]. The efficiency of GCV has been proved in various frameworks, in particular by [START_REF] Li | From stein's unbiased risk estimates to the method of generalized cross validation[END_REF][START_REF] Li | Asymptotic optimality for C p , C L , cross-validation and generalized cross-validation: discrete index set[END_REF] and by [START_REF] Cao | On oracle inequalities related to smoothing splines[END_REF].

Analytic Approximation When CV is used for selecting among linear models, [START_REF] Shao | Linear model selection by cross-validation[END_REF] proposed an analytic approximation to LPO with p ∼ n, which is called APCV.

LOO bootstrap and .632 bootstrap

The bootstrap is often used for stabilizing an estimator or an algorithm, replacing A(D n ) by the average of A(D ⋆ n ) over several bootstrap resamples D ⋆ n . This idea was applied by [START_REF] Efron | Estimating the error rate of a prediction rule: improvement on cross-validation[END_REF] to the LOO estimator of the risk, leading to the LOO bootstrap. Noting that the LOO bootstrap was biased, [START_REF] Efron | Estimating the error rate of a prediction rule: improvement on cross-validation[END_REF] gave a heuristic argument leading to the .632 bootstrap estimator of the risk, later modified into the .632+ bootstrap by [START_REF] Efron | Improvements on cross-validation: the .632+ bootstrap method[END_REF]. The main drawback of these procedures is the weakness of their theoretical justifications. Only empirical studies have supported the good behaviour of .632+ bootstrap [START_REF] Efron | Improvements on cross-validation: the .632+ bootstrap method[END_REF][START_REF] Molinaro | Prediction error estimation: a comparison of resampling methods[END_REF].

Historical remarks

Simple validation or hold-out was the first CV-like procedure. It was introduced in the psychology area [START_REF] Larson | The shrinkage of the coefficient of multiple correlation[END_REF] from the need for a reliable alternative to the resubstitution error, as illustrated by [START_REF] Anderson | Selectioon of predictor variables in linear multiple regression[END_REF]. The holdout was used by [START_REF] Herzberg | The parameters of cross-validation[END_REF] for assessing the quality of predictors. The problem of choosing the training set was first considered by [START_REF] Stone | Cross-validatory choice and assessment of statistical predictions[END_REF], where "controllable" and "uncontrollable" data splits were distinguished; an instance of uncontrollable division can be found in the book by [START_REF] Simon | Prediction methods in criminology[END_REF].

A primitive LOO procedure was used by [START_REF] Hills | Allocation Rules and their Error Rates[END_REF] and by [START_REF] Lachenbruch | Estimation of Error Rates in Discriminant Analysis[END_REF] for evaluating the error rate of a prediction rule, and a primitive formulation of LOO can be found in a paper by [START_REF] Mosteller | Data analysis, including statistics[END_REF]. Nevertheless, LOO was actually introduced independently by [START_REF] Stone | Cross-validatory choice and assessment of statistical predictions[END_REF], by [START_REF] Allen | The relationship between variable selection and data augmentation and a method for prediction[END_REF] and by [START_REF] Geisser | The predictive sample reuse method with applications[END_REF]. The relationship between LOO and the jackknife [START_REF] Quenouille | Approximate tests of correlation in time-series[END_REF], which both rely on the idea of removing one observation from the sample, has been discussed by [START_REF] Stone | Cross-validatory choice and assessment of statistical predictions[END_REF] for instance.

The hold-out and CV were originally used only for estimating the risk of an algorithm. The idea of using CV for model selection arose in the discussion of a paper by [START_REF] Efron | Combining possibly related estimation problems (with discussion)[END_REF] and in a paper by [START_REF] Geisser | A predictive approach to the random effect model[END_REF]. The first author to study LOO as a model selection procedure was [START_REF] Stone | Cross-validatory choice and assessment of statistical predictions[END_REF], who proposed to use LOO again for estimating the risk of the selected model.

Statistical properties of cross-validation estimators of the risk

Understanding the behaviour of CV for model selection, which is the purpose of this survey, requires first to analyze the performances of CV as an estimator of the risk of a single algorithm. Two main properties of CV estimators of the risk are of particular interest: their bias, and their variance.

Bias

Dealing with the bias incurred by CV estimates can be made by two strategies: evaluating the amount of bias in order to choose the least biased CV procedure, or correcting for this bias.

Theoretical assessment of the bias

The independence of the training and the validation samples imply that for every algorithm A and any

I (t) ⊂ { 1, . . . , n } with cardinality n t , E L H-O A; D n ; I (t) = E γ A D (t) n ; ξ = E [ L P ( A ( D nt ) ) ] .
Therefore, assuming that Card(I (t) j ) = n t for j = 1, . . . , B, the expectation of the CV estimator of the risk only depends on n t :

E L CV A; D n ; I (t) j 1≤j≤B = E [ L P ( A ( D nt ) ) ] . (12)
In particular (12) shows that the bias of the CV estimator of the risk of A is the difference between the risks of A, computed respectively with n t and n data points. Since n t < n, the bias of CV is usually nonnegative, which can be proved rigorously when the risk of A is a decreasing function of n, that is, when A is a smart rule; note however that a classical algorithm such as 1-nearest-neighbour in classification is not smart (Devroye et al., 1996, Section 6.8). Similarly, the bias of CV tends to decrease with n t , which is rigorously true if A is smart.

More precisely, (12) has led to several results on the bias of CV, which can be split into three main categories: asymptotic results (A is fixed and the sample size n tends to infinity), non-asymptotic results (where A is allowed to make use of a number of parameters growing with n, say n 1/2 , as often in model selection), and empirical results. They are listed below by statistical framework.

Regression The general behaviour of the bias of CV (positive, decreasing with n t ) is confirmed by several papers and for several CV estimators. For LPO, non-asymptotic expressions of its bias were proved by [START_REF] Celisse | Model Selection Via Cross-Validation in Density Estimation, Regression and Change-Points Detection[END_REF] for projection estimators, and by [START_REF] Arlot | Segmentation in the mean of heteroscedastic data via cross-validation[END_REF] for regressograms and kernels estimators when the design is fixed. For VFCV and RLT, an asymptotic expansion of their bias was yielded by [START_REF] Burman | A comparative study of ordinary cross-validation, vfold cross-validation and the repeated learning-testing methods[END_REF] for least-squares estimators in linear regression, and extended to spline smoothing [START_REF] Burman | Estimation of optimal transformations using v-fold cross validation and repeated learning-testing methods[END_REF]. Note finally that [START_REF] Efron | How biased is the apparent error rate of a prediction rule?[END_REF] proved non-asymptotic analytic expressions of the expectations of the LOO and GCV estimators of the risk in regression with binary data (see also [START_REF] Efron | Estimating the error rate of a prediction rule: improvement on cross-validation[END_REF], for some explicit calculations).

Density estimation shows a similar picture. Non-asymptotic expressions for the bias of LPO estimators for kernel and projection estimators with the quadratic risk were proved by [START_REF] Robin | Nonparametric density estimation by exact leave-p-out cross-validation[END_REF] and by [START_REF] Celisse | Density estimation via cross-validation: Model selection point of view[END_REF]. Asymptotic expansions of the bias of the LOO estimator for histograms and kernel estimators were previously proved by [START_REF] Rudemo | Empirical Choice of Histograms and Kernel Density Estimators[END_REF]; see [START_REF] Bowman | An alternative method of cross-validation for the smoothing of density estimates[END_REF] for simulations. [START_REF] Hall | On Kullback-Leibler loss and density estimation[END_REF] derived similar results with the log-likelihood contrast for kernel estimators, and related the performance of LOO to the interaction between the kernel and the tails of the target density s.

Classification For the simple problem of discriminating between two populations with shifted distributions, [START_REF] Davison | On the bias and variability of bootstrap and cross-validation estimates of error rate in discrimination problems[END_REF] compared the asymptotical bias of LOO and bootstrap, showing the superiority of the LOO when the shift size is n -1/2 : As n tends to infinity, the bias of LOO stays of order n -1 , whereas that of bootstrap worsens to the order n -1/2 . On realistic synthetic and real biological data, [START_REF] Molinaro | Prediction error estimation: a comparison of resampling methods[END_REF] compared the bias of LOO, VFCV and .632+ bootstrap: The bias decreases with n t , and is generally minimal for LOO. Nevertheless, the 10-fold CV bias is nearly minimal uniformly over their experiments. In the same experiments, .632+ bootstrap exhibits the smallest bias for moderate sample sizes and small signal-to-noise ratios, but a much larger bias otherwise.

CV-calibrated algorithms When a family of algorithm ( A λ ) λ∈Λ is given, and λ is chosen by minimizing

L CV (A λ ; D n ) over λ, L CV (A b λ ; D n ) is biased for estimating the risk of A b λ (D n ),
as reported from simulation experiments by [START_REF] Stone | Cross-validatory choice and assessment of statistical predictions[END_REF] for the LOO, and by [START_REF] Jonathan | On the use of cross-validation to assess performance in multivariate prediction[END_REF] for VFCV in the variable selection setting. This bias is of different nature compared to the previous frameworks. Indeed, L CV (A b λ , D n ) is biased simply because λ was chosen using the same data as L CV (A λ , D n ). This phenomenon is similar to the optimism of L Pn ( s (D n ) ) as an estimator of the loss of s (D n ). The correct way of estimating the risk of A b λ (D n ) with CV is to consider the full algorithm

A ′ : D n → A b λ(Dn) (D n )
, and then to compute L CV ( A ′ ; D n ). The resulting procedure is called "double cross" by [START_REF] Stone | Cross-validatory choice and assessment of statistical predictions[END_REF].

Correction of the bias

An alternative to choosing the CV estimator with the smallest bias is to correct for the bias of the CV estimator of the risk. [START_REF] Burman | A comparative study of ordinary cross-validation, vfold cross-validation and the repeated learning-testing methods[END_REF][START_REF] Burman | Estimation of optimal transformations using v-fold cross validation and repeated learning-testing methods[END_REF] proposed a corrected VFCV estimator, defined by

L corrVF (A; D n ) = L VF ( s; D n ) + L Pn ( A(D n ) ) - 1 V V j=1 L Pn A(D (-Aj ) n ) ,
and a corrected RLT estimator was defined similarly. Both estimators have been proved to be asymptotically unbiased for least-squares estimators in linear regression.

When the A j s have exactly the same size n/V , the corrected VFCV criterion is equal to the sum of the empirical risk and the V -fold penalty [START_REF] Arlot | V -fold cross-validation improved: V -fold penalization[END_REF], defined by

pen VF (A; D n ) = V -1 V V j=1 L Pn A(D (-Aj ) n ) -L P (-A j ) n A(D (-Aj ) n ) .
The V -fold penalized criterion was proved to be (almost) unbiased in the nonasymptotic framework for regressogram estimators.

Variance

CV estimators of the risk using training sets of the same size n t have the same bias, but they still behave quite differently; their variance var( L CV (A; D n ; (I

(t) j ) 1≤j≤B
)) captures most of the information to explain these differences.

Variability factors

Assume that Card(I (t) j ) = n t for every j. The variance of CV results from the combination of several factors, in particular (n t , n v ) and B.

Influence of (n t , n v ) Let us consider the hold-out estimator of the risk. Following in particular [START_REF] Nadeau | Inference for the generalization error[END_REF],

var L H-O A; D n ; I (t) = E var L P (v) n A(D (t) n ) D (t) n + var [ L P ( A(D nt ) ) ] = 1 n v E var γ ( s , ξ ) | s = A(D (t) n ) + var [ L P ( A(D nt ) ) ] . (13)
The first term, proportional to 1/n v , shows that more data for validation decreases the variance of L H-O , because it yields a better estimator of

L P A(D (t) n ) .
The second term shows that the variance of L H-O also depends on the distribution of L P A(D

(t)
n ) around its expectation; in particular, it strongly depends on the stability of A.

Stability and variance

When A is unstable, L LOO ( A ) has often been pointed out as a variable estimator (Section 7.10, [START_REF] Hastie | The elements of statistical learning[END_REF][START_REF] Breiman | Heuristics of instability and stabilization in model selection[END_REF]. Conversely, this trend disappears when A is stable, as noticed by [START_REF] Molinaro | Prediction error estimation: a comparison of resampling methods[END_REF] from a simulation experiment.

The relation between the stability of A and the variance of L CV ( A ) was pointed out by [START_REF] Devroye | Distribution-Free performance Bounds for Potential Function Rules[END_REF] in classification, through upper bounds on the variance of L LOO ( A ). [START_REF] Bousquet | Stability and Generalization[END_REF] extended these results to the regression setting, and proved upper bounds on the maximal upward deviation of L LOO ( A ).

Note finally that several approaches based on the bootstrap have been proposed for reducing the variance of L LOO ( A ), such as LOO bootstrap, .632 bootstrap and .632+ bootstrap [START_REF] Efron | Estimating the error rate of a prediction rule: improvement on cross-validation[END_REF]; see also Section 4.3.3.

Partial splitting and variance When (n t , n v ) is fixed, the variability of CV tends to be larger for partial data splitting methods than for LPO. Indeed, having to choose B < n nt subsets (I (t) j ) 1≤j≤B of { 1, . . . , n }, usually randomly, induces an additional variability compared to L LPO with p = n -n t . In the case of MCCV, this variability decreases like B -1 since the I (t) j are chosen independently. The dependence on B is slightly different for other CV estimators such as RLT or VFCV, because the I (t) j are not independent. In particular, it is maximal for the hold-out, and minimal (null) for LOO (if n t = n -1) and LPO (with p = n -n t ).

Note that the dependence on V for VFCV is more complex to evaluate, since B, n t , and n v simultaneously vary with V . Nevertheless, a non-asymptotic theoretical quantification of this additional variability of VFCV has been obtained by [START_REF] Robin | Nonparametric density estimation by exact leave-p-out cross-validation[END_REF] in the density estimation framework (see also empirical considerations by [START_REF] Jonathan | On the use of cross-validation to assess performance in multivariate prediction[END_REF].

Theoretical assessment of the variance

Understanding precisely how var( L CV (A)) depends on the splitting scheme is complex in general, since n t and n v have a fixed sum n, and the number of splits B is generally linked with n t (for instance, for LPO and VFCV). Furthermore, the variance of CV behaves quite differently in different frameworks, depending in particular on the stability of A. The consequence is that contradictory results have been obtained in different frameworks, in particular on the value of V for which the VFCV estimator of the risk has a minimal variance [START_REF] Burman | A comparative study of ordinary cross-validation, vfold cross-validation and the repeated learning-testing methods[END_REF]Hastie et al., 2001, Section 7.10). Despite the difficulty of the problem, the variance of several CV estimators of the risk has been assessed in several frameworks, as detailed below.

Regression In the linear regression setting, [START_REF] Burman | A comparative study of ordinary cross-validation, vfold cross-validation and the repeated learning-testing methods[END_REF] yielded asymptotic expansions of the variance of the VFCV and RLT estimators of the risk with homoscedastic data. The variance of RLT decreases with B, and in the case of VFCV, in a particular setting,

var L VF (A) = 2σ 2 n + 4σ 4 n 2 4 + 4 V -1 + 2 (V -1) 2 + 1 (V -1) 3 + o n -2 .
The asymptotical variance of the VFCV estimator of the risk decreases with V , implying that LOO asymptotically has the minimal variance.

Non-asymptotic closed-form formulas of the variance of the LPO estimator of the risk have been proved by [START_REF] Celisse | Model Selection Via Cross-Validation in Density Estimation, Regression and Change-Points Detection[END_REF] in regression, for projection and kernel estimators for instance. On the variance of RLT in the regression setting, see the asymptotic results of [START_REF] Girard | Asymptotic comparison of (partial) cross-validation, GCV and randomized GCV in nonparametric regression[END_REF] for Nadaraya-Watson kernel estimators, as well as the non-asymptotic computations and simulation experiments by [START_REF] Nadeau | Inference for the generalization error[END_REF] with several learning algorithms.

Density estimation Non-asymptotic closed-form formulas of the variance of the LPO estimator of the risk have been proved by [START_REF] Robin | Nonparametric density estimation by exact leave-p-out cross-validation[END_REF] and by [START_REF] Celisse | Density estimation via cross-validation: Model selection point of view[END_REF] for projection and kernel estimators. In particular, the dependence of the variance of L LPO on p has been quantified explicitly for histogram and kernel estimators by [START_REF] Robin | Nonparametric density estimation by exact leave-p-out cross-validation[END_REF].

Classification For the simple problem of discriminating between two populations with shifted distributions, [START_REF] Davison | On the bias and variability of bootstrap and cross-validation estimates of error rate in discrimination problems[END_REF] showed that the gap between asymptotic variances of LOO and bootstrap becomes larger when data are noisier. [START_REF] Nadeau | Inference for the generalization error[END_REF] made non-asymptotic computations and simulation experiments with several learning algorithms. [START_REF] Hastie | The elements of statistical learning[END_REF] empirically showed that VFCV has a minimal variance for some 2 < V < n, whereas LOO usually has a large variance; this fact certainly depends on the stability of the algorithm considered, as showed by simulation experiments by [START_REF] Molinaro | Prediction error estimation: a comparison of resampling methods[END_REF].

Estimation of the variance

There is no universal-valid under all distributions-unbiased estimator of the variance of RLT [START_REF] Nadeau | Inference for the generalization error[END_REF] and VFCV estimators [START_REF] Bengio | No unbiased estimator of the variance of K-fold cross-validation[END_REF]. In particular, [START_REF] Bengio | No unbiased estimator of the variance of K-fold cross-validation[END_REF] recommend the use of variance estimators taking into account the correlation structure between test errors; otherwise, the variance of CV can be strongly underestimated.

Despite these negative results, (biased) estimators of the variance of L CV have been proposed by [START_REF] Nadeau | Inference for the generalization error[END_REF], by [START_REF] Bengio | No unbiased estimator of the variance of K-fold cross-validation[END_REF] and by [START_REF] Markatou | Analysis of variance of cross-validation estimators of the generalization error[END_REF], and tested in simulation experiments in regression and classification. Furthermore, in the framework of density estimation with histograms, [START_REF] Robin | Nonparametric density estimation by exact leave-p-out cross-validation[END_REF] proposed an estimator of the variance of the LPO risk estimator. Its accuracy is assessed by a concentration inequality. These results have recently been extended to projection estimators by [START_REF] Celisse | Density estimation via cross-validation: Model selection point of view[END_REF].

Cross-validation for efficient model selection

This section tackles the properties of CV procedures for model selection when the goal is estimation (see Section 2.2).

Relationship between risk estimation and model selection

As shown in Section 3.1, minimizing an unbiased estimator of the risk leads to an efficient model selection procedure. One could conclude here that the best CV procedure for estimation is the one with the smallest bias and variance (at least asymptotically), for instance, LOO in the least-squares regression framework [START_REF] Burman | A comparative study of ordinary cross-validation, vfold cross-validation and the repeated learning-testing methods[END_REF]. Nevertheless, the best CV estimator of the risk is not necessarily the best model selection procedure. For instance, [START_REF] Breiman | Submodel selection and evaluation in regression. the x-random case[END_REF] observed that uniformly over the models, the best risk estimator is LOO, whereas 10fold CV is more accurate for model selection. Three main reasons for such a difference can be invoked. First, the asymptotic framework (A fixed, n → ∞) may not apply to models close to the oracle, which typically has a dimension growing with n when s does not belong to any model. Second, as explained in Section 3.2, estimating the risk of each model with some bias can be beneficial and compensate the effect of a large variance, in particular when the signal-tonoise ratio is small. Third, for model selection, what matters is not that every estimate of the risk has small bias and variance, but more that sign ( crit(m 1 )crit(m 2 ) ) = sign ( L P ( s m1 ) -L P ( s m2 ) )

with the largest probability for models m 1 , m 2 near the oracle.

Therefore, specific studies are required to evaluate the performances of the various CV procedures in terms of model selection efficiency. In most frameworks, the model selection performance directly follows from the properties of CV as an estimator of the risk, but not always.

The global picture

Let us start with the classification of model selection procedures made by [START_REF] Shao | An asymptotic theory for linear model selection[END_REF] in the linear regression framework, since it gives a good idea of the performance of CV procedures for model selection in general. Typically, the efficiency of CV only depends on the asymptotics of n t /n :

• When n t ∼ n, CV is asymptotically equivalent to Mallows' C p , hence asymptotically optimal.

• When n t ∼ λn with λ ∈ (0, 1), CV is asymptotically equivalent to GIC κ with κ = 1+λ -1 , which is defined as AIC with a penalty multiplied by κ/2. Hence, such CV procedures are overpenalizing by a factor (1+λ)/(2λ) > 1.

The above results have been proved by [START_REF] Shao | An asymptotic theory for linear model selection[END_REF] for LPO (see also [START_REF] Li | Asymptotic optimality for C p , C L , cross-validation and generalized cross-validation: discrete index set[END_REF], for the LOO); they also hold for RLT when B ≫ n 2 since RLT is then equivalent to LPO [START_REF] Zhang | Model selection via multifold cross validation[END_REF].

In a general statistical framework, the model selection performance of MCCV, VFCV, LOO, LOO Bootstrap, and .632 bootstrap for selection among minimum contrast estimators was studied in a series of papers (van der [START_REF] Van Der Laan | Unified cross-validation methodology for selection among estimators and a general cross-validated adaptive epsilonnet estimator: Finite sample oracle inequalities and examples[END_REF][START_REF] Van Der Laan | Asymptotic optimality of likelihood-based cross-validation[END_REF]van der Laan et al., , 2006;;van der Vaart et al., 2006); these results apply in particular to least-squares regression and density estimation. It turns out that under mild conditions, an oracle-type inequality is proved, showing that up to a multiplying factor C n → 1, the risk of CV is smaller than the minimum of the risks of the models with a sample size n t . In particular, in most frameworks, this implies the asymptotic optimality of CV as soon as n t ∼ n. When n t ∼ λn with λ ∈ (0, 1), this naturally generalizes Shao's results.

Results in various frameworks

This section gathers results about model selection performances of CV when the goal is estimation, in various frameworks. Note that model selection is considered here with a general meaning, including in particular bandwidth choice for kernel estimators.

Regression First, the results of Section 6.2 suggest that CV is suboptimal when n t is not asymptotically equivalent to n. This fact has been proved rigorously for VFCV when V = O(1) with regressograms [START_REF] Arlot | V -fold cross-validation improved: V -fold penalization[END_REF]: with large probability, the risk of the model selected by VFCV is larger than 1 + κ(V ) times the risk of the oracle, with κ(V ) > 0 for every fixed V . Note however that the best V for VFCV is not the largest one in every regression framework, as shown empirically in linear regression [START_REF] Breiman | Submodel selection and evaluation in regression. the x-random case[END_REF][START_REF] Herzberg | A note on modifications of jackknife criterion for model selection[END_REF]; [START_REF] Breiman | Heuristics of instability and stabilization in model selection[END_REF] proposed to explain this phenomenon by relating the stability of the candidate algorithms and the model selection performance of LOO in various regression frameworks.

Second, the "universality" of CV has been confirmed by showing that it naturally adapts to heteroscedasticity of data when selecting among regressograms. Despite its suboptimality, VFCV with V = O(1) satisfies a non-asymptotic oracle inequality with constant C > 1 [START_REF] Arlot | V -fold cross-validation improved: V -fold penalization[END_REF]. Furthermore, V -fold penalization (which often coincides with corrected VFCV, see Section 5.1.2) satisfies a non-asymptotic oracle inequality with C n → 1 as n → +∞, both when V = O(1) [START_REF] Arlot | V -fold cross-validation improved: V -fold penalization[END_REF] and when V = n (Arlot, 2008a). Note that n-fold penalization is very close to LOO, suggesting that it is also asymptotically optimal with heteroscedastic data. Simulation experiments in the context of changepoint detection confirmed that CV adapts well to heteroscedasticity, contrary to usual model selection procedures in the same framework [START_REF] Arlot | Segmentation in the mean of heteroscedastic data via cross-validation[END_REF].

The performances of CV have also been assessed for other kinds of estimators in regression. For choosing the number of knots in spline smoothing, [START_REF] Burman | Estimation of optimal transformations using v-fold cross validation and repeated learning-testing methods[END_REF] proved that corrected versions of VFCV and RLT are asymptotically optimal provided n/(Bn v ) = O(1). Furthermore, in kernel regression, several CV methods have been compared to GCV in kernel regression by [START_REF] Härdle | How far are automatically chosen regression smoothing parameters from their optimum?[END_REF] and by [START_REF] Girard | Asymptotic comparison of (partial) cross-validation, GCV and randomized GCV in nonparametric regression[END_REF]; the conclusion is that GCV and related criteria are computationally more efficient than MCCV or RLT, for a similar statistical performance.

Finally, note that asymptotic results about CV in regression have been proved by [START_REF] Györfi | A distribution-free theory of nonparametric regression[END_REF], and an oracle inequality with constant C > 1 has been proved by [START_REF] Wegkamp | Model selection in nonparametric regression[END_REF] for the hold-out, with least-squares estimators.

Density estimation CV performs similarly than in regression for selecting among least-squares estimators (van der [START_REF] Van Der Laan | Asymptotic optimality of likelihood-based cross-validation[END_REF]: It yields a risk smaller than the minimum of the risk with a sample size n t . In particular, non-asymptotic oracle inequalities with constant C > 1 have been proved by [START_REF] Celisse | Model Selection Via Cross-Validation in Density Estimation, Regression and Change-Points Detection[END_REF] for the LPO when p/n ∈ [a, b], for some 0 < a < b < 1.

The performance of CV for selecting the bandwidth of kernel density estimators has been studied in several papers. With the least-squares contrast, the efficiency of LOO was proved by [START_REF] Hall | Large sample optimality of least squares cross-validation in density estimation[END_REF] and generalized to the multivariate framework by [START_REF] Stone | An asymptotically optimal window selection rule for kernel density estimates[END_REF]; an oracle inequality asymptotically leading to efficiency was recently proved by [START_REF] Dalelane | Exact oracle inequality for sharp adaptive kernel density estimator[END_REF]. With the Kullback-Leibler divergence, CV can suffer from troubles in performing model selection (see also [START_REF] Schuster | On the consistency of maximum likelihood nonparametric density estimators[END_REF][START_REF] Chow | Consistent cross-validated density estimation[END_REF]. The influence of the tails of the target s was studied by [START_REF] Hall | On Kullback-Leibler loss and density estimation[END_REF], who gave conditions under which CV is efficient and the chosen bandwidth is optimal at first-order.

Classification In the framework of binary classification by intervals (that is, with X = [0, 1] and piecewise constant classifiers), [START_REF] Kearns | An Experimental and Theoretical Comparison of Model Selection Methods[END_REF] proved an oracle inequality for the hold-out. Furthermore, empirical experiments show that CV yields (almost) always the best performance, compared to deterministic penalties [START_REF] Kearns | An Experimental and Theoretical Comparison of Model Selection Methods[END_REF]. On the contrary, simulation experiments by Bartlett et al. (2002) in the same setting showed that random penalties such as Rademacher complexity and maximal discrepancy usually perform much better than hold-out, which is shown to be more variable.

Nevertheless, the hold-out still enjoys quite good theoretical properties: It was proved to adapt to the margin condition by [START_REF] Blanchard | Discussion: "Local Rademacher complexities and oracle inequalities in risk minimization[END_REF], a property nearly unachievable with usual model selection procedures (see also Massart, 2007, Section 8.5). This suggests that CV procedures are naturally adaptive to several unknown properties of data in the statistical learning framework.

The performance of the LOO in binary classification was related to the stability of the candidate algorithms by [START_REF] Kearns | Algorithmic Stability and Sanity-Check Bounds for Leave-One-Out Cross-Validation[END_REF]; they proved oracle-type inequalities called "sanity-check bounds", describing the worst-case performance of LOO (see also [START_REF] Bousquet | Stability and Generalization[END_REF].

An experimental comparison of several CV methods and bootstrap-based CV (in particular .632+ bootstrap) in classification can also be found in papers by [START_REF] Efron | How biased is the apparent error rate of a prediction rule?[END_REF] and [START_REF] Efron | Improvements on cross-validation: the .632+ bootstrap method[END_REF].

Cross-validation for identification

Let us now focus on model selection when the goal is to identify the "true model" S m0 , as described in Section 2.3. In this framework, asymptotic optimality is replaced by (model) consistency, that is,

P ( m(D n ) = m 0 ) ----→ n→∞ 1 .
Classical model selection procedures built for identification, such as BIC, are described in Section 3.3.

General conditions towards model consistency

At first sight, it may seem strange to use CV for identification: LOO, which is the pioneering CV procedure, is actually closely related to the unbiased risk estimation principle, which is only efficient when the goal is estimation. Furthermore, estimation and identification are somehow contradictory goals, as explained in Section 2.4.

This intuition about inconsistency of some CV procedures is confirmed by several theoretical results. [START_REF] Shao | Linear model selection by cross-validation[END_REF] proved that several CV methods are inconsistent for variable selection in linear regression: LOO, LPO, and BICV when lim inf n→∞ (n t /n) > 0. Even if these CV methods asymptotically select all the true variables with probability 1, the probability that they select too much variables does not tend to zero. More generally, [START_REF] Shao | An asymptotic theory for linear model selection[END_REF] proved that CV procedures behave asymptotically like GIC λn with λ n = 1 + n/n t , which leads to inconsistency as soon as n/n t = O(1).

In the context of ordered variable selection in linear regression, Zhang (1993) computed the asymptotic value of the probability of selecting the true model for several CV procedures. He also numerically compared the values of this probability for the same CV procedures in a specific example. For LPO with p/n → λ ∈ (0, 1) as n tends to +∞, P ( m = m 0 ) increases with λ. The result is slightly different for VFCV: P ( m = m 0 ) increases with V (hence, it is maximal for the LOO, which is the worst case of LPO). The variability induced by the number V of splits seems to be more important here than the bias of VFCV. Nevertheless, P ( m = m 0 ) is almost constant between V = 10 and V = n, so that taking V > 10 is not advised for computational reasons.

These results suggest that if the training sample size n t is negligible in front of n, then model consistency could be obtained. This has been confirmed theoretically by [START_REF] Shao | Linear model selection by cross-validation[END_REF][START_REF] Shao | An asymptotic theory for linear model selection[END_REF] for the variable selection problem in linear regression: CV is consistent when n ≫ n t → ∞, in particular RLT, BICV (defined in Section 4.3.2) and LPO with p = p n ∼ n and n -p n → ∞.

Therefore, when the goal is to identify the true model, a larger proportion of the data should be put in the validation set in order to improve the performance. This phenomenon is somewhat related to the cross-validation paradox [START_REF] Yang | Comparing learning methods for classification[END_REF].

Refined analysis for the algorithm selection problem

The behaviour of CV for identification is better understood by considering a more general framework, where the goal is to select among statistical algorithms the one with the fastest convergence rate. [START_REF] Yang | Comparing learning methods for classification[END_REF][START_REF] Yang | Consistency of cross validation for comparing regression procedures[END_REF] considered this problem for two candidate algorithms (or more generally any finite number of algorithms). Let us mention here that [START_REF] With Discussion By | Asymptotics for and against cross-validation[END_REF] considered a few specific examples of this problem, and showed that LOO can be inconsistent for choosing the best among two "good" estimators.

The conclusion of Yang's papers is that the sufficient condition on n t for the consistency in selection of CV strongly depends on the convergence rates ( r n,i ) i=1,2 of the candidate algorithms. Let us assume that r n,1 and r n,2 differ at least by a multiplicative constant C > 1. Then, in the regression framework, if the risk of s i is measured by E s i -s 2 , [START_REF] Yang | Consistency of cross validation for comparing regression procedures[END_REF] proved that the holdout, VFCV, RLT and LPO with voting (CV-v, see Section 4.2.2) are consistent in selection if

n v , n t → ∞ and √ n v max i r nt,i → ∞ , (14)
under some conditions on s i -s p for p = 2, 4, ∞. In the classification framework, if the risk of s i is measured by P ( s i = s ), [START_REF] Yang | Comparing learning methods for classification[END_REF] proved the same consistency result for CV-v under the condition

n v , n t → ∞ and n v max i r 2 nt,i s nt → ∞ , (15)
where s n is the convergence rate of P ( s

1 (D n ) = s 2 (D n ) ).
Intuitively, consistency holds as soon as the uncertainty of each estimate of the risk (roughly proportional to n

-1/2 v
) is negligible in front of the risk gap |r nt,1 -r nt,2 | (which is of the same order as max i r nt,i ). This condition holds either when at least one of the algorithms converges at a non-parametric rate, or when n t ≪ n, which artificially widens the risk gap.

Empirical results in the same direction were proved by Dietterich (1998) and by [START_REF] Alpaydin | Combined 5 x 2 cv F test for comparing supervised classification learning algorithms[END_REF], leading to the advice that V = 2 is the best choice when VFCV is used for comparing two learning procedures. See also the results by [START_REF] Nadeau | Inference for the generalization error[END_REF] about CV considered as a testing procedure comparing two candidate algorithms.

The sufficient conditions ( 14) and ( 15) can be simplified depending on max i r n,i , so that the ability of CV to distinguish between two algorithms depends on their convergence rates. On the one hand, if max i r n,i ∝ n -1/2 , then ( 14) or ( 15) only hold when n v ≫ n t → ∞ (under some conditions on s n in classification). Therefore, the cross-validation paradox holds for comparing algorithms converging at the parametric rate (model selection when a true model exists being only a particular case). Note that possibly stronger conditions can be required in classification where algorithms can converge at fast rates, between n -1 and n -1/2 .

On the other hand, ( 14) and ( 15) are milder conditions when max i r n,i ≫ n -1/2 : They are implied by n t /n v = O(1), and they even allow n t ∼ n (under some conditions on s n in classification). Therefore, non-parametric algorithms can be compared by more usual CV procedures (n t > n/2), even if LOO is still excluded by conditions ( 14) and (15).

Note that according to a simulation experiments, CV with averaging (that is, CV as usual) and CV with voting are equivalent at first but not at second order, so that they can differ when n is small [START_REF] Yang | Consistency of cross validation for comparing regression procedures[END_REF].

Specificities of some frameworks

Originally, the CV principle has been proposed for i.i.d. observations and usual contrasts such as least-squares and log-likelihood. Therefore, CV procedures may have to be modified in other specific frameworks, such as estimation in presence of outliers or with dependent data.

Density estimation

In the density estimation framework, some specific modifications of CV have been proposed.

First, [START_REF] Hall | Smoothed cross-validation[END_REF] defined the "smoothed CV", which consists in presmoothing the data before using CV, an idea related to the smoothed bootstrap.

They proved that smoothed CV yields an excellent asymptotical model selection performance under various smoothness conditions on the density.

Second, when the goal is to estimate the density at one point (and not globally), [START_REF] Hall | A local cross-validation algorithm[END_REF] proposed a local version of CV and proved its asymptotic optimality.

Robustness to outliers

In presence of outliers in regression, [START_REF] Leung | Cross-validation in nonparametric regression with outliers[END_REF] studied how CV must be modified to get both asymptotic efficiency and a consistent bandwidth estimator (see also [START_REF] Leung | Bandwidth selection in robust smoothing[END_REF].

Two changes are possible to achieve robustness: Choosing a "robust" regressor, or choosing a robust loss-function. In presence of outliers, classical CV with a non-robust loss function has been shown to fail by [START_REF] Härdle | How to determine the bandwidth of some nonlinear smoothers in practice[END_REF]. [START_REF] Leung | Cross-validation in nonparametric regression with outliers[END_REF] described a CV procedure based on robust losses like L 1 and Huber's [START_REF] Huber | Robust estimation of a local parameter[END_REF] ones. The same strategy remains applicable to other setups like linear models in [START_REF] Ronchetti | Robust linear model selection by cross-validation[END_REF].

Time series and dependent observations

As explained in Section 4.1, CV is built upon the heuristics that part of the sample (the validation set) can play the role of new data with respect to the rest of the sample (the training set). "New" means that the validation set is independent from the training set with the same distribution.

Therefore, when data ξ 1 , . . . , ξ n are not independent, CV must be modified, like other model selection procedures (in non-parametric regression with dependent data, see the review by [START_REF] Opsomer | Nonparametric regression with correlated errors[END_REF].

Let us first consider the statistical framework of Section 1 with ξ 1 , . . . , ξ n identically distributed but not independent. Then, when for instance data are positively correlated, [START_REF] Hart | Kernel regression estimation using repeated measurements data[END_REF] proved that CV overfits for choosing the bandwidth of a kernel estimator in regression (see also [START_REF] Chu | Comparison of two bandwidth selectors with dependent errors[END_REF][START_REF] Opsomer | Nonparametric regression with correlated errors[END_REF].

The main approach used in the literature for solving this issue is to choose I (t) and I (v) such that min i∈I (t) , j∈I (v) |i -j| > h > 0, where h controls the distance from which observations i and j are independent. For instance, the LOO can be changed into: I (v) = { J } where J is uniformly chosen in { 1, . . . , n }, and I (t) = { 1, . . . , J -h -1, J + h + 1, . . . , n }, a method called "modified CV" by [START_REF] Chu | Comparison of two bandwidth selectors with dependent errors[END_REF] in the context of bandwidth selection. Then, for short range dependences, ξ i is almost independent from ξ j when |i -j| > h is large enough, so that ( ξ j ) j∈I (t) is almost independent from ( ξ j ) j∈I (v) . Several asymptotic optimality results have been proved on modified CV, for instance by [START_REF] Hart | Data-driven bandwidth choice for density estimation based on dependent data[END_REF] for bandwidth choice in kernel density estimation, when data are α-mixing (hence, with a short range dependence structure) and h = h n → ∞ "not too fast". Note that modified CV also enjoys some asymptotic optimality results with long-range dependences, as proved by [START_REF] Hall | On bandwidth choice in nonparametric regression with both short-and long-range dependent errors[END_REF], even if an alternative block bootstrap method seems more appropriate in such a framework. Several alternatives to modified CV have also been proposed. The "h-block CV" [START_REF] Burman | A cross-validatory method for dependent data[END_REF] is modified CV plus a corrective term, similarly to the bias-corrected CV by [START_REF] Burman | A comparative study of ordinary cross-validation, vfold cross-validation and the repeated learning-testing methods[END_REF] (see Section 5.1). Simulation experiments in several (short range) dependent frameworks show that this corrective term matters when h/n is not small, in particular when n is small.

The "partitioned CV" has been proposed by [START_REF] Chu | Comparison of two bandwidth selectors with dependent errors[END_REF] for bandwidth selection: An integer g > 0 is chosen, a bandwidth λ k is chosen by CV based upon the subsample ( ξ k+gj ) j≥0 for each k = 1, . . . , g, and the selected bandwidth is a combination of ( λ k ).

When a parametric model is available for the dependency structure, [START_REF] Hart | Automated kernel smoothing of dependent data by using time series cross-validation[END_REF] proposed the "time series CV".

An important framework where data often are dependent is time-series analysis, in particular when the goal is to predict the next observation ξ n+1 from the past ξ 1 , . . . , ξ n . When data are stationary, h-block CV and similar approaches can be used to deal with (short range) dependences. Nevertheless, [START_REF] Burman | Data-dependent estimation of prediction functions[END_REF] proved in some specific framework that unaltered CV is asymptotic optimal when ξ 1 , . . . , ξ n is a stationary Markov process.

On the contrary, using CV for non-stationary time-series is a quite difficult problem. The only reasonable approach in general is the hold-out, that is, I (t) = { 1, . . . , m } and I (v) = { m + 1, . . . , n } for some deterministic m. Each model is first trained with ( ξ j ) j∈I (t) . Then, it is used for predicting successively ξ m+1 from ( ξ j ) j≤m , ξ m+2 from ( ξ j ) j≤m+1 , and so on. The model with the smallest average error for predicting ( ξ j ) j∈I (v) from the past is chosen.

Large number of models

As mentioned in Section 3, model selection procedures estimating unbiasedly the risk of each model fail when, in particular, the number of models grows exponentially with n [START_REF] Birgé | Minimal penalties for Gaussian model selection[END_REF]. Therefore, CV cannot be used directly, except maybe with n t ≪ n, provided n t is well chosen (see Section 6 and Celisse, 2008b, Chapter 6).

For least-squares regression with homoscedastic data, [START_REF] Wegkamp | Model selection in nonparametric regression[END_REF] proposed to add to the hold-out estimator of the risk a penalty term depending on the number of models. This method is proved to satisfy a non-asymptotic oracle inequality with leading constant C > 1.

Another general approach was proposed by [START_REF] Arlot | Segmentation in the mean of heteroscedastic data via cross-validation[END_REF] in the context of multiple change-point detection. The idea is to perform model selection in two steps: First, gather the models ( S m ) m∈Mn into meta-models ( S D ) D∈Dn , where D n denotes a set of indices such that Card(D n ) grows at most polynomially with n. Inside each meta-model S D = m∈Mn(D) S m , s D is chosen from data by optimizing a given criterion, for instance the empirical contrast L Pn ( t ), but other criteria can be used. Second, CV is used for choosing among ( s D ) D∈Dn . Simulation experiments show this simple trick automatically takes into account the cardinality of M n , even when data are heteroscedastic, contrary to other model selection procedures built for exponential collection of models which all assume homoscedasticity of data.

Closed-form formulas and fast computation

Resampling strategies, like CV, are known to be time consuming. The naive implementation of CV has a computational complexity of B times the complexity of training each algorithm A, which is usually intractable for LPO, even with p = 1. The computational cost of VFCV or RLT can still be quite costly when B > 10 in many practical problems. Nevertheless, closed-form formulas for CV estimators of the risk can be obtained in several frameworks, which greatly decreases the computational cost of CV.

In density estimation, closed-form formulas have been originally derived by [START_REF] Rudemo | Empirical Choice of Histograms and Kernel Density Estimators[END_REF] and by [START_REF] Bowman | An alternative method of cross-validation for the smoothing of density estimates[END_REF] for the LOO risk estimator of histograms and kernel estimators. These results have been recently extended by [START_REF] Robin | Nonparametric density estimation by exact leave-p-out cross-validation[END_REF] to the LPO risk estimator with the quadratic loss. Similar results are more generally available for projection estimators as settled by [START_REF] Celisse | Density estimation via cross-validation: Model selection point of view[END_REF]. Intuitively, such formulas can be obtained provided the number N of values taken by the B = n nv hold-out estimators of the risk, corresponding to different data splittings, is at most polynomial in the sample size.

For least-squares estimators in linear regression, [START_REF] Zhang | Model selection via multifold cross validation[END_REF] proved a closed-form formula for the LOO estimator of the risk. Similar results have been obtained by [START_REF] Wahba | Periodic splines for spectral density estimation: The use of cross validation for determining the degree of smoothing[END_REF][START_REF] Wahba | Practical Approximate Solutions to Linear Operator Equations When the Data are Noisy[END_REF], and by [START_REF] Craven | Smoothing noisy data with spline functions. Estimating the correct degree of smoothing by the method of generalized cross-validation[END_REF] in the spline smoothing context as well. These papers led in particular to the definition of GCV (see Section 4.3.3) and related procedures, which are often used instead of CV (with a naive implementation) because of their small computational cost, as emphasized by [START_REF] Girard | Asymptotic comparison of (partial) cross-validation, GCV and randomized GCV in nonparametric regression[END_REF].

Closed-form formulas for the LPO estimator of the risk were also obtained by [START_REF] Celisse | Model Selection Via Cross-Validation in Density Estimation, Regression and Change-Points Detection[END_REF] in regression for kernel and projection estimators, in particular for regressograms. An important property of these closed-form formulas is their additivity: For a regressogram associated to a partition (I λ ) λ∈Λm of X , the LPO estimator of the risk can be written as a sum over λ ∈ Λ m of terms which only depend on observations (X i , Y i ) such that X i ∈ I λ . Therefore, dynamic programming [START_REF] Bellman | Applied Dynamic Programming[END_REF] can be used for minimizing the LPO estimator of the risk over the set of partitions of X in D pieces. As an illustration, [START_REF] Arlot | Segmentation in the mean of heteroscedastic data via cross-validation[END_REF] successfully applied this strategy in the change-point detection framework. Note that the same idea can be used with VFCV or RLT, but for a larger computational cost since no closed-form formulas are available for these CV methods.

Finally, in frameworks where no closed-form formula can be proved, some efficient algorithms exist for avoiding to recompute L H-O (A; D n ; I (t) j ) from scratch for each data splitting I (t) j . These algorithms rely on updating formulas such as the ones by [START_REF] Ripley | Pattern Recognition and Neural Networks[END_REF] for LOO in linear and quadratic discriminant analysis; this approach makes LOO as expensive to compute as the empirical risk.

Very similar formulas are also available for LOO and the k-nearest neighbours estimator in classification [START_REF] Daudin | Estimation of the conditional risk in classification: The swapping method[END_REF].

Nevertheless, in density estimation, closed-form expressions of the LPO estimator have been derived by [START_REF] Robin | Nonparametric density estimation by exact leave-p-out cross-validation[END_REF] with histograms and kernel estimators, and by [START_REF] Celisse | Density estimation via cross-validation: Model selection point of view[END_REF] for projection estimators. These expressions allow to perform LPO without additional computational cost, which reduces the aforementioned trade-off to the easier bias-variability trade-off. In particular, [START_REF] Robin | Nonparametric density estimation by exact leave-p-out cross-validation[END_REF] proposed to choose p for LPO by minimizing a criterion defined as the sum of a squared bias and a variance terms (see also Politis et al., 1999, Chapter 9).

10.2 How the splits should be chosen?

For hold-out, VFCV, and RLT, an important question is to choose a particular sequence of data splits.

First, should this step be random and independent from D n , or take into account some features of the problem or of the data? It is often recommended to take into account the structure of data when choosing the splits. If data are stratified, the proportions of the different strata should (approximately) be the same in the sample and in each training and validation sample. Besides, the training samples should be chosen so that s m (D (t) n ) is well defined for every training set; in the regressogram case, this led [START_REF] Arlot | V -fold cross-validation improved: V -fold penalization[END_REF] and [START_REF] Arlot | Segmentation in the mean of heteroscedastic data via cross-validation[END_REF] to choose carefully the splitting scheme. In supervised classification, practitioners usually choose the splits so that the proportion of each class is the same in every validation sample as in the sample. Nevertheless, [START_REF] Breiman | Submodel selection and evaluation in regression. the x-random case[END_REF] made simulation experiments in regression for comparing several splitting strategies. No significant improvement was reported from taking into account the stratification of data for choosing the splits.

Another question related to the choice of (I (t) j ) 1≤j≤B is whether the I (t) j should be independent (like MCCV), slighly dependent (like RLT), or strongly dependent (like VFCV). It seems intuitive that giving similar roles to all data points in the B "training and validation tasks" should yield more reliable results as other methods. This intuition may explain why VFCV is much more used than RLT or MCCV. Similarly, [START_REF] Shao | Linear model selection by cross-validation[END_REF] proposed a CV method called BICV, where every point and pair of points appear in the same number of splits, see Section 4.3.2. Nevertheless, most recent theoretical results on the various CV procedures are not accurate enough to distinguish which one may be the best splitting strategy: This remains a widely open theoretical question. Note finally that the additional variability due to the choice of a sequence of data splits was quantified empirically by [START_REF] Jonathan | On the use of cross-validation to assess performance in multivariate prediction[END_REF] and theoretically by [START_REF] Robin | Nonparametric density estimation by exact leave-p-out cross-validation[END_REF] for VFCV.

V-fold cross-validation

VFCV is certainly the most popular CV procedure, in particular because of its mild computational cost. Nevertheless, the question of choosing V remains widely open, even if indications can be given towards an appropriate choice.

A specific feature of VFCV-as well as exhaustive strategies-is that choosing V uniquely determines the size of the training set n t = n(V -1)/V and the number of splits B = V , hence the computational cost. Contradictory phenomena then occur.

On the one hand, the bias of VFCV decreases with V since n t = n(1 -1/V ) observations are used in the training set. On the other hand, the variance of VFCV decreases with V for small values of V , whereas the LOO (V = n) is known to suffer from a high variance in several frameworks such as classification or density estimation. Note however that the variance of VFCV is minimal for V = n in some frameworks like linear regression (see Section 5.2). Furthermore, estimating the variance of VFCV from data is a difficult problem in general, see Section 5.2.3.

When the goal of model selection is estimation, it is often reported in the literature that the optimal V is between 5 and 10, because the statistical performance does not increase much for larger values of V , and averaging over 5 or 10 splits remains computationally feasible (Hastie et al., 2001, Section 7.10). Even if this claim is clearly true for many problems, the conclusion of this survey is that better statistical performance can sometimes be obtained with other values of V , for instance depending on the SNR value.

When the SNR is large, the asymptotic comparison of CV procedures recalled in Section 6.2 can be trusted: LOO performs (nearly) unbiased risk estimation hence is asymptotically optimal, whereas VFCV with V = O(1) is suboptimal. On the contrary, when the SNR is small, overpenalization can improve the performance. Therefore, VFCV with V < n can yield a smaller risk than LOO thanks to its bias and despite its variance when V is small (see simulation experiments by [START_REF] Arlot | V -fold cross-validation improved: V -fold penalization[END_REF]. Furthermore, other CV procedures like RLT can be interesting alternatives to VFCV, since they allow to choose the bias (through n t ) independently from B, which mainly governs the variance. Another possible alternative is V -fold penalization, which is related to corrected VFCV (see Section 4.3.3).

When the goal of model selection is identification, the main drawback of VFCV is that n t ≪ n is often required for choosing consistently the true model (see Section 7), whereas VFCV does not allow n t < n/2. Depending on the frameworks, different (empirical) recommandations for choosing V can be found in the literature. In ordered variable selection, the largest V seems to be the better, V = 10 providing results close to the optimal ones [START_REF] Zhang | Model selection via multifold cross validation[END_REF]. On the contrary, [START_REF] Dietterich | Approximate statistical tests for comparing supervised classification learning algorithms[END_REF] and [START_REF] Alpaydin | Combined 5 x 2 cv F test for comparing supervised classification learning algorithms[END_REF] recommend V = 2 for choosing the best learning procedures among two candidates.

Future research

Perhaps the most important direction for future research would be to provide, in each specific framework, precise quantitative measures of the variance of CV estimators of the risk, depending on n t , the number of splits, and how the splits are chosen. Up to now, only a few precise results have been obtained in this direction, for some specific CV methods in linear regression or density estimation (see Section 5.2). Proving similar results in other frameworks and for more general CV methods would greatly help to choose a CV method for any given model selection problem.

More generally, most theoretical results are not precise enough to make any distinction between the hold-out and CV methods having the same training sample size n t , because they are equivalent at first order. Second order terms do matter for realistic values of n, which shows the dramatic need for theory that takes into account the variance of CV when comparing CV methods such as VFCV and RLT with n t = n(V -1)/V but B = V .

  The idea is that the empirical contrast L Pn ( t ) has an expectation L

P ( t ) which is minimal over S at s. Hence, minimizing L Pn ( t ) over a set S of candidate values for s hopefully leads to a good estimator of s. Let us now give three popular examples of empirical contrast minimizers:

10 Conclusion: which cross-validation method for which problem?

This conclusion collects a few guidelines aiming at helping CV users, first interpreting the results of CV, second appropriately using CV in each specific problem.

The general picture

Drawing a general conclusion on CV methods is an impossible task because of the variety of frameworks where CV can be used, which induces a variety of behaviors of CV. Nevertheless, we can still point out the three main criteria to take into account for choosing a CV method for a particular model selection problem:

• Bias: CV roughly estimates the risk of a model with a sample size n t < n (see Section 5.1). Usually, this implies that CV overestimates the variance term compared to the bias term in the bias-variance decomposition (2) with sample size n.

When the goal is estimation and the signal-to-noise ratio (SNR) is large, the smaller bias usually is the better, which is obtained by taking n t ∼ n.

Otherwise, CV can be asymptotically suboptimal. Nevertheless, when the goal is estimation and the SNR is small, keeping a small upward bias for the variance term often improves the performance, which is obtained by taking n t ∼ κn with κ ∈ (0, 1). See Section 6. When the goal is identification, a large bias is often needed, which is obtained by taking n t ≪ n; depending on the framework, larger values of n t can also lead to model consistency, see Section 7.

• Variability: The variance of the CV estimator of the risk is usually a decreasing function of the number B of splits, for a fixed training size.

When the number of splits is fixed, the variability of CV also depends on the training sample size n t . Usually, CV is more variable when n t is closer to n. However, when B is linked with n t (as for VFCV or LPO), the variability of CV must be quantified precisely, which has been done in few frameworks. The only general conclusion on this point is that the CV method with minimal variability seems strongly framework-dependent, see Section 5.2 for details.

• Computational complexity: Unless closed-form formulas or analytic approximations are available (see Section 9), the complexity of CV is roughly proportional to the number of data splits: 1 for the hold-out, V for VFCV, B for RLT or MCCV, n for LOO, and n p for LPO. The optimal trade-off between these three factors can be different for each problem, depending for instance on the computational complexity of each estimator, on specificities of the framework considered, and on the final user's trade-off between statistical performance and computational cost. Therefore, no "optimal CV method" can be pointed out before having taken into account the final user's preferences.