A Bound on the Error of Cross Validation Using the Approximation and Estimation Rates, with Consequences for the Training-Test Split

Michael J. KearnsNeurIPS 1995 · OpenReview

This paper, authored by Michael Kearns (then at AT&T Research), provides a rigorous theoretical framework for one of the most common tasks in machine learning: deciding how to split a dataset into training and testing sets for model selection. By deriving formal bounds on cross-validation error, Kearns explains why certain "rules of thumb" work and how the optimal split changes based on the complexity of the problem.

TL;DR

The paper provides a formal bound on cross-validation error using "approximation" and "estimation" rates. It reveals that while the optimal training-test split depends on the unknown complexity of the target function, a small, fixed test set (around 10%) is remarkably robust and near-optimal across a wide range of scenarios.

What Problem Does This Paper Address?

In model selection, practitioners often face a dilemma: how much data should be withheld for a test set? If you withhold too much, the model is trained on insufficient data and performs poorly. If you withhold too little, your estimate of the model's performance becomes noisy and unreliable, leading you to choose the wrong model architecture.

While the "80/20" or "90/10" split is common practice, it was largely heuristic at the time of this paper. Kearns seeks to provide a formal mathematical justification for these splits by analyzing how the generalization error of cross-validation behaves as a function of the split ratio, the sample size, and the underlying complexity of the task.

Methods

The author treats model selection as a two-part problem: choosing the right number of parameters (architecture) and tuning those parameters. The analysis relies on two key concepts:

  1. Approximation Rate ($\epsilon_g(d)$): This measures the "representational power" of a model class with $d$ parameters. It represents the best possible error a model of that size could achieve if it had infinite data.
  2. Estimation Rate ($\rho(d, m)$): This measures the "generalization gap"—how much the error on a finite training set of size $m$ is likely to deviate from the true error.

Kearns derives Theorem 1, a bound that combines these rates with a third term representing the error introduced by the testing phase itself. He then applies this theory to a specific case study called the Intervals Problem (learning boolean step functions on a line), deriving an analytical expression for the optimal test fraction ($\gamma_{opt}$).

Datasets

The paper relies on synthetic datasets and theoretical models rather than real-world benchmarks to maintain mathematical clarity:

  • The Intervals Problem: A 1D problem where the goal is to learn a function consisting of $s$ alternating segments.
  • The Perceptron Problem: A high-dimensional problem involving linear classifiers with sparse weights.
  • Power Law Decay Models: A parametric approach used to simulate how approximation error typically drops as model complexity increases in neural networks.
  • Experimental Setup: For the empirical plots, the author generated 5,000 to 10,000 synthetic samples, often corrupted with 30% label noise to test the robustness of the bounds.

Key Insights and Ideas

  • The "Bowl" Phenomenon: When a problem is simple relative to the amount of data available, the cross-validation error is relatively insensitive to the split ratio. The error curve looks like a wide, flat bowl.
Cross-validation error bound showing the "bowl" shape
  • Complexity Shifts the Split: As the target function becomes more complex, the "bowl" narrows and the optimal test fraction ($\gamma$) decreases. In other words, harder problems require you to give a larger percentage of your data to the training set to get any meaningful learning done.
  • The Robustness of 10%: One of the most practical takeaways is that a small, fixed test set (around 10%) performs near-optimally for a very wide range of target complexities. This provides a theoretical "blessing" for the common 90/10 split used in the industry.
  • Trade-off Dynamics: The paper formalizes the trade-off: as you increase the test set size, you get a better estimate of performance (lower test error variance) but a worse model (higher approximation error due to less training data).

Key Results

  • Theorem 1: Provides a rigorous upper bound on the generalization error of a model chosen via cross-validation.
  • Sensitivity Analysis: Experiments showed that for a simple task ($s=10$ intervals), any split between 10% and 50% worked well. However, for a complex task ($s=100$), a 50% test split resulted in significantly worse performance than a 10% split.
Error vs. train set size for varying complexities
  • Invariance: The qualitative properties of the optimal split (the "four important phenomena" listed in Section 6) appear to be invariant across different types of problems, including perceptrons and power-law models.

Limitations and Future Work

  • Simple Cross-Validation: The analysis is restricted to the "hold-out" method (a single training-test split). It does not formally cover more computationally expensive variants like $k$-fold cross-validation or leave-one-out, though the author suggests the themes likely apply.
  • Nested Classes: The theory assumes models are chosen from a nested sequence of function classes ($H_1 \subset H_2 \dots$), which may not describe all modern model selection scenarios (e.g., comparing completely different architectures).
  • Qualitative vs. Quantitative: While the bounds are rigorous, they contain constants that are difficult to calculate for real-world datasets, meaning the results are more useful for understanding trends than for calculating the exact number of samples to hold out in a specific project.
  • Future Directions: The author suggests investigating "non-classical" learning problems where the learning curve does not follow a standard power law, as these might break the observed split-ratio patterns.

Summary updated

Abstract

We give a theoretical and experimental analysis of the generalization error of cross validation using two natural measures of the problem under consideration. The approximation rate measures the accuracy to which the target function can be ideally approximated as a function of the number of parameters, and thus captures the complexity of the target function with respect to the hypothesis model. The estimation rate measures the deviation between the training and generalization errors as a function of the number of parameters, and thus captures the extent to which the hypothesis model suffers from overfitting. Using these two measures, we give a rigorous and general bound on the error of the simplest form of cross validation. The bound clearly shows the dangers of making γ —the fraction of data saved for testing—too large or too small. By optimizing the bound with respect to γ, we then argue that the following qualitative properties of cross-validation behavior should be quite robust to significant changes ...
BibTeX
@inproceedings{kearns1995bound,
  author = {Michael J. Kearns},
  title = {{A Bound on the Error of Cross Validation Using the Approximation and Estimation Rates, with Consequences for the Training-Test Split}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {1995},
  url = {https://openreview.net/forum?id=B1V6VPWO-S},
}
Figure