Learning Curves: Asymptotic Values and Rate of Convergence

Corinna Cortes, Lawrence D. Jackel, Sara A. Solla, Vladimir Vapnik, John S. DenkerNeurIPS 1993 · OpenReview

The Resource Dilemma in Model Training

Training state-of-the-art classifiers on massive datasets is computationally expensive, often requiring weeks of processing time. This paper introduces a principled method to predict a model's final performance using only a fraction of the data. This allows researchers to terminate underperforming architectures early and allocate resources to the most promising candidates.

In machine learning research, a common "resource dilemma" arises when datasets grow large. Training every possible classifier architecture to completion becomes impossible due to limited compute. A naive solution is to train all candidates on a small subset of the data and pick the winner. However, this is highly risky due to the "Crossing Phenomenon."

Crossing learning curves

As illustrated above, the relative rankings of classifiers are not stable across dataset sizes. A "fast learner" might perform well on small data but plateau early with a higher final error. Conversely, a "slow learner" might start poorly but eventually reach a much lower error rate given enough data. To solve this, we need a way to accurately extrapolate "learning curves"—plots of error versus training set size—to predict final performance on the full database.

Extrapolating Performance: The Sum and Difference Method

The authors propose a predictive method based on the theoretical observation that test and training errors converge toward a common asymptotic value ($a$) as the training set size ($l$) increases. They model these errors using power-law decays:

  • Test Error: $\epsilon_{test} = a + b/l^\alpha$
  • Training Error: $\epsilon_{train} = a - c/l^\beta$

This highlights an elegant symmetry of errors: test and training errors are roughly symmetric around their shared asymptote. Training error underestimates the true error, while test error overestimates it, but they "squeeze" together following predictable power laws.

Assuming the exponents and amplitudes are roughly equal ($\alpha \approx \beta$ and $b \approx c$), the authors derive a clever "sum and difference" trick. When plotted on a log-log scale:

  1. The sum ($\epsilon_{test} + \epsilon_{train}$) approaches a constant value ($2a$), revealing the best possible error the model can achieve.
  2. The difference ($\epsilon_{test} - \epsilon_{train}$) forms a straight line with a slope of $-\alpha$, revealing how fast the model learns.
Log-log plot of error sum and difference

The resulting algorithm is straightforward: measure errors at a few intermediate training sizes, plot them in log-log space to find the parameters, and then project those lines out to the full database size.

Experimental Validation and Key Results

The study primarily uses the NIST Special Database 3 (handwritten digits), evaluating both a binary task (separating digits 0-4 from 5-9) and a full 10-class digit recognition task using a 60,000-pattern database.

  • Validation on Linear Classifiers: The model showed excellent agreement with experimental data for boolean classifiers, where the sum and difference plots formed near-perfect straight lines.
  • Saving Weeks of Training: The method was tested on a modified version of LeNet, a famous early convolutional neural network. By training on only 12,000 patterns, the authors successfully predicted that a new architecture would be twice as accurate as the old one at the full 60,000-pattern mark. This justified a three-week training run on the new architecture with high confidence.
  • Theoretical Alignment: The empirical results (finding $\alpha$ between 0.5 and 1.0) align well with predictions from the statistical mechanics of learning.

Insights, Limitations, and Future Work

During their experiments, the authors discovered a surprising empirical correlation: the harder the task (higher asymptotic error $a$), the slower the learning rate (smaller exponent $\alpha$). This means difficult problems are a "double whammy"—you get worse results, and it takes significantly more data to get there. This correlation is not accounted for by existing theoretical models and remains a subject for future research.

While powerful, the method has limitations:

  • Large-Scale Assumption: The power-law modeling is assumed to hold only for "large" training sets. It may fail if the training set is too small to capture the underlying complexity of the task.
  • Parameter Sensitivity: The model assumes $b \approx c$ and $\alpha \approx \beta$. While the authors provide a weighted sum method to handle cases where this doesn't hold, it adds complexity to parameter extraction.

Ultimately, this paper provides a highly practical framework for managing computational resources, allowing researchers to confidently peek into the future of their models' training trajectories.

Summary updated

Abstract

Training classifiers on large databases is computationally demand(cid:173) ing. It is desirable to develop efficient procedures for a reliable prediction of a classifier's suitability for implementing a given task, so that resources can be assigned to the most promising candidates or freed for exploring new classifier candidates. We propose such a practical and principled predictive method. Practical because it avoids the costly procedure of training poor classifiers on the whole training set, and principled because of its theoretical foundation. The effectiveness of the proposed procedure is demonstrated for both single- and multi-layer networks. 1
BibTeX
@inproceedings{cortes1993learning,
  author = {Corinna Cortes and Lawrence D. Jackel and Sara A. Solla and Vladimir Vapnik and John S. Denker},
  title = {{Learning Curves: Asymptotic Values and Rate of Convergence}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {1993},
  url = {https://openreview.net/forum?id=SJ-sRvWdZr},
}
Figure