Training Error vs Test Error

Fix a loss function $\ell(y, \hat y)$ that penalizes a prediction $\hat y$ against a true label $y$ — squared error for regression, 0/1 loss for classification. The learning problem assumes an unknown data-generating distribution $\mathcal D$ over pairs $(x, y)$, from which we observe a finite training set $S = \{(x_1,y_1), \dots, (x_n,y_n)\}$ drawn i.i.d. from $\mathcal D$. For a hypothesis $h$ drawn from a hypothesis space $\mathcal H$, define two risks. The true risk (also called expected risk or generalization error) is the quantity we actually care about:

This is an expectation over the entire population, most of which we will never see. It cannot be computed exactly because $\mathcal D$ is unknown. The empirical risk on a sample $S$ is the quantity we can compute:

When $S$ is the training set used to select $h$, $\hat R_S(h)$ is called the training error. Learning algorithms typically work by empirical risk minimization (ERM): choose $\hat h = \arg\min_{h \in \mathcal H} \hat R_S(h)$. This is the natural strategy since $R(h)$ itself is inaccessible — but it has a subtle consequence. Because $\hat h$ was selected to minimize error on $S$, the training error $\hat R_S(\hat h)$ is a biased estimator of $R(\hat h)$: in expectation, $\hat R_S(\hat h) \le R(\hat h)$. The hypothesis is fit to the noise and idiosyncrasies of the particular sample, not just the underlying signal. Test error solves this by evaluating $\hat h$ on a second sample $S'$, drawn from the same $\mathcal D$ but disjoint from and untouched during the fitting of $\hat h$:

