Generalization and Cross-Validation

Risk, held-out estimates, and cross-validation

Last modified: 2026-11-19

Show code
# reticulate provisions the Python packages that this page imports.
library(reticulate) # nolint: undesirable_function_linter
py_packages <- c("numpy", "pandas", "matplotlib", "SyncRNG")
py_require(py_packages)

Source

Adapted from Brian Hutchinson’s Fall 2025 lecture notes, which supplied the crime-and-income example and the generalization argument. Logan Sizemore’s Spring 2025 lecture on generalization is the basis of the cross-validation section. The wider reading is Hastie et al. [1], Chapter 2, and James et al. [2], Chapter 2.

1 Generalization

Watch

Hutchinson covers generalization, bias, variance and overfitting, in the video Generalization (31 min) [3].

Definition 1 (Objective function (objective))

Definition 1 (Objective function (objective)) An objective function, or objective for short [4, Sec. 1.1] and 4.1, is the quantity training optimizes as the model’s parameters vary, by minimizing it or by maximizing it. It is a function of the parameters alone, with the data held fixed. For a model \(\modmemof{\param}\) with parameters \(\param\) and a training set \(\trainset\), the objective that is the empirical risk is

\[ \objfnf{\param} \eqdef \empriskf{\modmemof{\param}; \trainset} , \tag{1}\]

and training minimizes \(\objfnf{\param}\) over \(\param\).

Example 1 (The objective as a function of the slope and intercept)

Example 1 (The objective as a function of the slope and intercept) For the crime data, the objective is the empirical risk as a function of the pair \((m, b)\).

# The five neighbourhoods of @tbl-crime-data, read once in @exm-crime-task.
x <- crime$x
y <- crime$y

objective <- function(m, b) mean((m * x + b - y)^2)

fit <- lm(y ~ x)
m_hat <- coef(fit)[["x"]]
b_hat <- coef(fit)[["(Intercept)"]]
print(round(c(objective(0, mean(y)), objective(m_hat, b_hat)), 6))
[1] 0.023056 0.002721

The flat line \((m, b) = (0, \bar y)\) has objective value \(0.023056\), and the least-squares pair \((\hat m, \hat b) = (-1.2877, 0.7052)\) has the smaller value \(0.002721\). Training searches over \((m, b)\) for the pair with the smallest value.

Remark 1 (The empirical risk is one objective among many)

Remark 1 (The empirical risk is one objective among many). So far the only objective in these notes is the empirical risk, which the minimization problem minimizes over the slope and intercept. Later chapters change the objective without changing the loss: whatever is handed to the optimizer is the objective, and the empirical risk is only one thing it can be made from.

Definition 2 (Cost function)

Definition 2 (Cost function) A cost function is an objective function for which smaller values are better.

Example 2 (The empirical risk of the crime data as a cost function)

Example 2 (The empirical risk of the crime data as a cost function) For the crime data, the objective of Example 1 is the empirical risk under squared-error loss, which is a cost function: \[ \objfnf{m, b} = \frac{1}{n} \sum_{i=1}^n (m x_i + b - y_i)^2 . \] A line farther from the data has a larger value.

# Raising the slope of the fitted line by 1 increases the squared errors.
cost_fitted <- objective(m_hat, b_hat)
cost_steeper <- objective(m_hat + 1, b_hat)
costs <- c(cost_fitted, cost_steeper)
round(costs, 6)
[1] 0.002721 0.119961

The pair \((\hat m, \hat b)\) from lm has cost \(0.002721\), and raising the slope by 1 raises the cost to \(0.119961\). Training moves toward smaller values, so it minimizes this cost. Figure 1 plots both against the data.

Show code
crime_points <- tibble::tibble(x = x, y = y)
crime_points |>
  ggplot2::ggplot() +
  ggplot2::aes(x = x, y = y) +
  ggplot2::geom_point() +
  ggplot2::geom_abline(intercept = b_hat, slope = m_hat, colour = "#0072B2") +
  ggplot2::geom_abline(
    intercept = b_hat,
    slope = m_hat + 1,
    colour = "#D55E00"
  ) +
  ggplot2::expand_limits(y = 0.7) +
  ggplot2::labs(x = "Per-capita income", y = "Crime rate")
Figure 1: The fitted line (blue) and the line with its slope raised by 1 (orange), over the crime data.
A scatter plot of five points, crime rate from 0.09 to 0.48 against per-capita income from 0.18 to 0.49. A blue line, the fitted line, slopes down from about 0.47 at income 0.18 to about 0.07 at income 0.49 and passes near every point. An orange line, with slope raised by 1, is much flatter, running from about 0.65 down to about 0.56. It lies above all five points.

Remark 2 (How the loss, the empirical risk, the objective function and the cost function relate)

Remark 2 (How the loss, the empirical risk, the objective function and the cost function relate). Four related quantities answer different questions.

  • The loss function assesses one prediction.
  • The empirical risk is the loss averaged over the \(n\) examples in the training set, so it assesses a model on the whole training set.
  • The objective function is whatever training optimizes as the parameters vary. So far it is the empirical risk. For a penalized fit such as the one in the ridge regression section, it combines the empirical risk, or a multiple of it, with a penalty.
  • A cost function is an objective function for which smaller values are better, so training minimizes it. The log-likelihood is an objective function that training maximizes, so minus the log-likelihood is a cost function. Other texts also use “cost function” for the loss function or for the empirical risk, but here it always refers to a minimized objective function.

Under squared-error loss, the empirical risk is the sample mean squared error, and the residual sum of squares is \(n\) times that empirical risk. The two differ only by the factor \(n \ge 1\), so they have the same minimizers.

