Validation and overfitting

The previous note removed the leaks: no feature carries the answer, and every fitted step of the pipeline sees only training rows. A clean split is still not a measurement of the risk. A validation score is an average over a finite set of examples, so it is a random number with a spread; the model reported is usually the best of many tried on the same examples, so its score is biased upward; and the split must imitate how the model will be used, or the score answers a different question. This note builds the protocol: which data are used for what, how to reuse them efficiently with cross-validation, how big the error bar is, and how to keep model selection from contaminating the final estimate.

Notation. The data $D$ hold $n$ labelled pairs. A model trained on a set $T$ is $\hat f_T$; its risk is $R(\hat f_T)$, and its average loss on a disjoint set $V$ is $\hat R_V(\hat f_T) = \frac{1}{\lvert V \rvert}\sum_{i \in V} L(y_i, \hat f_T(x_i))$. In $K$-fold cross-validation, $D$ is split into folds $D_1, \dots, D_K$ and $D_{-k}$ is everything except $D_k$. A hyperparameter, such as a polynomial degree or a number of neighbours, is $\lambda$.

Three sets and what each is for#

The training error is useless as an estimate of risk; the opening note showed it falling to zero while the risk exploded. The standard protocol therefore uses three disjoint parts:

• the training set, on which the model’s parameters are fitted;
• the validation set, on which choices that are not fitted by the training procedure are made: hyperparameters, features, the model family, when to stop;
• the test set, touched once, at the end, to report the risk of the final choice.

Why three rather than two? Every decision made by looking at a set uses up some of its honesty. If twenty hyperparameter values are compared on the validation set, the winner’s validation score includes the luck of that comparison; only a set that played no part in any decision still gives an unbiased estimate. The NLP course states the same rule for text corpora in three splits and what each is for.

A score on $m$ independent test examples is an average of $m$ losses, so the central limit theorem gives its error bar. Worked example. Accuracy $0.85$ on $m = 500$ test examples has standard error $\sqrt{0.85 \cdot 0.15 / 500} = 0.016$, so the 95% interval is $0.85 \pm 0.031$. Halving the interval needs four times as many test examples, and two models whose accuracies differ by 0.02 on this test set cannot be told apart by unpaired intervals; the paired bootstrap compares them on the same examples and is much sharper.

Cross-validation: every example validates once#

A hold-out split wastes data twice: the validation examples do not train the model, and the training examples do not validate it. With a few hundred rows both halves are small. $K$-fold cross-validation (Stone, 1974) splits the data into $K$ folds, trains $K$ models, each on $D_{-k}$, scores each on its own fold, and averages:

$$\hat R_{\mathrm{CV}} = \frac1K \sum_{k=1}^K \hat R_{D_k}\big(\hat f_{D_{-k}}\big) .$$

Figure

Cross-validation and nested cross-validation

Every example is validated exactly once, by a model that did not see it. The price is $K$ fits instead of one. Each model is trained on a fraction $(K - 1)/K$ of the data, so the estimate describes a slightly smaller training set and is slightly pessimistic; with $K = n$, leave-one-out, that bias almost vanishes, at the cost of $n$ fits. $K = 5$ or $10$ is the usual compromise. After cross-validation has chosen the hyperparameters, the final model is refitted on all the data.

What cross-validation estimates. One would like $\hat R_{\mathrm{CV}}$ to estimate the risk of the model fitted on these data. It does not do that well: it estimates the average risk of models fitted on training sets like this one, drawn from the same distribution (Bates, Hastie and Tibshirani, 2024; Hastie, Tibshirani and Friedman, 2009, Section 7.12). For model selection this is fine, since the question is which procedure works better; it matters when the number is read as a guarantee for one deployed model.

Splits that match deployment#

A random split assumes that the rows are independent draws and that future cases come from the same distribution. When either assumption fails, the split must be built to imitate deployment (Roberts et al., 2017).

