PaperlayerView exact revision on arXiv

Source-linked AI summary

The Shape of Learning Curves: a Review

Tom Viering, Marco Loog

arXiv:2103.10948v2cs.LG

TL;DR

The paper addresses how learning curves depend on training-set size and how their shapes can be characterized and used. It reviews definitions, estimation, applications, and theoretical and empirical evidence, finding diverse behavior with no universal model.

  • Problem

    Learning-curve behavior is important for understanding generalization and planning model selection, data collection, and computation, but its shapes and governing factors remain incompletely characterized.

  • Method

    The paper reviews the origins, formal definition, estimation, applications, and theoretical and empirical literature on learning-curve shapes, including Gaussian-process analyses and ill-behaved cases.

  • Results

    Learning curves can show power-law or exponential behavior, but Gaussian-process curves and ill-behaved examples exhibit richer shapes; no universal model is identified.

  • Takeaways & Limitations

    Learning curves should be examined as functions of training-set size because their shape can inform model selection, extrapolation, and reductions in data-collection or computational costs.

  • Takeaways & Limitations

    Theoretical results often concern relatively basic learners, while empirical studies are frequently limited in scope, leaving substantial behavior poorly understood.

Abstract

from arXiv · show

Learning curves provide insight into the dependence of a learner's generalization performance on the training set size. This important tool can be used for model selection, to predict the effect of more training data, and to reduce the computational complexity of model training and hyperparameter tuning. This review recounts the origins of the term, provides a formal definition of the learning curve, and briefly covers basics such as its estimation. Our main contribution is a comprehensive overview of the literature regarding the shape of learning curves. We discuss empirical and theoretical evidence that supports well-behaved curves that often have the shape of a power law or an exponential. We consider the learning curves of Gaussian processes, the complex shapes they can display, and the factors influencing them. We draw specific attention to examples of learning curves that are ill-behaved, showing worse learning performance with more training data. To wrap up, we point out various open problems that warrant deeper empirical and theoretical investigation. All in all, our review underscores that learning curves are surprisingly diverse and no universal model can be identified.

1 INTRODUCTION

This review defines machine-learning learning curves around generalization performance versus training-set size, distinguishes them from training and human memorization curves, and surveys their shapes and uses.

  • A learning curve plots a learner’s generalization performance against the number of training examples.
  • The review focuses on supervised classification and regression, distinguishing well-behaved curves from ill-behaved curves that may worsen with more data.
  • The paper reviews curve estimation, practical uses, theoretical and empirical shape evidence, and research directions.
  • Learning Curve Origins and Meanings: The concept traces to Ebbinghaus for human learning, while machine-learning usage developed through later discussions and perceptron analyses.
  • Learning Curve Origins and Meanings: Machine-learning learning curves concern performance on unseen data, unlike Ebbinghaus-style curves, which measure memorization of supplied material.
  • Learning Curve Origins and Meanings: In this review, a learning curve also differs from a training curve, which plots training error or an objective against optimization epochs or iterations.

2 DEFINITION, ESTIMATION, FEATURE CURVES

The review formalizes learning curves as expected risk across training-set sizes, explains practical estimation and plotting, and cautions that scalar summaries can hide diverse curve behavior.

  • Definition: An individual learning curve records a learner’s risk for training sets of size n, while averaging over training sets yields the expected learning curve.
  • Definition: A problem-average learning curve averages performance over a distribution of problems and is especially natural for Bayesian approaches.
  • Estimation: In practice, hold-out methods, k-fold cross-validation, or repeated random train-test splits estimate learning curves from finite data.
  • Estimation: Hyperparameters should ideally be tuned separately for each training-set size because their optimal values can depend strongly on n.
  • Plotting: Logarithmic axes can reveal small gains and make power-law or exponential behavior easier to inspect.
  • Summarizing Learning Curves: AULC averages performance across selected sample sizes but assumes those sizes are equally likely and cannot distinguish crossing curves.
  • Summarizing Learning Curves: Because learning-curve shapes are diverse, summaries should use multiple parametric models and report the best-fit parameters together with fit quality.
  • Feature Curves: Peaking describes a learning curve with a maximum, often a cusp, associated with model instability and distinct from feature-curve peaking caused by dimensionality.

