Beating the hold-out: bounds for K-fold and progressive cross-validation
Open accessAbstract
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 l/k of the data, for 2 < k < n (It = 12 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 LT individual hypotheses.We introduceprogressive validation as 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.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
k-fold cross-validation is more robust to variance from random splitting of a small dataset than a single train/validate split.
“The k-fold CV setup has the advantage of being more robust to variance introduced during random splitting of a small dataset compared to a single train/validate split, since we are running k simultaneous models with identical architecture and hyper-parameters on k different train/validation splits [22,23].”
From Fully Automated Placental Volume Quantification From<scp>3D</scp>Ultrasound for Prediction of Small‐for‐Gestational‐Age Infants (2022) · cites this paper as [22]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
Breiman, L. (1996) · Machine Learning · doi:10.1007/bf00058655 · Cited by 16,325 · see citing works
Spencer, J. (1991) · Medical Entomology and Zoology · Cited by 4,370 · see citing works
A Probabilistic Theory of Pattern Recognition
Devroye, L., Györfi, L., & Lugosi, G. (1996) · Stochastic Modelling and Applied Probability · doi:10.1007/978-1-4612-0711-5 · Cited by 3,274 · see citing works
Algorithmic Stability and Sanity-Check Bounds for Leave-One-Out Cross-Validation
Kearns, M., & Ron, D. (1999) · Neural Computation · doi:10.1162/089976699300016304 · Cited by 407 · see citing works
中澤, 真. (1997) · Medical Entomology and Zoology · Cited by 352 · see citing works
Distribution-free performance bounds for potential function rules
Devroye, L., & Wagner, T. J. (1979) · IEEE Transactions on Information Theory · doi:10.1109/tit.1979.1056087 · Cited by 233 · see citing works
Algorithmic stability and sanity-check bounds for leave-one-out cross-validation
Kearns, M. J., & Ron, D. (1997) · Conference on Learning Theory · doi:10.1145/267460.267491 · Cited by 122 · see citing works
From on-line to batch learning
Littlestone, N. (1989) · Conference on Learning Theory · doi:10.5555/93335.93365 · Cited by 121 · see citing works
Helmbold, D. P., & Warmuth, M. K. (1995) · Journal of Computer and System Sciences · doi:10.1006/jcss.1995.1044 · Cited by 74 · see citing works
Cross-validation for binary classification by real-valued functions
Anthony, M., & Holden, S. B. (1998) · Conference on Learning Theory · doi:10.1145/279943.279987 · Cited by 29 · see citing works
Discussion of the paper "Arcing Classifiers" by Leo Breiman
Freund, Y., & Schapire, R. E. (1998) · Cited by 18 · see citing works
(2003) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2003.1251159 · Cited by 1 · see citing works
Flagged first, then by citations
Research works printed but not linked: 1
- Our bounds, however, are not very informative in the leave-one-out case, because we would be comparing it to a hold-out of a single element. ical Analysis In Proc. Eleventh Annual Conference on Computational Learning Theory, 1998.
Cited by
Sorted by citations
Effect of data leakage in brain MRI classification using 2D convolutional neural networks
Yagis, E., Atnafu, S. W., García Seco de Herrera, A., Marzi, C., Scheda, R., Giannelli, M., Tessa, C., Citi, L., & Diciotti, S. (2021) · Scientific Reports · doi:10.1038/s41598-021-01681-w · Cited by 161 · see citing works
Let's (not) stick together: pairwise similarity biases cross-validation in activity recognition
Hammerla, N. Y., & Plötz, T. (2015) · Proceedings of the 2015 ACM International Joint Conference on Pervasive and Ubiquitous Computing · doi:10.1145/2750858.2807551 · Cited by 91 · see citing works
Adaptive bias correction for improved subseasonal forecasting
Mouatadid, S., Orenstein, P., Flaspohler, G., Cohen, J., Oprescu, M., Fraenkel, E., & Mackey, L. (2023) · Nature Communications · doi:10.1038/s41467-023-38874-y · Cited by 54 · see citing works
Schwartz, N., Oguz, I., Wang, J., Pouch, A., Yushkevich, N., Parameshwaran, S., Gee, J., Yushkevich, P., & Oguz, B. (2022) · Journal of Ultrasound in Medicine · doi:10.1002/jum.15835 · Cited by 11 · see citing works
- Authors
- Blum, A., Kalai, A., & Langford, J.
- Affiliations
- Carnegie Mellon University (US)
- Venue
- Proceedings of the twelfth annual conference on Computational learning theory
- Publisher
- ACM
- Published
- 1999-07-06
- Pages
- 203-208
- OpenAlex
- W2009772318
- Cited by
- 265
- References
- 12
- Citations by year
- 2026: 7 · 2025: 17 · 2024: 15 · 2023: 17 · 2022: 13 · 2021: 15 · 2020: 20 · 2019: 12 · 2018: 16 · 2017: 16 · 2016: 9 · 2015: 19 · 2014: 17 · 2013: 11 · 2012: 6
- FWCI
- 1.41
- Type
- conference paper
- Language
- en
- Open access
- bronze
- doi.org
- Locations
- Conference on Learning Theory (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Machine Learning and Algorithms
- Physical Sciences › Computer Science › Artificial Intelligence › Machine Learning and Data Classification
- Physical Sciences › Computer Science › Artificial Intelligence › Stochastic Gradient Optimization Techniques
- Keywords
- k-fold cross-validation, generalization error, training error, leave-one-out cross-validation, variance bounds, VC dimension
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