• Stratified folds keep the class proportions of the whole data in every fold. For rare classes this matters: with 5 positives among 100 objects and random folds of 20, the number of positives in a fold is hypergeometric, and a fold has no positive at all with probability $\binom{95}{20} / \binom{100}{20} = 0.319$. On such a fold recall is undefined, because its denominator TP + FN counts the actual positives and is 0. Precision has the denominator TP + FP, the predicted positives: it is undefined only if the model flags nothing in the fold, and equals 0 as soon as it flags anything, since every flag is then a false alarm.
• Group splits keep all the rows of one group (a patient, a user, a shop, a document) on the same side. If several photos of one patient are split across training and validation, the model can recognize the patient rather than the disease, and the score measures memorization. Whenever the model will meet new groups, the validation must contain unseen groups.
• Time splits train on the past and validate on the future: an expanding window that trains on months $1, \dots, t$ and validates on month $t + 1$, for several $t$. A random split of time-ordered data lets the model learn from the future, and features such as “spend in the last 30 days” become leaks. A gap between the training and the validation period imitates the delay before a model is deployed.

Overfitting and underfitting#

As a model family grows richer, the training error falls steadily and the validation error falls, reaches a minimum and rises: the U-shape of the opening note’s figure. Left of the minimum the model underfits: both errors are high and close to each other, because the family cannot represent the regularities in the data. Right of it the model overfits: the training error is much lower than the validation error, because the model fits the noise of its sample. The bias–variance note gives the decomposition behind the two regimes.

A learning curve plots both errors against the size of the training set and tells which regime a model is in. For the polynomial example of the opening note (a sine with noise variance 0.09, equally spaced inputs), the exact expected errors are:

Training points	Degree 1: training	Degree 1: new data	Degree 9: training	Degree 9: new data
12	0.329	0.318	0.015	0.208
24	0.308	0.298	0.053	0.124
48	0.297	0.291	0.071	0.107
192	0.289	0.287	0.085	0.095

The straight line underfits: its two errors are close from the start and both converge to about 0.29, far above the noise level of 0.09, so more data cannot help; a richer family can. (Its training error is even slightly above its error on new data, because equally spaced inputs include the two ends of the interval, where a line misses the sine most.) The degree-9 polynomial overfits on 12 points, with a gap of 0.19 between the two errors, and the gap closes as data grow: at 192 points both errors are within 0.01 of the noise. More data is the cure for overfitting; it does nothing for underfitting.

How noisy is a validation estimate?#

A cross-validated score is a random variable: it depends on which examples happened to be drawn and how they were split. The figure measures that spread in a setting where the true risk is known exactly:

Figure

How accurate risk estimates are

Three things stand out. The training error is biased by $-0.10$ on a true risk of about 0.21: it is not an estimate of risk at all. A 20% hold-out is nearly unbiased but its 8 validation examples give a spread of 0.15, as large as the effect one might want to detect. Cross-validation uses every example for validation and halves the spread to 0.07, which is close to $\sqrt{0.21 \cdot 0.79 / 40} = 0.064$, the standard error of an error rate measured on 40 independent examples. That is a benchmark for this setting, not a universal floor: it describes a proportion of independent 0–1 errors, and estimators that use more than the 0–1 errors, or correlated and stratified observations, can have a different spread. Reshuffling the same 40 examples does not create new information, so cross-validation stays near it.

The error bar of cross-validation. The natural error bar takes the standard deviation of the $K$ fold scores and divides by $\sqrt K$. In the figure’s setting it averages 0.059, while the actual spread of the 5-fold estimate is 0.074. The fold scores are not independent: the training sets of any two folds share most of their rows, so their models make similar errors, and the naive formula ignores the correlation. Bengio and Grandvalet (2004) proved that no unbiased estimator of the variance of $K$-fold cross-validation exists that is valid for all distributions, and Bates, Hastie and Tibshirani (2024) show that the naive intervals can cover far less often than their nominal level and propose a nested scheme that corrects them. In practice: repeat cross-validation with several random splits to remove the noise of the split itself, compare models on the same folds (a paired comparison), and expect the naive error bar to be too narrow, as it is in this setting and in the settings Bates, Hastie and Tibshirani study; it is not a guaranteed lower bound on the uncertainty either.

