Source-linked AI summary
A survey of cross-validation procedures for model selection
Sylvain Arlot, Alain Celisse
TL;DR
The paper examines algorithm selection and cross-validation when the same data are used for training and selection. It surveys theoretical results on bias, variability, and oracle inequalities, while identifying conditions and splitting strategies that remain unresolved.
Problem
Algorithm selection aims to choose one algorithm from data, but reusing the same data for training creates a main difficulty.
Method
The survey relates cross-validation results to model selection theory, distinguishing positive findings and rigorous theoretical results.
Results
Cross-validation procedures differ in bias and variability: 10-fold cross-validation has nearly minimal bias uniformly, while some bootstrap procedures overpenalize model selection.
Takeaways & Limitations
The best cross-validation risk estimator need not be the best model-selection procedure, so procedure choice depends on the target task.
Takeaways & Limitations
The conclusions remain conditional because stronger conditions may be possible, and the choice of splitting strategy remains a widely open theoretical question.
Abstract
from arXiv · showhide
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.
1.2 Examples
The section introduces statistical learning, model selection, and representative prediction frameworks, then relates estimator quality to efficiency, consistency, and oracle inequalities. It emphasizes that no procedure can generally be both model-consistent and minimax rate optimal.
- Statistical algorithms: Statistical algorithms map data to estimators, whose quality is measured by their expected loss or risk.The survey defines an algorithm as a measurable mapping from data to an estimator and evaluates it through its expected loss.
- Model selection: Model selection chooses among candidate algorithms or models using the data, but reusing the same data for training and selection creates the central difficulty.The selected estimator is produced by applying the data-chosen algorithm to the same sample.
- Model-selection properties: The survey connects model-selection procedures to oracle inequalities and reports efficient procedures with multiplicative factors tending to 1.Some procedures are approximately minimax, while others satisfy oracle inequalities with C_n tending to 1.
- Model-selection properties: When a true model exists, model consistency is stronger than efficiency; when no true model exists, efficiency is the relevant well-defined property.The survey also notes that no model-selection procedure can be simultaneously model-consistent and minimax rate optimal in the regression framework.
bLCV
Cross-validation risk estimators are determined by their data-splitting schemes, trading computational cost, training-set size, and statistical behavior. The survey reviews exhaustive, partial, repeated, and related procedures, while emphasizing unresolved questions and limitations of theoretical support.
- Cross-validation procedures: All cross-validation risk estimators average validation losses over data splits, and their form is determined by the splitting scheme.The survey distinguishes averaging-before-comparison procedures and notes that split design is central to the estimator.
- Statistical properties: The survey separates positive and negative results about cross-validation model-selection performance and identifies training-set size as a key choice.It also states that choosing the training-set size remains extensively studied and that some questions, such as splitting strategy, remain open.
- Exhaustive splitting: Leave-p-out cross-validation exhaustively leaves every possible set of p observations out for validation; p = 1 gives leave-one-out cross-validation.Its exhaustive computation motivates partial-splitting alternatives.
- Partial splitting: V-fold cross-validation partitions the data into V approximately equal folds and uses each fold successively for validation.Its algorithmic complexity is only V times training on n − n/V observations, much less than leave-one-out when V ≪ n.
- Partial splitting: Repeated learning-testing and Monte-Carlo cross-validation use randomly chosen training subsets, with Monte-Carlo cross-validation allowing repeated selection of the same split.Repeated learning-testing approximates leave-p-out cross-validation for p = n − n_t.
- Related estimators: Cross-validation-like procedures address observed drawbacks through bias correction, penalties, generalized cross-validation, and bootstrap-based estimators.The survey describes generalized cross-validation as a rotation-invariant version of leave-one-out in least-squares regression and notes weak theoretical justification for .632+ bootstrap procedures.
bLCV
The survey organizes cross-validation bias results by asymptotic status and statistical framework. Across several settings, CV bias is generally nonnegative and often decreases as the validation-set size increases, while selection and splitting choices affect the estimator’s behavior.
- General behavior: CV bias is usually nonnegative because the training size n_t is smaller than n.This behavior is reported across the survey’s discussion of CV risk estimation.
- Results by framework: CV-bias results are divided into asymptotic, non-asymptotic, and empirical categories across statistical frameworks.Asymptotic analyses fix A while n grows; non-asymptotic analyses allow A to use a number of parameters growing with n.
- Regression: In regression, the bias of CV is generally positive and decreasing across several CV estimators.Non-asymptotic bias expressions are available for LPO with projection estimators, regressograms, and kernel estimators under fixed design.
- CV-calibrated algorithms: Selecting an algorithm by minimizing its CV criterion makes the resulting risk estimate biased because the algorithm was selected using the same data.The survey recommends applying CV to the full selection algorithm, a procedure called double cross-validation.
- Partial splitting and variance: When training and validation sizes are fixed, partial-splitting methods are more variable than LPO because random split selection adds variability.For hold-out and LOO, variance is respectively maximal and null when n_t=n−1; other estimators have more complex dependence on V and B.
- Stability and variance: CV-estimator variance depends strongly on algorithm stability: it is often high for unstable algorithms and tends to diminish when the algorithm is stable.Partial data splitting also adds variability compared with LPO; for MCCV, this additional variability decreases like B^-1.
bLVF(A)
The survey finds that cross-validation performance depends strongly on the validation-to-training sample-size ratio, estimator class, and objective. Its theoretical results distinguish procedures that are asymptotically efficient or model-selection consistent from settings where variance, bias, or overpenalization limits performance.
- Variance and efficiency: LOO can have minimal variance in some settings, yet it is known to suffer high variance in classification and density estimation.The variance comparison is framework-dependent: LOO is minimal in some regression settings, while other results identify high-variance behavior.
- Guidelines and open questions: CV risk estimators have non-asymptotic oracle inequalities in several frameworks, but precise finite-sample variance behavior remains an important open direction.The survey concludes with guidelines for interpreting CV and choosing among splitting strategies; stratifying splits produced no significant improvement in the reported results.
- Model-selection consistency: For model identification, consistency improves when the validation set contains a larger data proportion; CV is consistent when n ≫ n_t → ∞ under the stated procedures.This includes RLT, BICV, and LPO with p = p_n ∼ n and n − p_n → ∞.
- Comparing procedures: For comparing two learning procedures, empirical results advise V = 2 for VF CV, while consistency depends on the algorithms' convergence rates and the risk gap.Consistency holds when each estimator's uncertainty is negligible relative to the risk gap, including cases with a nonparametric convergence rate or n_t ≪ n.