The DOI matches its Crossref record; 18 of the 18 references it cites were found in a registry or an index.
Algorithmic Stability and Sanity-Check Bounds for Leave-One-Out Cross-Validation
Abstract
In this article we prove sanity-check bounds for the error of the leave-oneout cross-validation estimate of the generalization error: that is, bounds showing that the worst-case error of this estimate is not much worse than that of the training error estimate. The name sanity check refers to the fact that although we often expect the leave-one-out estimate to perform considerably better than the training error estimate, we are here only seeking assurance that its performance will not be considerably worse. Perhaps surprisingly, such assurance has been given only for limited cases in the prior literature on cross-validation. Any nontrivial bound on the error of leave-one-out must rely on some notion of algorithmic stability. Previous bounds relied on the rather strong notion of hypothesis stability, whose application was primarily limited to nearest-neighbor and other local algorithms. Here we introduce the new and weaker notion of error stability and apply it to obtain sanity-check bounds for leave-one-out for other classes of learning algorithms, including training error minimization procedures and Bayesian algorithms. We also provide lower bounds demonstrating the necessity of some form of error stability for proving bounds on the error of the leave-one-out estimate, and the fact that for training error minimization algorithms, in the worst case such bounds must still depend on the Vapnik-Chervonenkis dimension of the hypothesis class.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
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?
In the citing paper
“For unbiased performance estimation of both classifiers, leave-one-out cross validation was conducted [51].”
From Mobile Sensing and Support for People With Depression: A Pilot Trial in the Wild (2016) · cites this paper as [51]
Citations
Cites
Stochastic relaxation, gibbs distributions, and the bayesian restoration of images.
Geman, S., & Geman, D. (1984) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.1984.4767596 · Cited by 17,949
(1973) · CERN Document Server (European Organization for Nuclear Research) · Cited by 12,895
A Study of Cross-Validation and Bootstrap for Accuracy Estimation and Model Selection
Kohavi, R. (1995) · Zenodo · doi:10.5281/zenodo.19712698 · Cited by 10,909
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
Estimation of Dependences Based on Empirical Data
Vapnik, V. N. (2006) · Information science and statistics · doi:10.1007/0-387-34239-7 · Cited by 2,252
Subset Selection in Regression
Miller, A. J. (2003) · Technometrics · doi:10.1198/tech.2003.s144 · Cited by 1,501
Decision theoretic generalizations of the PAC model for neural net and other learning applications
Haussler, D. H. (1992) · Information and Computation · doi:10.1016/0890-5401(92)90010-d · Cited by 845
Subset Selection in Regression.
RAAB, G. M., & Miller, T. (1991) · Biometrics · doi:10.2307/2532418 · Cited by 547
Statistical mechanics of learning from examples
Seung, H. S., Sompolinsky, H., & Tishby, N. (1992) · Physical Review A · doi:10.1103/physreva.45.6056 · Cited by 532
Toward efficient agnostic learning
Kearns, M. J., Schapire, R. E., & Sellie, L. M. (1992) · Conference on Learning Theory · doi:10.1145/130385.130424 · Cited by 353
Self-citationDistribution-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 237
Toward Efficient Agnostic Learning
Kearns, M. J., Schapire, R. E., & Sellie, L. M. (1994) · Machine Learning · doi:10.1007/bf00993468 · Cited by 172
Self-citationAn experimental and theoretical comparison of model selection methods
Kearns, M. J., Mansour, Y., Ng, A. Y., & Ron, D. (1995) · Conference on Learning Theory · doi:10.1145/225298.225301 · Cited by 167
Self-citationA Finite Sample Distribution-Free Performance Bound for Local Discrimination Rules
Rogers, W. H., & Wagner, T. J. (1978) · The Annals of Statistics · doi:10.1214/aos/1176344196 · Cited by 135
Distribution-free inequalities for the deleted and holdout error estimates
Devroye, L., & Wagner, T. J. (1979) · IEEE Transactions on Information Theory · doi:10.1109/tit.1979.1056032 · Cited by 120
Rigorous learning curve bounds from statistical mechanics
Haussler, D. H., Seung, H. S., Kearns, M. J., & Tishby, N. (1994) · Conference on Learning Theory · doi:10.1145/180139.181018 · Cited by 96
Self-citationPAC-like upper bounds for the sample complexity of leave-one-out cross-validation
Holden, S. B. (1996) · Annual Conference on Computational Learning Theory (COLT) · doi:10.1145/238061.238067 · Cited by 19
Rigorous Learning Curve Bounds from Statistical Mechanics
Haussler, D. H., Kearns, M. J., Seung, H. S., & Tishby, N. (1996) · Machine Learning · doi:10.1023/a:1026499208981 · Cited by 19
Self-citation
Cited by
Sorted by citations
A survey of cross-validation procedures for model selectionPreprint
Arlot, S., & Célisse, A. (2009) · Cited by 3,627
A survey of cross-validation procedures for model selection
Arlot, S., & Celisse, A. (2010) · Statistics Surveys · doi:10.1214/09-ss054 · Cited by 3,522
Huang, L., Joseph, A. D., Nelson, B., Rubinstein, B. I. P., & Tygar, J. D. (2011) · Proceedings of the 4th ACM workshop on Security and artificial intelligence · doi:10.1145/2046684.2046692 · Cited by 1,194
Kasiviswanathan, S. P., Lee, H. K., Nissim, K., Raskhodnikova, S., & Smith, A. (2011) · SIAM Journal on Computing · doi:10.1137/090756090 · Cited by 898
No Unbiased Estimator of the Variance of K-Fold Cross-ValidationPreprint
Bengio, Y., & Grandvalet, Y. (2003) · RePEc: Research Papers in Economics · Cited by 886
Metadata
- Authors
- Kearns, M., & Ron, D.
- Affiliations
- AT&T (United States) (US)
- Tel Aviv University (IL)
- Venue
- Neural Computation
- Publisher
- MIT Press - Journals
- Published
- 1999-08-01
- Volume
- 11
- Issue
- 6
- Pages
- 1427-1453
- ISSN
- 0899-7667 (ISSN-L)
- 1530-888X
- OpenAlex
- W2138263042
- Cited by
- 407
- References
- 18
- Citations by year
- 2026: 4 · 2025: 7 · 2024: 11 · 2023: 18 · 2022: 22 · 2021: 26 · 2020: 35 · 2019: 46 · 2018: 23 · 2017: 22 · 2016: 27 · 2015: 18 · 2014: 17 · 2013: 24 · 2012: 14
- FWCI
- 4.55
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- Neural Computation (publishedVersion)
- PubMed (publishedVersion)
- Funders
- National Science Foundation
- Office of Naval Research
- 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
- leave-one-out cross-validation, generalization error estimation, algorithm stability, VC dimension, lower bounds
- MeSH terms
- Algorithms, Neural Networks, Computer
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