Reusing a test set#

Each look at a test set followed by a decision makes the next look less honest. When $M$ models are compared on one validation set, the best score is biased upward even if all the models are equally good: the probability course computes that the best of 1,000 equally accurate models, scored on 10,000 examples, looks on average 1.3 accuracy points better than it is, and that Hoeffding’s inequality with the union bound guarantees a margin of $\sqrt{(\ln M + \ln(2/\delta))/(2n)}$ for all of them at once. The bound assumes the candidates were fixed in advance. A researcher who tries a model, looks at the test score, adjusts, and looks again is choosing candidates adaptively, and the bound no longer applies; Dwork et al. (2015) show how fast such adaptive reuse can overfit a hold-out set and how to limit it. How large the effect is in practice depends on the field: when Recht et al. (2019) collected new test sets for CIFAR-10 and ImageNet, accuracies fell by 3–15 and 11–14 points, yet the ranking of the models was almost unchanged, and they attribute the drop to a slightly harder new test set rather than to adaptive overfitting.

The rule that follows is simple: decisions are made on validation data (or by cross-validation), and the test set is used once. A test set that has been used to choose between models becomes a validation set.

Nested cross-validation#

Cross-validation is often used both to choose hyperparameters and to report the result, which reintroduces the selection bias. The best cross-validated score over many hyperparameter values is optimistic for the same reason as the best of $M$ models (Varma and Simon, 2006; Cawley and Talbot, 2010). Nested cross-validation separates the two jobs:

1. An outer loop splits the data into $K$ folds. For each outer fold $k$:
2. an inner cross-validation on $D_{-k}$ alone chooses $\lambda$;
3. the model with that $\lambda$ is refitted on $D_{-k}$ and scored on $D_k$.
4. The average of the $K$ outer scores estimates the risk of the whole procedure, selection included.

The right half of the figure above shows one outer round. On pure noise, where every model has true accuracy 0.5, choosing the number of neighbours $k$ of a nearest-neighbour classifier among 20 values by 5-fold cross-validation and reporting the best cross-validated accuracy gives 0.567 on average over 200 datasets of 100 objects; nested cross-validation gives 0.504 (the Code section). The outer estimate describes the procedure, not one $\lambda$: different outer folds may choose different values, and the final model is obtained by running the inner selection once more on all the data.

What changed#

	Training error	Hold-out	$K$-fold CV	Nested CV
Bias in the figure’s setting	$-0.10$	$+0.01$	$+0.01$
Spread in the figure’s setting	0.05	0.15	0.07
Fits needed	1	1	$K$	$K \times K_{\text{inner}}$ per candidate
Safe for selecting and reporting at once	no	no	no	yes

Limitations#

• Every estimate assumes the split imitates deployment. If the future differs from the past (a new market, a policy change), no resampling of the past measures it; only data from the new regime do.
• Small data stay noisy. An error rate $p$ measured on $n$ independent examples has standard error $\sqrt{p(1-p)/n}$, and cross-validation on the same $n$ examples typically stays near this benchmark: it does not create information.
• Cross-validation is expensive. $K$ fits per candidate, and $K \times K$ for nested schemes; for large neural networks a single hold-out set is usually all that is affordable, which is acceptable when the validation set is large.
• The naive error bar is often too narrow, and there is no universal unbiased replacement; repeated and nested schemes help.

What you should remember#

• Training data fit the parameters, validation data make the choices, test data are used once to report.
• A score on $m$ independent examples has standard error $\sqrt{p(1-p)/m}$: 0.85 on 500 examples is $\pm 0.031$ at 95%.
• $K$-fold cross-validation validates every example once; it is slightly pessimistic and estimates the risk of the procedure on similar training sets.
• Stratify for rare classes, keep groups together, split time-ordered data by time.
• Underfitting: both errors high and close; overfitting: a large gap that shrinks with more data.
• The fold-to-fold error bar of cross-validation tends to underestimate its spread (0.059 against 0.074 in the figure’s setting).
• The best of many validation scores is optimistic; nested cross-validation reports the selection procedure honestly.