Because $S'$ played no role in choosing $\hat h$, this is an unbiased estimate of $R(\hat h)$: $\mathbb{E}_{S'}[\hat R_{S'}(\hat h)] = R(\hat h)$, treating $\hat h$ as fixed. This single distinction — was the data used to choose the hypothesis, or only to evaluate it — is the entire content of the training/test error dichotomy.

Measuring training and test error is procedurally simple, but the discipline lies in never letting information flow the wrong direction — from the test set into model fitting or model selection.

Step 1 — Split the data. Partition the available labeled data into a training set $S_{\text{train}}$ and a test set $S_{\text{test}}$, drawn (or assumed) i.i.d. from the same distribution $\mathcal D$. A common split is 70–90% train, 10–30% test; the test set must be large enough that its own sampling noise doesn't swamp the signal you're trying to measure.

Step 2 — Fit on training data only. Run the learning algorithm (ERM, gradient descent, decision tree induction, whatever the model class calls for) using only $S_{\text{train}}$ to produce $\hat h$.

Step 3 — Compute training error. Evaluate $\hat h$ on $S_{\text{train}}$ itself: $\hat R_{S_{\text{train}}}(\hat h)$. This tells you how well the model fits the data it was optimized against.

Step 4 — Compute test error. Evaluate the same, frozen $\hat h$ on $S_{\text{test}}$, which it has never seen: $\hat R_{S_{\text{test}}}(\hat h)$. This is your estimate of true risk $R(\hat h)$.

Step 5 (if tuning hyperparameters) — use a validation set, not the test set. If you need to choose among several models or hyperparameters (polynomial degree, regularization strength, tree depth), do so using a third split — a validation set — or via k-fold cross-validation on the training data. The test set is touched exactly once, at the very end, to report a final unbiased number. ``` ALGORITHM TrainTestEvaluate(D, learner, loss, split_ratio):

# D: full labeled dataset drawn i.i.d. from distribution

# learner: algorithm that fits a hypothesis given data

# loss: pointwise loss function ℓ(y, ŷ) Shuffle D uniformly at random # break any ordering artifacts (S_train, S_test) ← Split(D, split_ratio) h_hat ← learner.fit(S_train) # ERM: minimize empirical risk on train ONLY train_error ← Mean( loss(y_i, h_hat(x_i)) for (x_i, y_i) in S_train ) test_error ← Mean( loss(y_i, h_hat(x_i)) for (x_i, y_i) in S_test ) return train_error, test_error

ALGORITHM KFoldCrossValidate(D_train, learner, loss, k):

# Used for model/hyperparameter SELECTION, never for the final reported number folds ← PartitionIntoKEqualParts(Shuffle(D_train), k) scores ← [] for i in 1..k: val_fold ← folds[i] train_folds ← Concatenate(folds[1..k] minus folds[i]) h_i ← learner.fit(train_folds) scores.append( Mean( loss(y, h_i(x)) for (x,y) in val_fold ) ) return Mean(scores) # cross-validation estimate of test error ``` The crucial invariant, enforced in both procedures, is: any data point used to fit $\hat h$ (directly, or indirectly through hyperparameter choice) must never be used to report its final error. Violating this — even by something as innocuous as normalizing features using statistics computed over the whole dataset before splitting — leaks test information into training and biases the reported error downward.

Time complexity. Computing either error requires one pass over the relevant set, evaluating $h$ at each point: $O(n)$ time for $|S_{\text{train}}| = n$ and $O(m)$ for $|S_{\text{test}}| = m$, each multiplied by the (model-dependent) cost of a single prediction, $c(h)$. So training-error computation is $O(n \cdot c(h))$ and test-error computation is $O(m \cdot c(h))$ — linear in the size of the evaluated set, entirely separate from the (typically much larger) cost of fitting $\hat h$ in the first place. $k$-fold cross-validation multiplies the fitting cost by $k$, since a fresh hypothesis is trained on each of the $k$ training-fold combinations; this is the classic accuracy/compute tradeoff of resampling-based model selection.

Space complexity. $O(n + m)$ to hold both splits, plus whatever space the fitted hypothesis $\hat h$ itself occupies (e.g., $O(d)$ for a $d$-dimensional linear model, or the size of a tree/network). No additional asymptotic overhead is introduced by the train/test split itself, only a constant-factor duplication consideration if both sets must be memory-resident simultaneously.

Correctness — why training error is optimistically biased. Let $\hat h_S = \arg\min_{h \in \mathcal H} \hat R_S(h)$ be the ERM hypothesis fit on sample $S$. For any fixed hypothesis $h$ (chosen independently of $S$), linearity of expectation gives

i.e., the empirical risk of a fixed hypothesis is unbiased. But $\hat h_S$ is not fixed — it is chosen adaptively, as the specific minimizer over $S$. The key inequality is

for any fixed reference hypothesis $h^\star$ (e.g., the truly-best hypothesis in $\mathcal H$), simply because $\hat h_S$ was defined as the minimizer. Taking expectations and using the unbiasedness of $\hat R_S(h^\star)$:

More directly: one can show $\mathbb{E}_S[R(\hat h_S) - \hat R_S(\hat h_S)] \ge 0$, with equality only in degenerate cases (e.g. $|\mathcal H|=1$). Intuitively, ERM exploits sampling noise in $S$ — it can find a hypothesis that fits the particular realized noise in the training sample, which will not reproduce on fresh data. The richer $\mathcal H$ is (the more hypotheses ERM can search over), the more opportunity it has to fit noise, and the larger this generalization gap

becomes. This gap is exactly bounded by the uniform-convergence tools of statistical learning theory (VC dimension, Rademacher complexity), which show the gap shrinks at a rate like $O(\sqrt{\text{complexity}(\mathcal H)/n})$ — vanishing as $n \to \infty$ for hypothesis spaces of fixed complexity, and growing when complexity scales with $n$ (as in memorizing models). This machinery formalizes the intuition behind Overfitting and Underfitting.

Why test error is unbiased. $S_{\text{test}}$ is independent of $\hat h_S$ by construction (it is disjoint from $S_{\text{train}}$ and never used in fitting or model selection). Treat $\hat h_S$ as a fixed function once it emerges from training; then $S_{\text{test}}$ is a fresh i.i.d. sample with respect to that fixed function, so

exactly, by linearity of expectation over i.i.d. draws. The price is variance: $\hat R_{S_{\text{test}}}$ is a Monte Carlo average of $m$ i.i.d. loss values, so by the standard variance-of-mean formula its standard error is $O(1/\sqrt m)$. Larger test sets give tighter, but still unbiased, estimates; smaller test sets are noisier but remain unbiased in expectation. This unbiasedness is contingent entirely on the no-peeking discipline — the moment the test set influences any modeling decision, this guarantee breaks.

Honest tradeoff. Held-out evaluation costs you data: every example spent on $S_{\text{test}}$ is one fewer example available to fit $\hat h$, which can hurt performance for small datasets. Cross-validation mitigates this by rotating the held-out role across $k$ folds, trading a $k\times$ increase in fitting compute for a training-set-sized evaluation budget — a classic statistical-efficiency-versus-computational-cost tradeoff.

Suppose we fit polynomial regression models of increasing degree $d$ to $n = 20$ noisy samples of $y = \sin(x) + \varepsilon$, $\varepsilon \sim \mathcal N(0, 0.1^2)$, then evaluate on a held-out test set of $m = 200$ fresh samples from the same generator. Mean squared error is the loss.

Reading the table: as $d$ grows, the hypothesis space $\mathcal H_d$ (degree-$\le d$ polynomials) becomes richer, and ERM drives training error monotonically toward zero — with 20 points and a degree-19 polynomial, the fit can pass through every point exactly, giving training error indistinguishable from zero. But test error is not monotonic. It decreases from $d=1$ to around $d=5$ as the model captures genuine curvature in $\sin(x)$, reaches a minimum near the true model complexity, then increases sharply as $d$ continues to grow — the polynomial starts fitting the specific noise draws in the 20 training points rather than the underlying sine curve. At $d=19$ the training error is essentially zero while the test error is enormous: a textbook case of the generalization gap predicted above, driven to its extreme. This single table is the empirical signature that later motivates the bias–variance framing of Overfitting and Underfitting: low-degree models underfit (both errors are high and close together), very high-degree models overfit (training error near zero, test error large), and the sweet spot minimizes test error, not training error. Crucially, if we had only looked at training error, we would have wrongly concluded degree 19 is the best model.

The training/test distinction is not attributable to a single inventor; it crystallized from statistics and pattern recognition as machine learning became an empirical discipline demanding honest evaluation protocols.

Every deployed machine learning system relies on the training/test distinction to decide whether it is safe to ship. Competition platforms like Kaggle enforce strict train/public-test/private-test splits precisely to prevent leaderboard overfitting — the public leaderboard behaves like a semi-repeated test set, and competitors who over-tune to it often collapse on the private leaderboard, a real-world demonstration of test-set reuse bias. Production ML pipelines at large tech companies use time-based train/validation/test splits (train on past data, test on future data) to simulate genuine deployment conditions, since randomly shuffled splits would leak future information backward in time. Regulatory and safety-critical domains — clinical diagnosis models, credit scoring, autonomous driving perception — require reported performance metrics to come from held-out data never touched during development, often with external, independently-collected test sets to guard against subtler forms of the same bias (e.g., dataset-specific artifacts). Benchmark suites in computer vision and NLP (ImageNet, GLUE, SQuAD) maintain hidden test sets with restricted submission counts, directly enforcing the "use it once" discipline this article derives from first principles. Understanding training versus test error is the prerequisite for every downstream diagnostic tool — learning curves, validation curves, early stopping — that practitioners use to detect and correct Overfitting and Underfitting before a model ever reaches production.

Ask the tutor: How does the size of the hypothesis space quantitatively control the size of the generalization gap, via VC dimension or Rademacher complexity bounds?