Cross-validation variance explained with optimal k fold choice
A Theory of Cross-Validation Variance
Machine Learning
Summary
Cross-validation is a common way to estimate how good a model is by splitting data into parts for training and testing. The paper explains how each data point affects the accuracy estimate in two ways: when it is used to test the model and when it helps train the model. They prove a precise formula for how much the estimate can vary because of the way data is split. This shows that K-fold cross-validation, especially leave-one-out, is the best way to minimize this variation. Their results help people decide which cross-validation method to use for more reliable model performance assessment.
What this means in practice
- •For machine learning engineers: Choose cross-validation schemes with minimal variance to get more reliable model performance estimates in practice.
- •For medical data teams: Use leave-pair-out cross-validation to efficiently assess diagnostic tests by accurately estimating AUC performance.
A theory result. No direct application yet.
Authors
Nathaniel S. O'Connell, Jaime L. Speiser
Abstract
Cross-validation estimates predictive performance by repeatedly splitting the data into training and validation sets, fitting the model on the first and evaluating it on the second. Every observation influences the estimate in two roles, through its own evaluation when it is held out and through the models it helps fit when it trains. The random splits determine its weight in each role. From this representation, we prove an exact finite-sample identity for the variance of the cross-validated estimate. For a given splitting scheme with a common training set size, the variance is a function of these weights, with constants of the model, the metric, and the population. It covers metrics averaged over observations, such as mean squared error, and over case--control pairs, such as the AUC. The identity shows which schemes to use. The variance decomposes into sampling variance, which depends only on the training size, and variance due to the random fold splitting, which arises when the weights change from one draw of the splits to the next. K-fold cross-validation, whose weights are equal across observations by design, is therefore variance optimal at first order; Monte Carlo and bootstrap cross-validation are not. The first-order variance of K-fold does not depend on K, and under reasonable conditions on the model leave-one-out has the smallest variance of any K-fold scheme. For the AUC the same holds for leave-pair-out, which evaluates every case--control pair. Finally, we show the cross-validated estimate is asymptotically normal with the identity's full variance. Together, these results provide a general theoretical foundation for inference on cross-validated performance and establish principles for selecting variance-optimal cross-validation designs.