Code#

The error bar of a test accuracy, an empty fold, exact learning curves, the spread of risk estimates, and nested against flat cross-validation:

import numpy as np
from numpy.polynomial import legendre as L
from scipy import stats

rng = np.random.default_rng(0)

# the error bar of a test accuracy: 0.85 on 500 independent examples
se = np.sqrt(0.85 * 0.15 / 500)
print(round(float(se), 3), round(float(1.96 * se), 3))                                    # 0.016 0.031

# 100 objects, 5 positives, 5 folds of 20: the chance that a random fold has no positive at all
print(round(float(stats.hypergeom(100, 5, 20).pmf(0)), 3))                         # 0.319

# learning curves, exact: polynomials of degree 1 and 9 on n equally spaced points of sin(2 pi x) + N(0, 0.3^2)
m, s2 = (lambda x: np.sin(2 * np.pi * x)), 0.09
gx, gw = L.leggauss(200); gx, gw = (gx + 1) / 2, gw / 2
def expected_errors(n, deg):
    x = np.linspace(0, 1, n)
    A = np.linalg.pinv(L.legvander(2 * x - 1, deg))
    G = L.legvander(2 * gx - 1, deg) @ A
    train = (((m(x) - L.legvander(2 * x - 1, deg) @ A @ m(x)) ** 2).sum() + s2 * (n - deg - 1)) / n
    return round(float(train), 3), round(float(s2 + gw @ (G @ m(x) - m(gx)) ** 2 + s2 * gw @ (G ** 2).sum(axis=1)), 3)
for deg in (1, 9):
    print(deg, [expected_errors(n, deg) for n in (12, 24, 48, 192)])
# 1 [(0.329, 0.318), (0.308, 0.298), (0.297, 0.291), (0.289, 0.287)]
# 9 [(0.015, 0.208), (0.053, 0.124), (0.071, 0.107), (0.085, 0.095)]