Exercise 1 (Estimate what cannot be computed)

Exercise 1 (Estimate what cannot be computed) The risk cannot be evaluated, and the empirical risk can. The solution to “Which model was actually better?” rules out reporting the second in place of the first.

Describe a procedure that uses only the available data and returns an honest estimate of the risk, and say what the procedure costs.

Solution 1. Set some data aside. Split \(\trainset\) before fitting anything; fit on one part; score on the other. The scored part played no role in choosing the model’s parameters, so the sample mean of its losses is an unbiased estimate of the risk: over repeated draws of the held-out points, it equals the risk on average, neither systematically above nor below.

The cost is the data itself. Points moved into the held-out set are points the model never learns from, so the model is worse than it needed to be, and the estimate depends on however few points were set aside and is noisy in proportion.

The usual arrangement is three sets rather than two:

  1. A training set, which the fit uses.

  2. A validation set (Definition 3; also called a development or dev set), scored repeatedly while choosing between models, tuning their settings, and deciding when to stop.

  3. A test set (Definition 5), scored exactly once, at the end, on the model finally chosen. It stays unused until then.

The third set exists because of what the second one does. A validation set consulted a hundred times is a set a hundred decisions have been fitted to, and its score stops being honest about a model those decisions selected. Section 1.1 covers what to do when there is not enough data for all three.

Example 3 (Splitting the Auto data)

Example 3 (Splitting the Auto data) Split the cars of the Auto data [2] at random, 60% for training, 20% for validation and the rest for testing.

# Draw the three index sets from one shuffled list of cars, so that they cannot overlap.
import numpy as np
import pandas as pd

auto_split = pd.read_csv("data/auto.csv").dropna(subset=["horsepower"])
n_cars = len(auto_split)
shuffled = np.random.default_rng(571).permutation(n_cars)
n_train = int(0.6 * n_cars)
n_val = int(0.2 * n_cars)
idx_train = shuffled[:n_train]
idx_val = shuffled[n_train:n_train + n_val]
idx_test = shuffled[n_train + n_val:]
print(n_train, n_val, len(idx_test))
235 78 79

Of the 392 cars with a recorded horsepower, 235 form the training set, which is all the fitting procedure sees, and the other 157 are held out of the fit.

Definition 3 (Validation set)

Definition 3 (Validation set) A validation set is a subset of the data set, the pairs indexed by a set \(\validx\) that shares no index with \(\trainidx\), and that we use for model selection among candidate models fitted to the training set [5]:

\[ \valset \eqdef \set{(\vpredvar_i, \outvar_i) : i \in \validx} \subseteq \dataset, \quad \validx \cap \trainidx = \emptyset . \tag{2}\]

The model with the smallest empirical risk on the validation set is the one we keep.

Definition 4 (Validation error)

Definition 4 (Validation error) The validation error of a model \(\modmem\) is its empirical risk on the validation set, \(\empriskf{\modmem; \valset}\).

See validation error in the statistics notes.

Example 4 (Choosing a polynomial degree)

Example 4 (Choosing a polynomial degree) Fit polynomials of degree 1 to 9 to the 235 training cars of Example 3, predicting mpg from horsepower, and score each on the 78 validation cars.

# Scale horsepower to 0 to 1 so that high degrees are numerically stable.
hp = auto_split["horsepower"].to_numpy(dtype=float)
hp = (hp - hp.min()) / (hp.max() - hp.min())
mpg = auto_split["mpg"].to_numpy(dtype=float)

def mse(coef, idx):
    return np.mean((np.polyval(coef, hp[idx]) - mpg[idx]) ** 2)

degrees = range(1, 10)
fits = {d: np.polyfit(hp[idx_train], mpg[idx_train], d) for d in degrees}
val_mse = {d: mse(fits[d], idx_val) for d in degrees}
train_mse = {d: mse(fits[d], idx_train) for d in degrees}
best_degree = min(val_mse, key=val_mse.get)
train_mse_9 = train_mse[9]
val_mse_9 = val_mse[9]
val_mse_best = val_mse[best_degree]

def mse_ci(coef, idx):
    # Normal-approximation 95% interval for the mean of the squared errors.
    sq = (np.polyval(coef, hp[idx]) - mpg[idx]) ** 2
    se = sq.std(ddof=1) / np.sqrt(len(sq))
    return sq.mean() - 1.96 * se, sq.mean() + 1.96 * se

val_ci_best = mse_ci(fits[best_degree], idx_val)
val_ci_9 = mse_ci(fits[9], idx_val)
print(best_degree, round(val_mse[best_degree], 3), round(train_mse_9, 3), round(val_mse_9, 3))
2 18.006 16.78 19.559
print(np.round(val_ci_best, 3), np.round(val_ci_9, 3))
[12.012 23.999] [11.9   27.218]

The degree with the smallest validation error, 2, is the one we keep. The training cars could not make this choice, because the training error keeps falling as the degree grows: the degree-9 fit has training error 16.78 and validation error 19.56. The chosen degree’s validation error, 18.01, has a 95% confidence interval of 12.01 to 24.00, and the degree-9 fit’s has 11.90 to 27.22. Each interval comes from the 78 validation cars alone, and the chosen degree’s is optimistic, because the same cars picked the degree.

Definition 5 (Test set)

Definition 5 (Test set) A test set is a subset of the data set, the pairs indexed by a set \(\testidx\) that shares no index with \(\trainidx\) or \(\validx\), and that we use only once, after the model is chosen, to estimate the risk of the chosen model \(\modmem\) by its empirical risk on the test set, \(\empriskf{\modmem; \testset}\):