3 GENERAL PRACTICAL USAGE

Learning curves support model comparison, data-collection planning, and computational savings, but crossings, model dependence, and sample-size limitations complicate their use.

  • Better Model Selection and Crossing Curves: A single benchmark score can miss sample-size-dependent algorithm rankings, because learning curves may cross as training data increases.
  • Better Model Selection and Crossing Curves: Across 36 datasets, decision trees and logistic regression had crossing learning curves in 15 cases, with the complex model better at large sample sizes.
  • Better Model Selection and Crossing Curves: Separability and dimensionality can indicate which algorithms dominate, while comparing training and learning errors can reveal overfitting.
  • Extrapolation and Sample Size: Learning-curve extrapolation can estimate how many examples are needed for a target performance and when data collection can stop.
  • Extrapolation and Sample Size: For classifiers, power calculations that ignore the machine-learning model may fail to predict the minimal sample size accurately.
  • Speeding Up Training and Tuning: Progressive sampling can stop training when the curve becomes nearly flat, potentially reducing computation time and memory.
  • Speeding Up Training and Tuning: Initial learning curves can predict classifier rankings or hyperparameter choices, reducing costly cross-validation or full training.

4 WELL-BEHAVED LEARNING CURVES

Learning curves often improve with more data and are frequently modeled by power laws or exponentials, but empirical and theoretical evidence also reveals substantial dependence on the problem, learner, and fitting procedure. No universal shape is established.

  • Definition and broad evidence: Well-behaved curves improve with increased training sample sizes, satisfying ¯R_n(A) ≥ ¯R_{n+1}(A) for all n.Such learners are also called smart or monotone in related settings.
  • Empirical parametric fits: Power laws often fit empirical learning curves, including decision trees, logistic regression, machine translation, and deep neural networks.The power law with offset can model non-zero asymptotic error, while deep-network studies report power-law behavior across many data scales and domains.
  • Empirical parametric fits: 12 of 14 decision-tree datasets favored a power law, while another study found EXP3 had the lowest MSE in 64 of 86 well-fitted cases.The latter analysis used 121 datasets and C4.5, showing that exponential fits can outperform power laws in some settings.
  • Evidence limitations: Evidence for power laws remains qualified because studies may omit competing models, goodness-of-fit tests, or relevant offsets, and fitting can require substantial hyperparameter and model-size tuning.Bounded performance measures also make unbounded logarithmic or power-law extrapolations suspect outside the observed range.
  • Theoretical evidence: Theoretical conclusions depend on assumptions: PAC bounds use changing worst-case distributions, whereas fixed-distribution learning curves can decrease faster or wiggle.For well-specified Bayesian problems, theoretical posterior-averaged curves are provably monotone and favor exponential and power-law shapes.
  • Problem-dependent shapes: Exponential behavior is supported for some problems, including a provable 1NN curve with error 2^-n when two classes are sufficiently separated.Other studies also report exponential fits, and theoretical work permits exponential, power-law, or arbitrarily slow convergence for optimal learners.

5 GAUSSIAN PROCESS LEARNING CURVES

Gaussian-process learning curves are especially tractable for problem-averaged squared loss under Gaussian likelihoods, revealing multiple shape regimes and important limits of spectral approximations.

  • Gaussian-process setting: For GP regression with Gaussian likelihood and squared loss, the problem-averaged learning curve equals the Bayes risk, or problem-averaged squared error.In the well-specified case, this quantity equals the posterior variance.
  • Gaussian-process setting: The problem-averaged curve averages over test points and input training sets after GP averaging has already accounted for problems and output samples.A fixed-training-set version leaves only the average over input training sets unfinished.
  • Spectral analysis: The covariance eigendecomposition supplies eigenfunctions and eigenvalues used to express, approximate, or bound GP learning curves.The remaining average over random training inputs is typically analytically intractable.
  • Two regimes and length scale: GP length scales often create an initial linear-decrease regime followed by an asymptotic regime with diminishing returns as training-point effects interact.Initially, points are far apart and reduce posterior variance similarly; later, nearby points provide less additional information.
  • Asymptotic behavior: The PA curve cannot decrease faster than 1/n for large n in the discussed setting, while asymptotically training and test errors coincide.The cited approximation is an upper bound on training loss and a lower bound on the PA curve.
  • Limits of spectral analysis: Learning curves are not reliably determined by eigenvalue spectra alone: equal spectra can yield different curves, and several bounds may be arbitrarily loose.The review identifies these as limitations of spectrum-based approximation and motivates seeking additional information.
  • Smoothness and curve shape: Under Sacks-Ylvisaker regularity, smoother Gaussian processes have faster asymptotic PA-curve decay, with rate Opn^(-(2s+1)/(2s+2)).The review contrasts power-law behavior for finite smoothness with faster-than-power-law decay for the squared exponential covariance.
  • Bounds: Williams and Vivarelli construct learning-curve bounds by treating each training point as a one-point training set and selecting the closest point for each test point.The construction relies on error decreasing when the training set grows.