# how far risk estimates fall from the true risk: nearest centroid, 40 objects in 20 dimensions, signal in one
n, d, R = 40, 20, 2000
y = np.repeat([0, 1], n // 2)
mu = np.zeros((2, d)); mu[0, 0], mu[1, 0] = -1, 1
def fit(X, yy): return np.array([X[yy == 0].mean(0), X[yy == 1].mean(0)])
def error(c, X, yy): return float(((((X - c[1]) ** 2).sum(1) < ((X - c[0]) ** 2).sum(1)) != yy).mean())
def true_risk(c):
    w, mid = c[1] - c[0], c.mean(0)
    return 0.5 * stats.norm.cdf(w @ (mu[0] - mid) / np.linalg.norm(w)) + 0.5 * stats.norm.cdf(-w @ (mu[1] - mid) / np.linalg.norm(w))
def folds(K):
    f = np.empty(n, int)
    for cl in (0, 1):
        f[rng.permutation(np.flatnonzero(y == cl))] = np.arange(n // 2) % K
    return f
out = {k: [] for k in ('train', 'hold', 'cv5', 'loo', 'se5', 'risk')}
for _ in range(R):
    X = rng.normal(size=(n, d)) + mu[y]
    c = fit(X, y); risk = true_risk(c); out['risk'].append(risk)
    out['train'].append(error(c, X, y) - risk)
    f = folds(5)
    out['hold'].append(error(fit(X[f != 0], y[f != 0]), X[f == 0], y[f == 0]) - risk)
    e = [error(fit(X[f != k], y[f != k]), X[f == k], y[f == k]) for k in range(5)]
    out['cv5'].append(np.mean(e) - risk); out['se5'].append(np.std(e, ddof=1) / np.sqrt(5))
    out['loo'].append(np.mean([error(fit(np.delete(X, i, 0), np.delete(y, i)), X[i:i + 1], y[i:i + 1]) for i in range(n)]) - risk)
for k in ('train', 'hold', 'cv5', 'loo'):
    print(k, round(float(np.mean(out[k])), 3), round(float(np.std(out[k], ddof=1)), 3))
print(round(float(np.mean(out['risk'])), 3), round(float(np.mean(out['se5'])), 3))
# train -0.101 0.048 | hold 0.011 0.147 | cv5 0.01 0.073 | loo 0.004 0.069
# 0.21 0.059: the mean true risk and the mean naive standard error of the 5-fold estimate

# choosing k for kNN on pure noise: the best cross-validated accuracy against nested cross-validation
ks = np.arange(1, 40, 2)                                                    # 20 candidate values of k
def knn_errors(Xtr, ytr, Xte, yte):
    D = ((Xte[:, None, :] - Xtr[None, :, :]) ** 2).sum(-1)
    votes = np.cumsum(ytr[np.argsort(D, axis=1)], axis=1)[:, ks - 1]        # positives among the k nearest, every k
    return ((votes > ks / 2) != yte[:, None]).mean(0)
def cv_errors(X, yy, K=5):
    f = rng.permutation(len(yy)) % K
    return np.mean([knn_errors(X[f != k], yy[f != k], X[f == k], yy[f == k]) for k in range(K)], axis=0)
flat, nested = [], []
for _ in range(200):
    X, yy = rng.normal(size=(100, 10)), rng.integers(0, 2, 100)            # labels carry no information
    flat.append(1 - cv_errors(X, yy).min())
    f, acc = rng.permutation(100) % 5, []
    for k in range(5):
        tr, te = f != k, f == k
        best = np.argmin(cv_errors(X[tr], yy[tr]))                          # the inner loop picks k
        acc.append(1 - knn_errors(X[tr], yy[tr], X[te], yy[te])[best])
    nested.append(np.mean(acc))
print(round(float(np.mean(flat)), 3), round(float(np.mean(nested)), 3))       # 0.567 0.504

Next#

A validation protocol can now measure any model honestly. The models so far are only thought experiments: the memorizer and the polynomial. The next note introduces the first practical method, the one closest to memorizing: predict for a new object what happened to the most similar objects in the training set. It needs only a notion of distance, it is consistent as the data grow, and it breaks in high dimension in a way that motivates the global models of the rest of the course.

References#

• E. Sokolov et al. Машинное обучение (HSE), lecture notes, lecture 1: introduction (hold-out and cross-validation).
• T. Hastie, R. Tibshirani, J. Friedman. The Elements of Statistical Learning, 2nd ed. Springer, 2009. Sections 7.2 and 7.10 (model complexity, cross-validation), Section 7.12 (conditional or expected test error).
• M. Stone. Cross-validatory choice and assessment of statistical predictions. Journal of the Royal Statistical Society B, 36(2), 1974.
• Y. Bengio, Y. Grandvalet. No unbiased estimator of the variance of K-fold cross-validation. Journal of Machine Learning Research, 5, 2004.
• S. Bates, T. Hastie, R. Tibshirani. Cross-validation: what does it estimate and how well does it do it? Journal of the American Statistical Association, 119(546), 2024. arXiv: 2104.00673.
• D. R. Roberts et al. Cross-validation strategies for data with temporal, spatial, hierarchical, or phylogenetic structure. Ecography, 40(8), 2017.
• S. Varma, R. Simon. Bias in error estimation when using cross-validation for model selection. BMC Bioinformatics, 7, 2006.
• G. C. Cawley, N. L. C. Talbot. On over-fitting in model selection and subsequent selection bias in performance evaluation. Journal of Machine Learning Research, 11, 2010.
• C. Dwork, V. Feldman, M. Hardt, T. Pitassi, O. Reingold, A. Roth. The reusable holdout: preserving validity in adaptive data analysis. Science, 349(6248), 2015.
• B. Recht, R. Roelofs, L. Schmidt, V. Shankar. Do ImageNet classifiers generalize to ImageNet? ICML, 2019.