Beating the hold-out: bounds for K-fold and progressive cross-validation

By Avrim Blum, Adam Tauman Kalai, J. Langford. 1999

The empirical error on a test set, the hold-out estimate, often is a more reliable estimate of generalization error than the observed error on the training set, the training estimate. K-fold cross validation is used in practice with the hope of being more accurate than the hold-out estimate without reducing the number of training examples. We argue that the k-fold estimate does in fact achieve this goal. Specifically, we show that for any nontrivial learning problem and learning algorithm that is insensitive to example ordering, the k-fold estimate is strictly more accurate than a single hold-out estimate on 1/k of the data, for 2 < k < n (k = n is leave-one-out), based on its variance and all higher moments. Previous bounds were termed sanitycheck because they compared the k-fold estimate to the training estimate and, further, restricted the VC dimension and required a notion of hypothesis stability [2]. In order to avoid these dependencies, we consider a k-fold hypothesis that is a randomized combination or average of the k individual hypotheses. We introduce progressive validationas another possible improvement on the hold-out estimate. This estimate of the generalization error is, in many ways, as good as that of a single hold-out, but it uses an average of half as many examples for testing. The procedure also involves a hold-out set, but after an example has been tested, it is added to the training set and the learning algorithm is rerun.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits (2014, methodology): “Our evaluation criteria is progressive validation (Blum et al., 1999) on 0/1 loss.”
Ad click prediction: a view from the trenches (2013, methodology): “We generally use progressive validation (sometimes called online loss) [5] rather than cross-validation or evaluation on a held out dataset.”
Test of lepton universality with B0 → K*0ℓ+ℓ− decays (2017, methodology): “To best exploit the size of the available data sample for the training procedure, a k-folding technique [49]”
Making Contextual Decisions with Low Technical Debt (2016, methodology): “This simulation is imperfect because training occurs on fewer events and because the policy evaluated on the test set is not adaptive. When training on the train set progressive validation techniques [13] allow an unbiased estimate of policy value deployed with zero delay. When evaluating the ﬁnal t”
On the generalization ability of on-line learning algorithms (2001, background): “As a remark, we note that a version of Corollary 2 restricted to the absolute loss was given in [33].”
A Contextual Bandit Bake-off (2018, unknown): “The performance of method A on a dataset of size n is measured by the progressive validation loss (Blum et al., 1999): where a t is the action chosen by the algorithm on the t -th example, and c t the true cost vector.”
Batch learning from logged bandit feedback through counterfactual risk minimization (2015, methodology): “We use mini-batch AdaGrad (Duchi et al., 2011) with batch size = 100 and step size η = 1 to adapt our learning rates for the stochastic approaches and use progressive validation (Blum et al., 1999) and gradient norms to detect convergence.”
Large-Scale Learning with Less RAM via Randomization (2013, methodology): “Metrics are computed using progressive validation (Blum et al., 1999) as is standard for online learning: on each round a prediction is made for a given example and record for evaluation, and only after that is the model allowed to train on the example.”
Tutorial on Practical Prediction Theory for Classification (2005, result): “Only weak general results in this model are known for some variants of cross validation (see Blum et al., 1999).”
Cross-validation: what does it estimate and how well does it do it? (2021, background): “The enduring popularity of CV is due to the fact that it is a conceptually simple improvement over a one-time train-test split (Blum, Kalai, and Langford 1999).”
Generalization Bounds for Uniformly Stable Algorithms (2018, methodology): “In a somewhat similar spirit, stability is also used for analysis of the variance of the k-fold cross-validation estimator [3, 16, 17].”
Learning interpretable classification rules using sequential rowsampling (2015, background): “In related work, the learning curve literature in machine learn ing [2] [3] [4] [5] has considered how the generalization error evolves as a function of the received number of samples.”
Contextual Memory Trees (2018, methodology): “Since CMT operates online, we can evaluate its online performance using progressive validation (Blum et al., 1999) (i.e., testing each example ahead of training).”
IEEE TRANSACTIONS ON INFORMATION THEORY , VOL . ? , NO . ? , ? 200 ? 1 Improved Risk Tail Bounds for On-Line Algorithms (2007, unknown): “If the convexity assumptions do not hold (as in the case of classification problems), then the bound in (4) applies to a random hypothesis in the ensemble (this was investigated in [3] though with different goals).”
Counterfactual Risk Minimization (2015, background): “= 100 to adapt our learning rates for the stochastic approaches and use progressive validation (Blum et al., 1999) and gradient norms to detect convergence.”