\[ \testset \eqdef \set{(\vpredvar_i, \outvar_i) : i \in \testidx} \subseteq \dataset, \quad \testidx \cap \paren{\trainidx \cup \validx} = \emptyset . \tag{3}\]

Definition 6 (Test error)

Definition 6 (Test error) The test error of a model \(\modmem\) is its empirical risk on the test set, \(\empriskf{\modmem; \testset}\).

See test error in the statistics notes.

Example 5 (Reporting the chosen degree’s error)

Example 5 (Reporting the chosen degree’s error) Having chosen degree 2 on the validation cars of Example 4, score that one model on the 79 test cars.

# Refit the chosen degree on the training cars of @exm-training-set (scaled horsepower hp, mpg),
# so this chunk does not lean on the fits table of the validation example.
chosen_coef = np.polyfit(hp[idx_train], mpg[idx_train], best_degree)
# A normal-approximation 95% interval: the mean of the squared errors
# plus or minus 1.96 standard errors.
test_sq = (np.polyval(chosen_coef, hp[idx_test]) - mpg[idx_test]) ** 2
test_mse = np.mean(test_sq)
test_se = test_sq.std(ddof=1) / np.sqrt(len(test_sq))
test_lo, test_hi = test_mse - 1.96 * test_se, test_mse + 1.96 * test_se
print(round(test_mse, 3), round(test_lo, 3), round(test_hi, 3))
24.232 14.183 34.281

The estimate of the chosen model’s risk is 24.23, with a 95% confidence interval of 14.18 to 34.28. The test cars played no part in the fit or the choice, so the choice did not tune this estimate to them. If it disappoints and we go back to choose again, the test cars have become a validation set.

Definition 7 (Generalization gap)

Definition 7 (Generalization gap) The generalization gap of a model \(\modmem\) on a training set \(\trainset\) is its risk minus its training error [6, Sec. 5.2]:

\[ \popriskf{\modmem} - \empriskf{\modmem; \trainset} . \tag{4}\]

Example 6 (Estimating the chosen degree’s gap)

Example 6 (Estimating the chosen degree’s gap) The risk in Equation 4 cannot be computed, so estimate it by the test error of Example 5, and subtract the training error of the same degree-2 fit.

# train_mse holds each degree's training error from @exm-validation-set;
# test_mse is the chosen degree's test error from @exm-test-set.
train_mse_best = train_mse[best_degree]
gap_estimate = test_mse - train_mse_best
print(round(train_mse_best, 3), round(test_mse, 3), round(gap_estimate, 3))
17.693 24.232 6.539

The training error is 17.69 and the test error is 24.23, so the estimated gap is 6.54. The estimate is noisy: the 95% interval for the test error in Example 5 runs from 14.18 to 34.28, and it contains the training error, so these cars alone do not show that the gap is positive.

Remark 3 (The three sets together)

Remark 3 (The three sets together). The three index sets \(\trainidx\), \(\validx\) and \(\testidx\) are disjoint and together cover \(1, \ldots, n\), so the training, validation and test sets are disjoint subsets that together make up the data set \(\dataset\), which is why Example 3 draws them from one shuffled list. The sets are not interchangeable: the first is for fitting, the second for choosing among fits, and the third for reporting. Data used for one job gives an optimistic answer to the next, as Figure 2 shows. Any pairs kept out of the fit are called held-out, so validation and test sets are both held-out sets.

The statistics notes define the same three sets formally: the training set, the validation set, and the test set. They use a different symbol for the training set and a plain observation index, but the same three-way split.

Remark 4 (What the validation and test errors estimate)

Remark 4 (What the validation and test errors estimate). Like the training error, the validation error and the test error are empirical risks, and they differ only in the set that scores the model. The model was not fitted to the validation or test set, so each estimates the risk \(\popriskf{\modmem}\) without the optimism of the training error. We choose the model with the smallest validation error, so the validation error of the chosen model is still optimistic. We compute the test error once, after the choice, so it is not.

Some textbooks use “test error” for the expected error of the fitted model on a new observation, which is the risk of the fitted model, not a number computed from a test set [1, Sec. 7.2]. Here the test error is the number computed from the test set, and the risk is what it estimates.

These ideas hold for any loss, not only squared error. Each error is the average loss on the set that scores the model: the training error, the validation error and the test error. The expected loss of the fitted model on a new observation is its generalization error, the risk of the fitted model. Averaging the generalization error over training sets gives the expected generalization error.

In Figure 2, change the degree and the number of training points, and compare the two error curves.

Figure 2: Polynomials fitted to a random sample of the cars in the Auto data [2], mpg against horsepower, scored on the cars in the sample (training) and on the rest (held out), with 95% confidence intervals on the held-out sRMSE.

Remark 5 (Reading the figure on training and held-out error)

Remark 5 (Reading the figure on training and held-out error). The polynomials are fitted with horsepower scaled to run from 0 to 1 and mpg standardized, but every axis and number here is in the original units, horsepower and miles per gallon. The sRMSE is the square root of the sample mean squared error, so it is in the units of the response, here miles per gallon (why we report sRMSE). The vertical bars on the held-out curve and the interval in the readout are 95% confidence intervals for the held-out sRMSE: the mean of the squared errors plus or minus 1.96 standard errors, from the central limit theorem, with the endpoints square-rooted. It is rough when a high-degree fit makes a few squared errors enormous, and it describes the risk of this fitted polynomial, not of the fitting method. The training error has no interval: the fit was chosen to make those errors small, so they are not independent draws and their mean is biased low as an estimate of the risk, and an interval around it would be centered in the wrong place.