6 ILL-BEHAVED LEARNING CURVES

Ill-behaved learning curves can worsen with additional data, either for particular training sets or in expectation, and include phase transitions alongside other nonstandard shapes.

  • Overview: More training data can worsen learning performance for a particular training set and, less obviously, in expectation over training sets.Such deterioration is not necessarily caused by finite samples or experimental setup.
  • Overview: The review contrasts this possibility with common expectations that learning performance improves or decays monotonically as sample size increases.The cited literature describes monotonic improvement as expected or conventional wisdom in many settings.
  • 6.1 Phase Transitions: Phase transitions are abrupt or nearly discontinuous changes in learning-curve properties, often analyzed using statistical-physics techniques in large-sample, high-dimensional limits.Most theoretical results concern relatively simple learners and often problem-averaged curves.
  • Overview: Figure 3 categorizes qualitative learning-curve shapes by subsection, using sample size n horizontally and dotted lines for under- versus overparameterization transitions.It includes error, squared loss, NLL, absolute loss, and problem-average curves.
  • 6.1 Phase Transitions: Binary-weight perceptrons can show long random-guessing plateaus until learning begins near the transition from overparameterization to underparameterization.The reported transition occurs around n relative to d, with memorization typically when n < d and learning when n > d.
  • 6.1 Phase Transitions: Phase transitions also appear in two-layer binary-weight networks, parity problems, unsupervised learning, PCA with missing data, and some real-data experiments.The review notes that phase transitions in bounds may not necessarily occur in the actual learning curve.

6.2 Peaking and Double Descent

Peaking and sample-wise double descent are nonmonotonic learning-curve behaviors associated with model instability, while regularization and learner choice can alter or remove the peak.

  • Peaking: Peaking is a cusp-like maximum in the learning curve and can occur even in realizable settings, unlike feature-curve peaking caused by dimensionality.Its apparent cause is related to model instability.
  • Peaking and double descent: Sample-wise double descent names the peak in performance versus training-set size for deep neural networks; model-wise and epoch-wise variants use different horizontal axes.Model-wise double descent concerns model size, whereas epoch-wise double descent concerns the training curve.
  • PFLD: PFLD often peaks near d ≈ n for squared loss and classification error, with α = d/n controlling relative dimension and sample size in asymptotic analyses.PFLD is a minimum-norm, ridgeless linear-regression classifier based on the pseudo-inverse.
  • Mechanism: PFLD error contains decreasing terms for mean estimation and dimensionality reduction, but covariance-eigenvalue estimation error increases with n and can create instability near n ≈ d.Small eigenvalues are inverted, so small estimation errors can have a large effect.
  • Mitigation: Regularization can prevent PFLD peaking, but performance is highly sensitive to tuning the ridge parameter λ.Under isotropic data, optimal regularization removes the peak in the cited analysis.
  • Learner dependence: SVMs may avoid peaking in some settings, although double descent can still occur for feature curves with squared hinge loss.The cited feature-curve peak is typically located at n > d.
  • Scope of analyses: Random-matrix analyses of peaking often use asymptotic limits where both n and d, or another complexity measure, diverge.The review cautions that conclusions from this setting require careful interpretation.

6.3 Dipping and Objective Mismatch

