A survey of cross-validation procedures for model selection

May combine two claims.

Since n_t < n, the bias of CV is usually nonnegative and tends to decrease when n_t increases, when the risk of A(D_n) is a decreasing function of n (A is a smart rule).

“Since n t < n , the bias of CV is usually nonnegative and tends to decrease when n t increases.This holds true when the risk of A(D n ) is a decreasing function of n , that is, when A is a smart rule.”

May combine two claims.

Assuming n_t is fixed, the first term of hold-out variance is proportional to 1/n_v; therefore more data for validation decreases the variance of L_HO.

“Assuming n t is fixed, the first term is proportional to 1/n v .Therefore, more data for validation decreases the variance of L HO , because it yields a better estimator of L P (A(D”

• AssumptionThe authors state this as an assumption: n_t is fixed when analyzing hold-out variance.

May combine two claims.

With training sets of the same size n_t, CV estimators have the same bias, but still behave differently; their variance captures most of the information to explain these differences.

“With training sets of the same size n t , CV estimators have the same bias, but still behave differently.Their variance var( L CV (A; D n ; (I”

May combine two claims.

The variance of L_HO also depends on the distribution of L_P(A(D_n^t)) around its expectation; in particular, it strongly depends on the stability of A.

“Both terms show that the variance of L HO 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 .”

May combine two claims.

The variability due to the choice of the data splits is maximal for hold-out, and minimal (null) for exhaustive splitting schemes like LOO and LPO.

“The variability due to the choice of the data splits is maximal for hold-out, and minimal (null) for exhaustive splitting schemes like LOO (if n t = n -1) and LPO (with p = n -n t ).”

May combine two claims.

The variance of CV strongly depends on the framework and on the stability of A; therefore radically different results have been obtained in different frameworks, in particular on the value of V for which the VFCV estimator has a minimal variance.

“Furthermore, the variance of CV strongly depends on the framework and on the stability of A .Therefore, radically different results have been obtained in different frameworks, in particular on the value of V for which the VFCV estimator has a minimal variance (Burman, 1989;Hastie et al., 2009, Section 7.10).”

• cites Burman, 1989Not checked yet

  Not checked in the free run.

• cites Hastie et al., 2009Not checked yet

  Not checked in the free run.

Probably not a substantial claim: may not pass S3 (load-bearing).

The dependence of var(L_VF(A)) on V is more complex to evaluate, since B, n_t, and n_v simultaneously vary with V.

“Note that the dependence of var( L VF (A)) on V is more complex to evaluate, since B , n t , and n v simultaneously vary with V .”

May combine two claims.

Closed-form formulas for CV estimators of the risk can be obtained in several frameworks, which greatly decreases the computational cost of CV.

“Nevertheless, closed-form formulas for CV estimators of the risk can be obtained in several frameworks, which greatly decreases the computational cost of CV.”

Classified as probably not a substantial claim.

The naive implementation of CV with B data splits has a computational complexity of B times that of training each algorithm A.

“The naive implementation of CV with B data splits has a computational complexity of B times that of training each algorithm A .”

Probably not a substantial claim: may not pass S3 (load-bearing).

When a true model exists, model consistency is a stronger property than efficiency.

“When a true model exists, model consistency is clearly a stronger property than efficiency defined in Section 2.2.”

Probably not a substantial claim: may not pass S3 (load-bearing).

A good model choice reaches the best trade-off between the approximation error and the estimation error, often called the bias-variance trade-off.

“More generally according to (2), a good model choice reaches the best trade-off between the approximation error ℓ ( s, S m ) and the estimation error α n D m , which is often called the bias-variance trade-off”

Probably not a substantial claim: may not pass S3 (load-bearing).

Oracle inequalities with leading constant C_n = 1 have been derived for aggregation with exponential weights.

“Oracle inequalities with leading constant C n = 1 have been derived for instance for aggregation with exponential weights (Lecué, 2006).”

• cites Lecué, 2006Not checked yet

  Not checked in the free run.

Probably not a substantial claim: may not pass S3 (load-bearing), S4 (based). May combine two claims.

In many frameworks, no true model exists, so efficiency is the only well-defined property.

“However, in many frameworks, no true model does exist so that efficiency is the only well-defined property.”

May combine two claims.

The main drawback of penalties such as AIC or Cp is their asymptotic nature, for AIC, or their dependence on assumptions on the distribution of data: Cp assumes the variance of Y does not depend on X; otherwise it has suboptimal performance.

“The main drawback of penalties such as AIC or C p is their asymptotic nature (for AIC) or their dependence on some assumptions on the distribution of data: C p assumes the variance of Y does not depend on X .Otherwise, it has a suboptimal performance (Arlot, 2008a).”

• cites Arlot, 2008aNot checked yet

  Not checked in the free run.

May combine two claims.

The major interest of cross-validation lies in the universality of the data splitting heuristics; it only assumes that data are identically distributed and that training and validation samples are independent, which can even be relaxed.

“The major interest of CV lies in the universality of the data splitting heuristics.It only assumes that data are identically distributed, and training and validation samples are independent, which can even be relaxed (see Section 8.1).”

Probably not a substantial claim: may not pass S4 (based). May combine two claims.

The family of cross-validation procedures contains procedures in the categories of Sections 3.1, 3.2.1 and 3.2.2: they all satisfy (7) with different values of κ_n.

“The family of CV procedures, which will be described and deeply investigated in the next sections, contains procedures in the categories of Sections 3.1, 3.2.1 and 3.2.2:they all satisfy (7) with different values of κ n .”

May combine two claims.

The universality of cross-validation is not shared by most other model selection procedures, which often are specific of a framework and can be completely misleading in another one.

“This universality is not shared by most other model selection procedures (see Section 3), which often are specific of a framework and can be completely misleading in another one.”

May combine two claims.

Burman proposed a corrected VFCV estimator and a similar correction holds for RLT; both estimators have been proved asymptotically unbiased for least squares in linear regression.

“Both estimators have been proved to be asymptotically unbiased for least squares in linear regression.”

• cites Burman, 1989Not checked yet

  Not checked in the free run.

• cites Burman, 1990Not checked yet

  Not checked in the free run.

May combine two claims.

GCV is closer to C_L than to CV, since GCV can be seen as an approximation to C_L with a particular estimator of variance.

“GCV is actually closer to C L (i.e., C p generalized to linear estimators; Mallows, 1973) than to CV, since GCV can be seen as an approximation to C L with a particular estimator of variance (Efron, 1986).”

• cites Efron, 1986Not checked yet

  Not checked in the free run.

May combine two claims.

The computational cost of V-fold cross-validation is only V times that of training A with n - n/V points; it is much less than leave-one-out or leave-p-out if V ≪ n.

“The computational cost of VFCV is only V times that of training A with n -n/V points; it is much less than LOO or LPO if V ≪ n .”

Probably not a substantial claim: may not pass S3 (load-bearing).

V-fold CV relies on a similar idea to Balanced Incomplete CV, since the set of training sample indices used by V-fold CV satisfies the first property and almost satisfies the second one.

“Note that VFCV relies on a similar idea, since the set of training sample indices used by VFCV satisfies the first property and almost satisfies the second one.”

Probably not a substantial claim: may not pass S3 (load-bearing). May combine two claims.

Monte-Carlo CV is very close to repeated learning-testing; unlike repeated learning-testing, Monte-Carlo CV allows the same split to be chosen several times.

“Monte-Carlo CV (MCCV, Picard and Cook, 1984) is very close to RLT.Unlike RLT, MCCV allows the same split to be chosen several times.”

• cites Picard and Cook, 1984Not checked yet

  Not checked in the free run.

Probably not a substantial claim: may not pass S3 (load-bearing). May combine two claims.

Repeated learning-testing can be seen as an approximation to leave-p-out with p = n - n_t, with which it coincides when B = n_p.

“RLT can be seen as an approximation to LPO with p = n -n t , with which it coincides when B = n p .”

May combine two claims.

LOO bootstrap and .632 bootstrap have nearly no theoretical justification and only empirical studies have supported the good behaviour of .632+bootstrap.

“However, these procedures have nearly no theoretical justification and only empirical studies have supported the good behaviour of .632+bootstrap (Efron and Tibshirani, 1997;Molinaro et al., 2005).”

• cites Efron and Tibshirani, 1997Not checked yet

  Not checked in the free run.

• cites Molinaro et al., 2005Not checked yet

  Not checked in the free run.

May combine two claims.

When A is unstable, L_LOO(A) has often been pointed out as a variable estimator; conversely, from a simulation experiment, this trend disappears when A is stable.

“When A is unstable, L LOO ( A ) has often been pointed out as a variable estimator (Section 7.10, Hastie et al., 2009;Breiman, 1996).Conversely, Molinaro et al. (2005) noticed, from a simulation experiment, that this trend disappears when A is stable.”

• cites Hastie et al., 2009Not checked yet

  Not checked in the free run.

• cites Breiman, 1996Not checked yet

  Not checked in the free run.

• cites Molinaro et al., 2005Not checked yet

  Not checked in the free run.

May combine two claims.

The best CV estimator of the risk is not necessarily the best model selection procedure; according to Breiman and Spector (1992), the best risk estimator is LOO, whereas 10-fold CV is more accurate for model selection.

“Nevertheless, the best CV estimator of the risk is not necessarily the best model selection procedure.According to Breiman and Spector (1992) the best risk estimator is LOO, whereas 10-fold CV is more accurate for model selection.”

• cites Breiman and Spector, 1992Not checked yet

  Not checked in the free run.

May combine two claims.

When n_t ∼ λn with λ ∈ (0,1), CV is asymptotically equivalent to GIC_κ with κ = 1 + λ^-1, which is defined as C_p with a penalty multiplied by κ/2; such CV procedures are overpenalizing by a factor (1 + λ)/(2λ) > 1.

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

May combine two claims.

When n_t ∼ n, CV is asymptotically equivalent to Mallows' C_p, hence asymptotically optimal.

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

May combine two claims.

Section 6.2 suggests the suboptimality of CV when n_t is not asymptotically equivalent to n, which has been settled with regressograms for VFCV when V = O(1).

“First, Section 6.2 suggests the suboptimality of CV when n t is not asymptotically equivalent to n , which has been settled with regressograms by Arlot (2008b) for VFCV when V = O(1) .”

• cites Arlot, 2008bNot checked yet

  Not checked in the free run.

May combine two claims.

CV procedures asymptotically behave like GIC_λn with λ_n = 1 + n/n_t, which leads to inconsistency if n/n_t = O(1).

“More generally, Shao (1997) proved that CV procedures asymptotically behave like GIC λn with λ n = 1 + n/n t , which leads to inconsistency if n/n t = O(1) .”

• cites Shao, 1997Not checked yet

  Not checked in the free run.

May combine two claims.

Several CV methods are inconsistent for variable selection in linear regression: LOO, LPO, and BICV when lim inf n→∞ (n_t/n) > 0. These CV methods asymptotically select all the true variables, but the probability that they select too many variables does not tend to zero.

“Shao (1993), who 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 .These CV methods asymptotically select all the true variables, but the probability that they select too many variables does not tend to zero.”

• cites Shao, 1993Not checked yet

  Not checked in the free run.

Probably not a substantial claim: may not pass S3 (load-bearing). May combine two claims.

n-fold penalization is very close to LOO, suggesting that LOO is also asymptotically optimal with heteroscedastic data.

“Note that n-fold penalization is very close to LOO, suggesting that LOO is also asymptotically optimal with heteroscedastic data.”

Probably not a substantial claim: may not pass S3 (load-bearing).

Closed-form formulas for the leave-p-out (LPO) estimator are given by Celisse (2008b) in regression for kernel and projection estimators.

“Closed-form formulas for the LPO estimator are also given by Celisse (2008b) in regression for kernel and projection estimators.”

• cites Celisse (2008b)Not checked yet

  Not checked in the free run.

May combine two claims.

The unbiased risk estimation principle is known to fail when the number of models grows exponentially with n; therefore the analysis of Section 6 is no longer valid, and n_t must be carefully chosen for avoiding overfitting.

“The unbiased risk estimation principle (see Section 3.1) is known to fail when the number of models grows exponentially with n (Birgé and Massart, 2007).Therefore, the analysis of Section 6 is no longer valid, and n t must be carefully chosen for avoiding overfitting”

• cites Birgé and Massart, 2007Not checked yet

  Not checked in the free run.

May combine two claims.

(15) is implied by n_t/n_v = O(1), when max_i r_n,i ≫ n^-1/2; it even allows n_t ∼ n (under some conditions). Therefore non-parametric algorithms can be compared by more usual CV procedures (n_t > n/2), even if LOO is still excluded by conditions (15).

“On the other hand, ( 15) is implied by n t /n v = O(1) , when max i r n,i ≫ n -1/2 .It even allows n t ∼ n (under some conditions).Therefore, non-parametric algorithms can be compared by more usual CV procedures (n t > n/2), even if LOO is still excluded by conditions (15).”

May combine two claims.

When data are dependent, all previous analyses break down since the validation and training samples are no longer independent; therefore CV must be modified.

“When data are dependent, all previous analyses break down since the validation and training samples are no longer independent.Therefore, CV must be modified.”

May combine two claims.

If max_i r_n,i ∝ n^-1/2, then (15) holds when n_v ≫ n_t → ∞; therefore the cross-validation paradox holds for comparing algorithms converging at the parametric rate.

“On the one hand, if max i r n,i ∝ n -1/2 , then (15) holds when n v ≫ n t → ∞ .Therefore, the cross-validation paradox holds for comparing algorithms converging at the parametric rate”

The quote only partly states this claim.

When the goal is estimation and the SNR is not large, CV can be asymptotically suboptimal.

“Otherwise, CV can be asymptotically suboptimal.”

May combine two claims.

In density estimation, closed-form expressions of the LPO estimator have been derived by Celisse and Robin (2008) with histograms and kernel estimators, and by Celisse (2008a) for projection estimators.

“Nevertheless, in density estimation, closed-form expressions of the LPO estimator have been derived by Celisse and Robin (2008) with histograms and kernel estimators, and by Celisse (2008a) for projection estimators.”

• cites Celisse and Robin (2008)Not checked yet

  Not checked in the free run.

• cites Celisse (2008a)Not checked yet

  Not checked in the free run.

May combine two claims.

Dynamic programming can be used to minimize L_CV over all partitions of X with a given number of pieces, a strategy applied by Arlot and Celisse (2009) for change-point detection.

“Therefore, dynamic programming (Bellman and Dreyfus, 1962) can be used for minimizing L CV over the set of all partitions of X with a given number of pieces, a strategy successfully applied by Arlot and Celisse (2009) for change-point detection.”

• cites Bellman and Dreyfus, 1962Not checked yet

  Not checked in the free run.

• cites Arlot and Celisse (2009)Not checked yet

  Not checked in the free run.

Probably not a substantial claim: may not pass S3 (load-bearing).

Similar updating formulas are available for leave-one-out and the k-nearest neighbours algorithm in classification.

“Note that very similar formulas are also available for LOO and the k-nearest neighbours algorithm in classification (Daudin and Mary-Huard, 2008).”

• cites Daudin and Mary-Huard, 2008Not checked yet

  Not checked in the free run.

Probably not a substantial claim: may not pass S3 (load-bearing), S4 (based). May combine two claims.

Otherwise, the computational complexity of CV is roughly proportional to the number of data splits: 1 for hold-out, V for VFCV, B for RLT or MCCV, n for LOO, and n^p for LPO.

“Otherwise, the computational complexity of CV is roughly proportional to the number of data splits: 1 for hold-out, V for VFCV, B for RLT or MCCV, n for LOO, and n p for LPO.”

May combine two claims.

When B is fixed, the variance of CV depends on n_t; usually CV is more variable when n_t is closer to n.

“When B is fixed, the variance of CV also depends on n t : Usually, CV is more variable when n t is closer to n .”

Probably not a substantial claim: may not pass S3 (load-bearing). May combine two claims.

Shao (1993) proposed a CV method called BICV, where every point and pair of points appear in the same number of splits.

“Similarly, Shao (1993) 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.”

• cites Shao (1993)Not checked yet

  Not checked in the free run.

Probably not a substantial claim: may not pass S3 (load-bearing).

With regressograms, Arlot (2008b) and Arlot and Celisse (2009) chose the splitting scheme carefully.

“With regressograms, this led Arlot (2008b) and Arlot and Celisse (2009) to choose carefully the splitting scheme.”

• cites Arlot (2008b)Not checked yet

  Not checked in the free run.

• cites Arlot and Celisse (2009)Not checked yet

  Not checked in the free run.

May combine two claims.

Most recent theoretical results on CV procedures are not accurate enough to distinguish which splitting strategy is best; this remains a widely open theoretical question.

“Nevertheless, most recent theoretical results on the various CV procedures are not accurate enough to distinguish which splitting strategy is the best: This remains a widely open theoretical question.”

May combine two claims.

Breiman and Spector (1992) compared several splitting strategies by simulations in regression and reported no significant improvement from taking into account stratification of data.

“Nevertheless, Breiman and Spector (1992) compared several splitting strategies by simulations in regression.No significant improvement was reported from taking into account stratification of data.”

• cites Breiman and Spector (1992)Not checked yet

  Not checked in the free run.

May combine two claims.

These closed-form expressions allow LPO to be performed without additional computational cost, reducing the trade-off to balancing bias and variance.

“These expressions allow to perform LPO without additional computational cost, which reduces the aforementioned trade-off to balancing bias and variance.”

Probably not a substantial claim: may not pass S3 (load-bearing). May combine two claims.

The additional variability due to the choice of a sequence of data splits was quantified empirically by Jonathan et al. (2000) and theoretically by Celisse and Robin (2008) for VFCV.

“Note finally that the additional variability due to the choice of a sequence of data splits was quantified empirically by Jonathan et al. (2000) and theoretically by Celisse and Robin (2008) for VFCV.”

• cites Jonathan et al. (2000)Not checked yet

  Not checked in the free run.

• cites Celisse and Robin (2008)Not checked yet

  Not checked in the free run.

May combine two claims.

The variance of VFCV decreases with V for small values of V, whereas LOO (V = n) is known to suffer from high variance in several frameworks such as classification or density estimation.

“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.”

Probably not a substantial claim: may not pass S3 (load-bearing). May combine two claims.

V-fold penalization is another possible alternative to VFCV, related to corrected VFCV.

“Another possible alternative is V -fold penalization, which is related to corrected VFCV (see Section 4.3.3).”

Probably not a substantial claim: may not pass S3 (load-bearing). May combine two claims.

VFCV is the most popular CV procedure, in particular because of its mild computational cost.

“VFCV is certainly the most popular CV procedure, in particular because of its mild computational cost.”

Probably not a substantial claim: may not pass S3 (load-bearing). May combine two claims.

The question of choosing V remains widely open, although indications can be given towards an appropriate choice.

“Nevertheless, the question of choosing V remains widely open, even if indications can be given towards an appropriate choice.”

Probably not a substantial claim: may not pass S3 (load-bearing).

For VFCV (and exhaustive strategies), choosing V uniquely determines the training set size n_t = n(V-1)/V and the number of splits B = V, hence the computational cost.

“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.”

Probably not a substantial claim: may not pass S3 (load-bearing).

Dietterich (1998) and Alpaydin (1999) recommend V = 2 for choosing the best among two learning procedures.

“However, Dietterich (1998) and Alpaydin (1999) recommend V = 2 for choosing the best among two learning procedures.”

• cites Dietterich (1998)Not checked yet

  Not checked in the free run.

• cites Alpaydin (1999)Not checked yet

  Not checked in the free run.

Probably not a substantial claim: may not pass S3 (load-bearing), S4 (based).

Estimating the variance of VFCV is a difficult task in general.

“Moreover, estimating the variance of VFCV is a difficult task in general (Section 5.2.3).”

May combine two claims.

Compared to procedures designed to be optimal in a specific framework like AIC, CV can have less accurate model selection performances and higher computational cost.

“Nevertheless, universality has a price: Compared to procedures designed to be optimal in a specific framework (like AIC), the model selection performances of CV can be less accurate, while its computational cost is higher.”

Probably not a substantial claim: may not pass S3 (load-bearing).

The claim that the optimal V is between 5 and 10 for estimation is true for many problems.

“Even if this claim is true for many problems, this survey concludes that better statistical performance can sometimes be obtained with other values of V , for instance depending on the SNR value.”

• cites Hastie et al., 2009, Section 7.10Not checked yet

  Not checked in the free run.

Probably not a substantial claim: may not pass S3 (load-bearing).

Different empirical recommendations for choosing V can be found depending on the framework.

“Depending on the frameworks, different (empirical) recommandations for choosing V can be found.”

Probably not a substantial claim: may not pass S3 (load-bearing). May combine two claims.

In ordered variable selection, the largest V seems better, with V = 10 providing results close to optimal.

“In ordered variable selection, the largest V seems to be the better, V = 10 providing results close to the optimal ones (Zhang, 1993).”

• cites Zhang, 1993Not checked yet

  Not checked in the free run.

May combine two claims.

When the SNR is large, LOO performs nearly unbiased risk estimation and is asymptotically optimal, whereas VFCV with V = O(1) is suboptimal.

“When the SNR is large, the asymptotic comparison of CV procedures 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.”

May combine two claims.

When the goal is identification, the main drawback of VFCV is that n_t ≪ n is often required for model consistency, whereas VFCV does not allow n_t < n/2.

“When the goal of model selection is identification, the main drawback of VFCV is that n t ≪ n is often required for model consistency (Section 7), whereas VFCV does not allow n t < n/2 .”

Probably not a substantial claim: may not pass S3 (load-bearing), S4 (based).

The resampling heuristics on which resampling-based penalties rely are almost as universal as the CV heuristics.

“The resampling heuristics on which they rely is almost as universal as the CV heuristics.”

Probably not a substantial claim: may not pass S4 (based). May combine two claims.

Second-order terms matter for realistic values of n, showing the need for theory to take into account the variance of CV when comparing procedures such as VFCV and RLT with n_t = n(V-1)/V but B = V.

“However, second order terms do matter for realistic values of n , which shows the dramatic need for theory to take into account the variance of CV when comparing CV procedures such as VFCV and RLT with n t = n(V -1)/V but B = V .”

Probably not a substantial claim: may not pass S3 (load-bearing).

The main drawback of resampling-based penalties compared to CV may only be that fewer theoretical studies exist about their model selection performances.

“The main drawback of resampling-based penalties, compared to CV, may only be that fewer theoretical studies exist about their model selection performances.”

May combine two claims.

Most theoretical results are not precise enough to distinguish between hold-out and CV procedures with the same training sample size n_t; they are all equivalent at first order.

“More generally, most theoretical results are not precise enough to make real distinction between hold-out and CV procedures having the same training sample size n t : They are all equivalent at first order.”

Classified as probably not a substantial claim.

Up to now, only a few precise results on the variance of CV estimators have been obtained, for some specific CV methods in linear regression or density estimation.

“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).”

May combine two claims.

When data are not homoscedastic, C_p is no longer efficient and can strongly overfit.

“Otherwise, C p is no longer efficient and can strongly overfit (Arlot, 2008a).”

• cites Arlot, 2008aNot checked yet

  Not checked in the free run.