Exercise 2 (How far can a held-out score be trusted?)

Exercise 2 (How far can a held-out score be trusted?) A spam filter \(\modmem\) was trained on one set of emails and then scored on a fresh held-out set \(\mathcal{V}\) of \(n\) emails, drawn independently from the same distribution as the emails it will face. Its held-out score \(\empriskf{\modmem; \mathcal{V}}\) is the fraction of those emails it labels wrong, and its risk \(\popriskf{\modmem}\) is its error rate on the population.

Find an upper bound on the chance that the held-out score misses the risk by more than some \(\tolout > 0\), using only the mean and variance of the held-out score.

Solution 2. Write \(Z_i\) for the loss on the \(i\)th held-out email: 1 if \(\modmem\) labels it wrong, and 0 if right. The filter was fixed before \(\mathcal{V}\) was drawn, so the \(Z_i\) are independent, and each is 1 with probability \(\popriskf{\modmem}\). The held-out score is their average, \(\empriskf{\modmem; \mathcal{V}} = \avgin Z_i\), so its mean is \(\popriskf{\modmem}\).

Its variance is the variance of one \(Z_i\) divided by \(n\). A 0/1 variable that is 1 with probability \(R\) has variance \(R(1 - R)\), and that is never more than \(\frac{1}{4}\):

\[ R(1 - R) = \frac{1}{4} - \paren{ R - \frac{1}{2} }^2 \le \frac{1}{4} . \]

So \(\Var{\empriskf{\modmem; \mathcal{V}}} \le \frac{1}{4n}\), whatever the filter’s error rate is. Chebyshev’s inequality bounds the chance of a miss by the variance divided by the square of the miss:

\[ P\paren{ \abs{ \empriskf{\modmem; \mathcal{V}} - \popriskf{\modmem} } > \tolout } \le \frac{\Var{\empriskf{\modmem; \mathcal{V}}}}{\tolout^2} \le \frac{1}{4 n \tolout^2} . \]

Exercise 3 (How far can a held-out score be trusted? (part 2))

Exercise 3 (How far can a held-out score be trusted? (part 2)) Use the setup of Exercise 2.

How does your bound change as \(n\) grows?

Solution 3. The bound shrinks in proportion to \(1/n\): ten times as many held-out emails make a miss of a given size at most a tenth as likely.

Show code
n_example <- 1000
eps_example <- 0.05
cheb_example <- 1 / (4 * n_example * eps_example^2)

For example, with \(n = 1000\) and \(\tolout = 0.05\), the chance of a miss is at most \(1 / (4 n \tolout^2) = 0.1\).

Chebyshev uses only the variance, and the 0/1 range entered only through the cap of \(\frac{1}{4}\) on it. Using the range itself, that each \(Z_i\) lies between 0 and 1, gives a much sharper bound, one that shrinks exponentially in \(n\) rather than in proportion to \(1/n\).

Theorem 1 (Hoeffding’s inequality for a held-out set)

Theorem 1 (Hoeffding’s inequality for a held-out set) Score a classifier \(\modmem\) with the misclassification loss. Let \(\valset\) be a held-out set of \(n\) observations drawn independently from the same distribution \(P(x, y)\), and let \(\empriskf{\modmem; \valset}\) be the fraction of them \(\modmem\) gets wrong, as in the definition of the empirical risk. If \(\modmem\) is fixed before \(\valset\) is drawn, then for every \(\tolout > 0\) [7],

\[ P\paren{ \abs{ \empriskf{\modmem; \valset} - \popriskf{\modmem} } > \tolout } \le 2 e^{-2 \tolout^2 n} . \tag{5}\]

Proof

Proof. The misclassification loss of \(\modmem\) on the \(i\)th held-out point, \(\lossf{y_{(i)}, \modmemf{x_{(i)}}}\), is 1 when \(\modmem\) gets the point wrong and 0 otherwise. Because \(\modmem\) is fixed before \(\valset\) is drawn, each loss is the same function of one of \(n\) independent draws from \(P(x, y)\). So the \(n\) losses are IID random variables in \([0, 1]\). Their common population mean is \(\popriskf{\modmem}\) by the definition of the risk, and their sample mean is \(\empriskf{\modmem; \valset}\) by the definition of the empirical risk. Hoeffding’s inequality for an average of IID variables in \([0, 1]\) bounds the chance that the average misses the mean by at least \(\tolout\) by \(2 e^{-2 \tolout^2 n}\). The event “misses by more than \(\tolout\)” is part of that event, so its chance is at most as large.

Remark 6 (Reading Hoeffding’s inequality)

Remark 6 (Reading Hoeffding’s inequality). The misclassification loss is 1 when \(\modmemf{x} \neq y\) and 0 otherwise, so \(\popriskf{\modmem}\), the risk, is the error rate of the classifier on the population. The probability in Equation 5 is over the draw of \(\mathcal{V}\); \(\popriskf{\modmem}\) is unknown but not random.

Exercise 4 (How many held-out emails are enough?)

Exercise 4 (How many held-out emails are enough?) A spam filter was trained on one set of emails, and you will estimate its error rate on a fresh held-out set. Say the estimate misses when it differs from the filter’s true error rate by more than 0.05.

How many held-out emails make the chance of a miss at most 0.05?

Solution 4. In Exercise 4, the filter was fixed before the held-out set was drawn, so Equation 5 applies. Write \(\tolout\) for the allowed miss and \(\tolin\) for the allowed chance. The chance of a miss is at most \(\tolin\) whenever the bound is:

