Algorithmic Stability and Sanity-Check Bounds for Leave-one-Out Cross-Validation

Michael J. Kearns, Dana RonCOLT 1997 · DOI

TL;DR

This paper introduces "error stability" as a weaker, more broadly applicable notion of algorithmic stability than previously used. They use this to derive "sanity-check bounds" for leave-one-out cross-validation, guaranteeing its performance is not much worse than training error, even for complex algorithms. This work is crucial for understanding the reliability of a widely used model selection technique.

What Problem Does This Paper Address?

Estimating how well a machine learning model will perform on unseen data (generalization error) is a fundamental challenge. Training error, while easy to compute, can be overly optimistic. Cross-validation, particularly leave-one-out (LOO) cross-validation, is a popular technique for estimating generalization error. However, theoretical guarantees for LOO's accuracy have been limited to specific types of algorithms (like nearest-neighbor) and often rely on strong assumptions about algorithmic stability. The authors aim to provide more general theoretical assurances for LOO, specifically "sanity-check bounds" that guarantee its performance is not significantly worse than the training error, even for a broader class of algorithms.

Methods

The core contribution is the introduction of error stability. This concept measures how much the error of a hypothesis changes when a single data point is removed from the training set, as opposed to how much the hypothesis itself changes (which is the stronger notion of "hypothesis stability").

They then use this error stability to derive new sanity-check bounds for the leave-one-out estimate. These bounds relate the difference between the LOO estimate and the true generalization error to the algorithm's error stability, the VC dimension of the hypothesis class, and other parameters.

The paper also revisits and generalizes existing results based on hypothesis stability, highlighting its limitations in more realistic (unrealizable) settings. They apply their new framework to specific algorithm classes:

  • Training error minimization algorithms: They show that these algorithms naturally satisfy certain error stability properties, leading to bounds that are independent of the VC dimension in some cases.
  • Bayesian algorithms: They demonstrate how their framework can be applied to randomized Bayesian algorithms, providing bounds based on their error stability.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and does not present experimental results on specific datasets.

Key Insights and Ideas

  • Error Stability is Key: The paper argues that "error stability" (how much the error changes with data removal) is a more practical and widely applicable notion than "hypothesis stability" (how much the hypothesis changes). This is because many natural algorithms might change their hypotheses significantly but still maintain a similar error.
  • LOO is "Sanity-Checked": The derived bounds guarantee that LOO's performance is not much worse than training error, providing a theoretical justification for its use even when strong stability guarantees are absent.
  • VC Dimension's Role: For training error minimizers, the bounds show that the dependence on VC dimension can be removed under certain conditions, suggesting that for these algorithms, LOO's accuracy is less sensitive to model complexity than previously thought.
  • Lower Bounds Highlight Necessity: The paper provides lower bounds demonstrating that error stability is indeed necessary for proving nontrivial bounds on LOO error, and that some assumptions beyond just error stability are required.

Key Results

  • Theorem 4.1: Provides a general sanity-check bound for deterministic algorithms based on error stability, VC dimension, and an "overestimation" property (LOO not underestimating training error).
  • Theorem 4.2: Shows that for training error minimization algorithms, the LOO error bound is O(√d/m), where 'd' is VC dimension and 'm' is sample size, with a dependence on 1/δ (probability parameter) that is generally unavoidable.
  • Theorem 4.4 & 4.5: Extend these results to randomized Bayesian algorithms, showing similar bounds based on their error stability.
  • Theorem 5.1 & 5.2: Provide lower bounds showing that the dependence on 1/√m and VC dimension (in some cases) is unavoidable for training error minimizers.
  • Theorem 5.3 & 5.4: Demonstrate that error stability alone is not sufficient for nontrivial LOO bounds, even with small VC dimensions, and that additional assumptions are needed.

Limitations and Future Work

  • Unrealizable Case Challenges: The paper notes that hypothesis stability is often too strong for the "unrealizable" case (where the target function is not in the hypothesis class), motivating the need for error stability.
  • Overestimation Assumption: The bounds often rely on the assumption that LOO "overestimates" the training error. While plausible for some algorithms (like training error minimizers), proving this property for general heuristics is an open problem.
  • Quantitative vs. Qualitative: The authors emphasize that their bounds focus on the qualitative behavior (e.g., dependence on parameters) rather than precise quantitative values.
  • Future Work:
    • Proving sanity-check bounds for popular heuristics like C4.5 and backpropagation.
  • Investigating whether error stability combined with limited VC dimension is sufficient for sanity-check bounds.
  • Improving the quantitative accuracy of the upper and lower bounds.
  • Generalizing results to other loss functions and k-fold cross-validation.

Summary updated

BibTeX
@inproceedings{kearns1997algorithmic,
  author = {Michael J. Kearns and Dana Ron},
  title = {{Algorithmic Stability and Sanity-Check Bounds for Leave-one-Out Cross-Validation}},
  booktitle = {Conference on Learning Theory},
  year = {1997},
  doi = {10.1145/267460.267491},
}
Figure