Learning curves

Two curves, two limits#

Fix a learning algorithm and let $E_{val}(n)$ and $E_{train}(n)$ denote expected validation and training error at training-set size $n$. Standard behaviour: $E_{val}(n)$ decreases toward an asymptote $E_\infty$; $E_{train}(n)$ increases toward the same asymptote (small samples are easier to fit than the population). The asymptote decomposes as irreducible noise plus the model class's approximation error — the bias term — while the gap $E_{val}(n) - E_{train}(n)$ tracks the variance/capacity term. The two diagnoses of the beginner section are readings of which term dominates.

Power-law shape#

Empirically and under several theoretical models, the excess error follows

$$ E_{val}(n) - E_\infty \approx b\, n^{-\beta} $$

with $\beta$ typically in $[0.5, 1]$ for classical models under smoothness assumptions (Amari, Fujita and Shinomoto, 1992, give $\beta = 1$ regimes for parametric learning). Large-scale empirical confirmation: Hestness et al. (2017), Deep learning scaling is predictable, empirically — across vision, language and speech, held-out loss follows power laws over orders of magnitude of $n$, with domain-dependent exponents. The programme culminates in neural scaling laws — Kaplan et al. (2020), Scaling laws for neural language models, and the compute-optimal reallocation of Hoffmann et al. (2022, Chinchilla) — where fitted curves in $n$ (tokens) and parameters drive multi-million-dollar data-versus-model budget decisions. The same logic, at learn-more-Python scale, is this lesson's plateau reading; the connection to LLM practice is covered in how LLMs work.

Fitting and extrapolating curves#

Practical sample-size forecasting fits $\hat{E}(n) = a + b n^{-\beta}$ to measured points by nonlinear least squares (weighted toward larger $n$, where variance is lower) and extrapolates. Figueroa et al. (2012, BMC Medical Informatics) validate this workflow for clinical text classification. Caveats: power-law fits are locally excellent and globally fallible — regime changes (new classes appearing, distribution shift as data collection broadens) break the extrapolation; report prediction intervals, not point forecasts. Mohr and van Rijn (2022), Learning curves for decision making in supervised machine learning — a survey, catalogue parametric forms and their failure modes.

Uses beyond the data-budget question#

• Early discarding in model selection: extrapolated curves let searches kill configurations predicted to plateau low (Domhan, Springenberg and Hutter, 2015) — the model-based cousin of successive halving's empirical ranking.
• Data valuation: the marginal value of a data point at current $n$ is the local slope $\partial E / \partial n$ — the quantity that pricing data acquisition or active learning implicitly estimates.
• Sanity-checking pipelines: a validation curve that fails to improve with $n$ on a task known to be learnable is a strong leakage or preprocessing-bug signal — sometimes the cheapest integration test a pipeline gets.

Sample-complexity theory, briefly#

PAC bounds give worst-case guarantees of the form $n = O!\left(\frac{d + \log(1/\delta)}{\varepsilon^2}\right)$ samples for error $\varepsilon$ at confidence $1-\delta$, with $d$ the VC dimension. These are distribution-free and correspondingly loose — often orders of magnitude above empirical needs. The practical stance: theory bounds the shape of what is possible; measured learning curves estimate the constants that matter for your dataset. When they conflict, the curve wins.

What to learn next#

• Overfitting and underfitting — the two diseases this instrument diagnoses.
• Data labelling — what the "more data" branch actually costs.
• AIC and BIC — model selection from a single fit, when retraining many times is off the table.