\[ \begin{aligned} 2 \e{-2 \tolout^2 \nobs} &\le \tolin \\ \e{-2 \tolout^2 \nobs} &\le \frac{\tolin}{2} \\ -2 \tolout^2 \nobs &\le \ln \frac{\tolin}{2} \\ 2 \tolout^2 \nobs &\ge -\ln \frac{\tolin}{2} = \ln \frac{2}{\tolin} \\ \nobs &\ge \frac{\ln (2 / \tolin)}{2 \tolout^2} . \end{aligned} \]

The fourth line multiplies both sides by \(-1\), which flips the inequality, and the fifth divides by \(2 \tolout^2\).

Show code
eps <- 0.05
delta <- 0.05
n_one <- ceiling(log(2 / delta) / (2 * eps^2))

With \(\tolout = 0.05\) and \(\tolin = 0.05\), that is \(\nobs \ge 738\) emails. The bound is loose, so fewer emails may well do, but 738 are enough whatever the classifier’s error rate is.

Exercise 5 (How many held-out emails are enough? (part 2))

Exercise 5 (How many held-out emails are enough? (part 2)) Use the setup of Exercise 4.

Suppose instead that 100 different filters, all trained before the held-out set was drawn, are scored on the same held-out set, and you keep the one with the lowest score. How many held-out emails make the chance that the kept filter’s estimate misses at most 0.05?

Solution 5. In Exercise 5, the kept filter was chosen by its held-out score, so it was not fixed before the held-out set was drawn, and Equation 5 does not apply to it directly.

Show code
n_models <- 100

It does apply to each of the \(M = 100\) filters \(\modmemof{1}, \ldots, \modmemof{M}\), since each was trained before the held-out set was drawn. The kept filter’s estimate can miss only if at least one filter’s estimate does, and the chance that at least one of several events happens is at most the sum of their chances. So

\[ \begin{aligned} P\paren{ \text{the kept filter misses} } &\le P\paren{ \text{some } \modmemof{m} \text{ misses} } \\ &\le \sumto{m}{M} P\paren{ \abs{ \empriskf{\modmemof{m}; \mathcal{V}} - \popriskf{\modmemof{m}} } > \tolout } \\ &\le \sumto{m}{M} 2 \e{-2 \tolout^2 \nobs} \\ &= 2 M \e{-2 \tolout^2 \nobs} , \end{aligned} \]

where the third line applies Equation 5 to each term.

Show code
n_many <- ceiling(log(2 * n_models / delta) / (2 * eps^2))
ratio_many <- round(n_many / n_one, 1)

Repeating the steps of Solution 4 with \(2M\) in place of 2 gives \(\nobs \ge \ln (2M / \tolin) / (2 \tolout^2)\), which is 1659 emails, about 2.2 times as many as for one filter.

Show code
n_half <- ceiling(log(2 / delta) / (2 * (eps / 2)^2))

Both answers are sufficient sizes, not required ones, since they come from an upper bound. Two things still follow for Solution 1’s three sets. The sufficient \(\nobs\) is proportional to \(1 / \tolout^2\), so halving the allowed miss quadruples it: with \(\tolout = 0.025\), Solution 4 needs 2952 emails rather than 738. And a validation set on which a fixed list of \(M\) models is compared needs the size from Solution 5 for that \(M\), \(\ln (2M / \tolin) / (2 \tolout^2)\), while a test set scored once on one model needs only the size from Solution 4. The union bound covers only a finite list of models; tuning a setting that can take infinitely many values needs the further analysis that Abu-Mostafa et al. [8] defers to its chapter 2.

Show code
# HTML formats get an interactive plotly figure; the handout and other formats
# get the same curves as a static SVG from tools/make_big_ideas_figures.py.
if (knitr::is_html_output()) {
  library(plotly)

  # Hoeffding's bound 2 exp(-2 tol^2 n), capped at 1 because a probability
  # cannot exceed 1.
  n_held_out <- seq(0, 2000, length.out = 401)
  bound <- function(tol) pmin(1, 2 * exp(-2 * tol^2 * n_held_out))

  widget <- plot_ly() |>
    add_trace(
      x = n_held_out, y = bound(0.1), type = "scatter", mode = "lines",
      name = "tolerance 0.1", line = list(color = "#1f77b4")
    ) |>
    add_trace(
      x = n_held_out, y = bound(0.05), type = "scatter", mode = "lines",
      name = "tolerance 0.05", line = list(color = "#d95f02", dash = "dash")
    ) |>
    add_trace(
      x = n_held_out, y = bound(0.02), type = "scatter", mode = "lines",
      name = "tolerance 0.02", line = list(color = "#1b9e77", dash = "dot")
    ) |>
    layout(
      xaxis = list(title = "held-out set size n"),
      yaxis = list(title = "bound on the chance of a miss", range = c(0, 1.02)),
      legend = list(orientation = "h", y = -0.2),
      margin = list(t = 10)
    ) |>
    config(displaylogo = FALSE, responsive = TRUE)

  # The alt text: a plotly widget has none of its own.
  htmltools::div(
    role = "img",
    `aria-label` = paste(
      "Interactive plot of Hoeffding's bound against held-out set size for",
      "tolerances 0.1, 0.05 and 0.02. Each curve starts at 1 and falls toward",
      "0, and a smaller tolerance falls later."
    ),
    widget
  )
} else {
  knitr::include_graphics("../images/big-ideas/hoeffding.svg")
}
Figure 3: The bound of Equation 5 on the chance that a held-out estimate misses by more than the tolerance, as the held-out set grows, for three tolerances. The bound is capped at 1, since a probability cannot exceed it. A smaller tolerance needs a much larger held-out set before the bound says anything.

