CoChat
Sign Up
Cited by 409Machine Learning and AlgorithmsMachine Learning and Data ClassificationStochastic Gradient Optimization Techniques

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

Kearns, Michael, Ron, Dana·1999·Neural Computation
DOI 10.1162/089976699300016304
Open this paper in CoChat — free account

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

Crossref · 10.1162/089976699300016304

Cites

18 of 18 references verified0 citation errors · 0 not checkable

Statistics

Recomputing p-values needs the paper’s full text.

Verification

Claims the paper makes

This paper’s full text isn’t openly available, so its claims and self-check weren’t run. The registry and citation checks still apply.

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?

Citations

Cites

Show all 18 references

Cited by

Sorted by citations

Items 401–409 of 409

Related

See all

Metadata

Authors
Kearns, M., & Ron, D.
Affiliations
  • AT&T (United States) (US)
  • Tel Aviv University (IL)
ORCID
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
DOI
10.1162/089976699300016304
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