Dipping occurs when performance improves initially but deteriorates with more data, often because the optimized objective is mismatched with the evaluation metric or the problem is misspecified.

  • 6.3 Dipping: Dipping is a learning curve that improves initially, then deteriorates permanently, so its best expected performance occurs at a finite training-set size.The behavior can occur for nearest-neighbor methods, kernel rules, and several linear classifiers.
  • 6.3 Dipping: A two-class toy problem shows SVM, logistic regression, LDA, and PFLD converging toward a suboptimal decision boundary as data becomes infinite.The figure attributes the mismatch to optimizing a surrogate loss rather than classification error.
  • Objective mismatch: Dipping requires a misspecified classification problem and optimization of an objective different from the learning curve’s evaluation metric.This is common because error rate, AUC, and F-measure are difficult to optimize directly.
  • Objective mismatch: C4.5 and kNN can deteriorate because their training procedures or objectives do not directly optimize the reported evaluation measure.Examples include greedy error minimization for C4.5 and AUC evaluation for kNN.
  • Active learning: Active-learning curves can dip, with optimal performance at fewer labeled samples than the complete training set.The review suggests this may reflect better alignment between active selection and the evaluation measure.
  • Other examples: Least-squares dipping in a time-series setting can arise from changing noise distributions, whereas likelihood fitting resolves the nonmonotonicity.The parametric model itself is adequate in the cited example.
  • Other examples: Negative transfer is interpretable as dipping when additional source data harms target performance because training combines source and target data.The objective mismatch comes from joint source-target training rather than target-only training.

6.4 Risk Monotonicity and ERM

Standard empirical risk minimization can produce non-monotonic learning curves across density estimation, classification, and regression, including increases, recovery, and jagged behavior. These examples challenge simple explanations based on dipping or peaking.

  • 6.4 Risk Monotonicity and ERM: ERM exhibits non-monotonic learning behavior in density estimation, classification, and regression.The reported examples use standard empirical risk minimization.
  • 6.4 Risk Monotonicity and ERM: Squared loss can increase with training-set size before eventually recovering.This behavior is described as distinct from dipping and peaking.
  • 6.4 Risk Monotonicity and ERM: Non-monotonicity can occur for any training-set size, without a direct link to learner capacity.The passage uses this observation to rule out an explanation based on peaking.
  • 6.4 Risk Monotonicity and ERM: Proofs cover squared, absolute, and hinge loss, while likelihood estimators exhibit the same deficiency.Mean estimation with L2 loss and the memorize algorithm are reported as provably monotonic exceptions.
  • 6.4 Risk Monotonicity and ERM: Regularization can worsen non-monotonicity, although optimal regularization tuning can guarantee monotonicity in certain settings.An experiment also reports a surprisingly jagged learning curve for absolute loss.

6.5 Misspecified Gaussian Processes

Misspecified Gaussian-process models can generate complex, non-monotonic learning curves, including multiple overfitting maxima and plateaus. Evidence maximization can remove these maxima in the hypercube setting and alleviate non-monotonicity.

  • 6.5 Misspecified Gaussian Processes: Gaussian-process learning curves receive special analytical treatment because they are more readily analyzed theoretically.The review focuses a dedicated section on these results.
  • 6.5 Misspecified Gaussian Processes: For a uniform hypercube distribution, multiple overfitting maxima and plateaus may occur even when student and teacher noise levels match.The analysis assumes shared eigenfunctions but potentially different eigenvalues.
  • 6.5 Misspecified Gaussian Processes: In one dimension, arbitrarily many overfitting maxima may appear when the student's noise level is sufficiently small.
  • 6.5 Misspecified Gaussian Processes: Evidence maximization removes the arbitrarily many hypercube overfitting maxima and makes the learning curve monotone.The optimized hyperparameters include length scale and noise level.
  • 6.5 Misspecified Gaussian Processes: Optimizing hyperparameters by evidence maximization can alleviate non-monotonicity.

6.6 Misspecified Bayesian Regression