1.1 Cross-validation

Exercise 6 (Use every point twice)

Exercise 6 (Use every point twice) The three sets of Solution 1 are practical only when we have a lot of data. Setting aside a tenth of the data for validation and a tenth for testing leaves the model fitting on the remaining eighty percent, and on a small dataset that costs twice: the model is worse for having seen less, and the held-out estimate is noisy because it is based on so few points.

Design a procedure in which every point is scored by a model that was not fitted to it, and every point also helps fit a model.

Solution 6. Divide the \(n\) points at random into \(k\) groups of roughly equal size. For each group in turn, fit the model on the other \(k-1\) groups and score it on the group left out. Average the \(k\) scores.

This is \(k\)-fold cross-validation (Definition 9), and the groups are its folds.

Exercise 7 (Use every point twice (part 2))

Exercise 7 (Use every point twice (part 2)) Use the setup of Exercise 6.

In your procedure, how many times is each point scored?

Solution 7. Each point belongs to exactly one group, so it is scored exactly once, by the one model that did not see it.

Exercise 8 (Use every point twice (part 3))

Exercise 8 (Use every point twice (part 3)) Use the setup of Exercise 6.

In your procedure, how many times is each point trained on?

Solution 8. Each point is trained on by the other \(k-1\) models. The estimate therefore rests on all \(n\) points rather than on a held-out fraction of them.

Exercise 9 (Use every point twice (part 4))

Exercise 9 (Use every point twice (part 4)) Use the setup of Exercise 6.

What does the procedure cost?

Solution 9. The cost is computation: the model is fitted \(k\) times instead of once. Five and ten are the usual values of \(k\). So use a train-validation-test split when there is plenty of data, and this procedure when there is not.

Definition 8 (Folds)

Definition 8 (Folds) Given a data set of \(n\) pairs, \(k\) folds \(I_1, \ldots, I_k\) are a random partition of the indices \(\set{1, \ldots, n}\) into \(k\) index sets of roughly equal size.

See folds in the statistics notes.

Definition 9 (\(k\)-fold cross-validation)

Definition 9 (\(k\)-fold cross-validation) Given a data set of \(n\) pairs and a learning algorithm, \(k\)-fold cross-validation splits the pairs into \(k\) folds \(I_1, \ldots, I_k\) [9]. For each fold \(I_j\), the algorithm is fit to the pairs outside that fold, which gives the model \(\fitmodf{-j}\).

Definition 10 (\(k\)-fold cross-validation estimate)

Definition 10 (\(k\)-fold cross-validation estimate) The \(k\)-fold cross-validation estimate of the risk scores each pair by the model \(\fitmodf{-j}\) that did not see it (the model fit outside fold \(I_j\) in \(k\)-fold cross-validation), and averages those scores over all \(n\) pairs:

\[ \hR_{k\text{-fold}} \eqdef \frac{1}{n} \sum_{j=1}^{k} \sum_{i \in I_j} \lossf{y_{(i)}, \fitmodf{-j}\paren{x_{(i)}}} . \tag{6}\]

Definition 11 (Leave-one-out cross-validation)

Definition 11 (Leave-one-out cross-validation) Leave-one-out cross-validation is \(k\)-fold cross-validation with \(k = n\) [9]: each pair is a fold of its own, and the model \(\fitmodf{-i}\) is fitted to the other \(n - 1\) pairs. Its estimate of the risk is

\[ \hR_{\text{LOO}} \eqdef \frac{1}{n} \sumin \lossf{y_{(i)}, \fitmodf{-i}\paren{x_{(i)}}} . \tag{7}\]

Example 7 (Leave-one-out on the five neighborhoods)

Example 7 (Leave-one-out on the five neighborhoods) With \(n = 5\) neighborhoods, \(k\)-fold cross-validation with \(k = n\) puts each neighborhood in a fold of its own. This is leave-one-out cross-validation (Definition 11): five fits, each on four neighborhoods and scored on the fifth. Fit the least-squares line to each training set of four, and score it by its squared error on the neighborhood left out:

import numpy as np

# The five neighbourhoods of the crime table, read once in the first example.
x_loo = crime["x"].to_numpy()
y_loo = crime["y"].to_numpy()

loo_py = []
for i_loo in range(5):
    # Train on every neighbourhood except i_loo, so the fit never sees the one it is scored on.
    keep_loo = np.arange(5) != i_loo
    m_loo, b_loo = np.polyfit(x_loo[keep_loo], y_loo[keep_loo], 1)
    # Score the line on the held-out neighbourhood alone.
    loo_py.append((m_loo * x_loo[i_loo] + b_loo - y_loo[i_loo]) ** 2)

loo_py = np.array(loo_py)
# A 95% interval for the mean of the five errors; 2.776 is the t quantile for 4 degrees of freedom,
# which replaces 1.96 because five errors are too few for the normal approximation.
loo_se_py = loo_py.std(ddof=1) / np.sqrt(5)
print(loo_py.round(4), loo_py.mean().round(4), (2.776 * loo_se_py).round(4))
[0.002  0.0026 0.0091 0.     0.015 ] 0.0057 0.0077
# The five neighbourhoods of the crime table, read once in the first example.
crime_loo <- crime
x_loo <- crime$x
y_loo <- crime$y

loo_r <- sapply(1:5, function(i) {
  # Train on every neighbourhood except i, so the fit never sees the one it is scored on.
  fit <- lm(y ~ x, data = crime_loo[-i, ])
  # Score the line on the held-out neighbourhood alone.
  (predict(fit, crime_loo[i, ]) - crime_loo$y[i])^2
})

# The same interval, with the t quantile for 4 degrees of freedom.
loo_se_r <- sd(loo_r) / sqrt(5)
loo_half_r <- qt(0.975, df = 4) * loo_se_r

print(round(c(loo_r, mean = mean(loo_r), half_width = loo_half_r), 4))
         1          2          3          4          5       mean half_width 
    0.0020     0.0026     0.0091     0.0000     0.0150     0.0057     0.0077 

Figure 4 shows the five splits. Each panel lists the neighborhoods in a small table, with the one held out shaded, and plots the same neighborhoods, with that one in a different color and shape. The line is fitted to the four blue circles alone.

Show code
import matplotlib.pyplot as plt

# Okabe-Ito colours, which stay distinct under the common colour-vision deficiencies;
# the circle against the diamond keeps the two groups apart in greyscale too.
train_col, held_col = "#0072B2", "#D55E00"
grid_loo = np.linspace(0.1, 0.55, 50)

fig, axes = plt.subplots(2, 5, figsize=(10, 4.2), layout="constrained",
                         height_ratios=[1.1, 1.4])
for i_loo in range(5):
    keep_loo = np.arange(5) != i_loo
    m_loo, b_loo = np.polyfit(x_loo[keep_loo], y_loo[keep_loo], 1)

    # Top row: the data as a table, with the held-out row shaded and labelled.
    top = axes[0, i_loo]
    top.axis("off");
    top.set_xlim(0, 1);
    top.set_ylim(0, 6.4);
    top.set_title(f"Split {i_loo + 1}", fontsize=10);
    top.text(0.05, 5.7, "x", fontsize=8, fontweight="bold");
    top.text(0.40, 5.7, "y", fontsize=8, fontweight="bold");
    for j in range(5):
        row_y = 4.7 - j
        if j == i_loo:
            top.fill_between([0, 1], row_y - 0.35, row_y + 0.85, color=held_col, alpha=0.25);
        top.text(0.05, row_y, f"{x_loo[j]:.2f}", fontsize=8);
        top.text(0.40, row_y, f"{y_loo[j]:.2f}", fontsize=8);
        top.text(0.72, row_y, "held out" if j == i_loo else "train", fontsize=7,
                 fontweight="bold" if j == i_loo else "normal");

    # Bottom row: the same neighbourhoods as a scatterplot, with the fitted line.
    bot = axes[1, i_loo]
    bot.plot(grid_loo, m_loo * grid_loo + b_loo, color="grey", linewidth=1.5);
    bot.scatter(x_loo[keep_loo], y_loo[keep_loo], color=train_col, marker="o", s=30,
                label="train");
    bot.scatter(x_loo[~keep_loo], y_loo[~keep_loo], color=held_col, marker="D", s=50,
                label="held out");
    bot.set_xlim(0.1, 0.55);
    bot.set_ylim(0, 0.6);
    bot.set_xlabel("per-capita income $x$", fontsize=8);
    if i_loo == 0:
        bot.set_ylabel("crime rate $y$", fontsize=8);
    bot.text(0.12, 0.03, f"error {loo_py[i_loo]:.3f}", fontsize=8);
    bot.tick_params(labelsize=7);
# One key for all five panels, in a row along the bottom of the figure.
fig.legend(*axes[1, 0].get_legend_handles_labels(), fontsize=8,
           loc="outside lower center", ncol=2);
plt.show()
Figure 4: The five leave-one-out splits of the crime data. In each panel the table lists the five neighbourhoods and shades the one held out; the scatterplot draws the held-out neighbourhood as an orange diamond, the four training neighbourhoods as blue circles, and the line fitted to the four, with the squared error on the held-out one.
Five columns, one per split, each with a table above and a scatterplot below. In the table, the five neighbourhoods are listed with their income and crime rate, and one row, a different one in each column, is shaded and marked held out. In the scatterplot, crime rate falls as income rises. Four points are blue circles and one is an orange diamond, the held-out neighbourhood. A grey line fitted to the four blue circles passes above or below the orange diamond by different amounts in the five panels.

The five squared errors are 0.002, 0.003, 0.009, 0.000, 0.015, and their mean, the leave-one-out estimate of the risk, is \(0.006\), with a 95% confidence interval of \(-0.002\) to \(0.013\). The interval is wide because five errors say little about their mean, and it is not a valid interval: the five errors share training points, so they are not independent, and squared errors are skewed, so a t interval fits them poorly. It reaches below zero, which a mean of squared errors cannot, so treat it as a rough guide to the uncertainty. Every neighborhood is scored once, by a line that never saw it, and every neighborhood helps fit four of the five lines. The largest error, 0.015, is in split 5, and the next largest, 0.009, is in split 3. Those two neighborhoods have incomes 0.24 and 0.31, on either side of the steep drop in crime rate that a straight line fitted without one of them smooths over.

Watch

Hutchinson covers train, dev and test sets and cross-validation, Generalization, part 2 (11 min) [3]. The chapter Model Selection puts its cross-validation videos beside each method.

Watch

Starmer explains cross-validation [10].

Read

GeeksforGeeks explains cross-validation [11].

Show code
# The constants of this figure live here, so the widget, the static plot and the prose agree.
cv_n <- 40          # points drawn, and so held-out squared errors
cv_k <- 5           # folds of the static plot
cv_degree <- 3      # degree of the static plot
cv_fresh_n <- 2000  # fresh points the static plot scores
cv_sd <- 0.1        # standard deviation of the noise in the static plot
Show code
ojs_define(cvN = cv_n)