Misspecified Bayesian regression can produce broad peaks in squared risk, including when the estimator remains consistent. The review describes SafeBayes, a modified Bayesian rule that alleviates these peaks and generally improves curve behavior empirically.

  • 6.6 Misspecified Bayesian Regression: Hierarchical Bayesian linear regression can produce a broad peak in squared risk when homogeneous noise is violated.The estimator can otherwise remain consistent.
  • 6.6 Misspecified Bayesian Regression: Misspecification is constructed by mixing ground-truth samples with noiseless samples generated at a fixed location.A fair coin determines which generation process produces each sample.
  • 6.6 Misspecified Bayesian Regression: The broad peak cannot be explained by dipping, peaking, outlier sensitivity, or approximation errors.The authors attribute the behavior to Bayes' rule under misspecification and note that it can occur for non-convex model classes.
  • 6.6 Misspecified Bayesian Regression: SafeBayes raises the likelihood to a power η and alleviates the broad peak.The parameter η cannot be learned in a Bayesian way, and the approach is empirically shown to make curves generally more well-behaved.

6.7 The Perfect Prior

Even with a perfect prior and Bayesian estimation, an individual problem can exhibit a non-monotonic learning curve. Such bumps can arise in flexible Bayesian estimation tasks, while posterior variance has a narrower monotonicity exception for conjugate exponential-family models.

  • 6.7 The Perfect Prior: A monotone prior-averaged learning curve does not guarantee monotonicity for every individual problem.The review illustrates this with Bayesian estimation of a coin's probability.
  • 6.7 The Perfect Prior: The coin-estimation construction produces a bump: loss rises and is eventually recovered as n approaches infinity.
  • 6.7 The Perfect Prior: This construction can create non-monotonic behavior for practically any Bayesian estimation task.The passage also notes that regularization can generate comparable learning-curve shapes.
  • 6.7 The Perfect Prior: Posterior variance can increase for a single problem unless the likelihood is in the exponential family with a conjugate prior.Gaussian processes fall within this latter class.

6.8 Monotonicity: a General Fix?

The review examines whether generally applicable methods can make learning curves monotone. Proposed approaches can guarantee or achieve monotonicity, but may involve assumptions or a trade-off with learning speed.

  • Monotonicity: a General Fix?: A wrapper can make any classifier monotone in error rate with high probability by selecting among models trained on increasing sample sizes.The wrapper retains the previous model unless the newer model is significantly better on validation data; consistency is preserved under stated conditions.
  • Monotonicity: a General Fix?: The wrapper may learn more slowly, raising a possible trade-off between monotonicity and learning speed.
  • Monotonicity: a General Fix?: Two algorithms guarantee monotonicity without setting aside validation data, assuming finite Rademacher complexity for the hypothesis class composed with the loss.
  • Monotonicity: a General Fix?: For 0-1 loss, any learner can be transformed into a monotonic one, disproving the conjecture that universally consistent monotone classifiers do not exist.

7 DISCUSSION AND CONCLUSION

The review finds that learning curves have diverse, often complex shapes, while current theory and empirical evidence remain too limited to support a universal model. It identifies methodological concerns and several open problems for understanding, fitting, and applying these curves.

  • Discussion and Conclusion: Power-law behavior in large deep learners has empirical support, but conclusions remain premature; exponential and other shapes also remain plausible.
  • Discussion and Conclusion: Gaussian-process learning curves have analytically tractable special cases, yet their general shape remains difficult to characterize and can involve multiple regimes.
  • Discussion and Conclusion: Ill-behaved curves show that learning performance can worsen with more data, and such behavior may occur even in well-specified, realizable settings.
  • Discussion and Conclusion: No generally applicable parametric model currently covers all learning-curve shapes, especially ill-behaved curves, although power laws and exponentials may belong in a flexible model class.
  • Discussion and Conclusion: Averaging hundreds or thousands of curves can mask individual-curve characteristics, motivating models for single-training-set curves.
  • How to Robustly Fit Learning Curves: Learning-curve fitting often relies on questionable least-squares log-value models and may fail; one reported study discarded 2% of fits.
  • How to Robustly Fit Learning Curves: Gaussian-noise assumptions are disputable because typical losses are non-negative and bounded, so confidence intervals and p-values require caution.
  • Bounds and Alternative Statistics: Uniform generalization bounds do not necessarily characterize curve shape: a strictly decreasing bound neither implies monotone learning nor rules out ill-behavior.
Loading 2103.10948v2…