Change \(k\) and the degree in Figure 5, and compare the \(k\)-fold estimate with the error on fresh points.

Figure 5: \(k\)-fold cross-validation of a polynomial fit to cars drawn at random from the Auto data of Figure 2. The grid shows which points each of the \(k\) fits scores; the dots are the \(k\) fold sRMSEs, and the solid line is their root-mean-square, the \(k\)-fold estimate of the sRMSE. The pale band around it is an approximate 95% confidence interval for the estimate: a bootstrap interval for the mean of the held-out squared errors, one per point, with its endpoints square-rooted. It is only approximate and runs too narrow, because the \(k\) fits share most of their training points, so the errors are not independent [12]. In the plot against degree, each bar is a 95% confidence interval, for the \(k\)-fold estimate on its left and for the error on the fresh points on its right; the second is computed as in Figure 2.

Remark 8 (Cross-validation replaces the validation set)

Remark 8 (Cross-validation replaces the validation set). Used to choose between models, cross-validation takes the place of the validation set, the one used again and again, and not of the final test set, which stays unused. Whichever scheme picked the model, the data used to pick it cannot also be the data used to report how good it is. If cross-validation picks the polynomial degree in Figure 5, for example, the cross-validation error of the winning degree is optimistic, because that degree won partly by fitting this sample’s noise well; an honest estimate needs points that took no part in the choice.

Reading

  • Starmer [13] covers the fundamental concepts of machine learning and cross-validation with pictures and little algebra.

  • Stanford University [14], Lectures 3–6, are handwritten notes from a Stanford course on probability and inference. They cover concentration inequalities (Hoeffding’s inequality in Lecture 3), empirical risk minimization and overfitting (Lecture 5), and uniform convergence with generalization bounds (Lecture 6), for readers who want the mathematics behind Hoeffding’s inequality in more detail. The textbook these notes recommend for this material is Shalev-Shwartz and Ben-David [15], Sections 2.1–2.3 and 4.1–4.2, which is free online.

Watch

Andrew Ng’s short lecture for DeepLearning.AI explains how to split data into a training set, a validation set and a test set [16]. The lecture calls the validation set the “dev set”.

Dependency graph

Open the block to see every definition and result of this page, with prerequisites at the top. Click a box to jump to it.

References

[1]
T. Hastie, R. Tibshirani, and J. Friedman, The elements of statistical learning: Data mining, inference, and prediction, 2nd ed. Springer, 2009. Available: https://hastie.su.domains/ElemStatLearn/
[2]
G. James, D. Witten, T. Hastie, and R. Tibshirani, An introduction to statistical learning with applications in R, 2nd ed. Springer, 2021. Available: https://www.statlearning.com/
[3]
B. Hutchinson, “DATA 471/571 (machine learning) and CSCI 481/581 (deep learning) video lectures.” Western Washington University. Accessed: Sep. 28, 2026. [Online]. Available: https://facultyweb.cs.wwu.edu/~hutchib2/video_lectures/data371/
[4]
S. Boyd and L. Vandenberghe, Convex optimization. Cambridge University Press, 2004. doi: 10.1017/CBO9780511804441.
[5]
Wikipedia contributors, “Training, validation, and test data sets — Wikipedia, the free encyclopedia.” 2026. Available: https://en.wikipedia.org/wiki/Training,_validation,_and_test_data_sets
[6]
I. Goodfellow, Y. Bengio, and A. Courville, Deep learning. MIT Press, 2016. Available: https://www.deeplearningbook.org/
[7]
Wikipedia contributors, “Hoeffding’s inequality — Wikipedia, the free encyclopedia.” 2026. Available: https://en.wikipedia.org/wiki/Hoeffding%27s_inequality
[8]
Y. S. Abu-Mostafa, M. Magdon-Ismail, and H.-T. Lin, Learning from data: A short course. AMLBook, 2012. Available: https://amlbook.com/
[9]
Wikipedia contributors, “Cross-validation (statistics) — Wikipedia, the free encyclopedia.” 2026. Available: https://en.wikipedia.org/wiki/Cross-validation_(statistics)
[10]
J. Starmer, “Machine learning fundamentals: Cross validation.” StatQuest, video on YouTube, 2018. Available: https://www.youtube.com/watch?v=fSytzGwwBVw
[11]
GeeksforGeeks, “Cross validation in machine learning.” GeeksforGeeks, tutorial article, 2026. Available: https://www.geeksforgeeks.org/machine-learning/cross-validation-machine-learning/
[12]
S. Bates, T. Hastie, and R. Tibshirani, “Cross-validation: What does it estimate and how well does it do it?” Journal of the American Statistical Association, vol. 119, no. 546, pp. 1434–1445, 2024, doi: 10.1080/01621459.2023.2197686.
[13]
J. Starmer, The StatQuest illustrated guide to machine learning. StatQuest Publications, 2022. Available: https://statquest.org/statquest-store/
[14]
Stanford University, “EE 278, probability and statistical inference: Fall 2024 lecture notes.” Handwritten lecture notes, Lectures 1–17, 2024. Available: http://web.stanford.edu/class/ee278/lectures.html
[15]
S. Shalev-Shwartz and S. Ben-David, Understanding machine learning: From theory to algorithms. Cambridge University Press, 2014. doi: 10.1017/CBO9781107298019.
[16]
A. Ng, “Train/dev/test sets.” DeepLearning.AI, Deep Learning Specialization, Course 2; video on YouTube, 2017. Available: https://www.youtube.com/watch?v=1waHlpKiNyY