Advanced28 min

Empirical Risk Minimisation

True risk versus empirical risk, why we optimise a proxy, and the approximation–estimation decomposition.

Assumes you know

Formulating a Learning Problem

Empirical Risk Minimisation

Intuition first

You want a model that does well on data it has never seen. You cannot measure that. So you measure the next best thing — error on the data you have — and minimise it, hoping the two track each other.

They do track each other, but only up to a point, and the gap between them behaves in a specific and predictable way. It widens when your model is more flexible, narrows when you have more data, and — crucially — the act of choosing the model by minimising training error is itself what creates the gap.

That last part is the subtle bit and worth stating carefully: training error is an honest estimate of test error for a model chosen in advance, and a dishonest one for a model chosen by looking at the training data. Since we always do the latter, training error is always optimistic.

Notation used in this lesson
Symbol	Meaning	Read aloud
R(h)	True risk: expected loss over the whole distribution	risk of h
R̂(h)	Empirical risk: average loss on the sample	R hat of h
ℋ	Hypothesis space	script H
ĥ	The hypothesis ERM selects from the sample	h hat
h*	Best hypothesis in ℋ (lowest true risk)	h star
f*	The best possible predictor, ignoring ℋ — the Bayes optimum	f star

The principle

\hat{h} = \argmin_{h \in \mathcal{H}} \; \hat{R}(h), \qquad \hat{R}(h) = \frac{1}{n}\sum_{i=1}^{n} L\big(y_i, h(x_i)\big)

This is what every supervised learning algorithm in this curriculum does. Linear regression solves it in closed form; a neural network approximates it with gradient descent; a decision tree greedily approximates it by splitting. The differences are in $\mathcal{H}$ and in the optimisation method, not in the principle.

The three-way error decomposition

Compare our learned model against the best achievable predictor:

\underbrace{R(\hat{h}) - R(f^*)}_{\text{total excess error}} = \underbrace{\big[R(\hat{h}) - R(h^*)\big]}_{\text{estimation error}} + \underbrace{\big[R(h^*) - R(f^*)\big]}_{\text{approximation error}}

Approximation error is the price of restricting to $\mathcal{H}$ . If the truth is a sine wave and $\mathcal{H}$ contains only straight lines, no amount of data removes this term. It depends on $\mathcal{H}$ alone, not on the sample.

Estimation error is the price of having finite data — we picked $\hat h$ instead of the genuinely best member $h^*$ because we could only see $n$ examples. It shrinks as $n$ grows and grows as $\mathcal{H}$ becomes richer.

Enlarging the hypothesis space reduces what you cannot represent and increases what you cannot reliably estimate. Total error is minimised somewhere in between.

Why empirical risk is optimistically biased

The optimism of the minimumAdvanced

For a fixed hypothesis $h$ chosen before seeing data, empirical risk is unbiased:

\E_S\big[\hat{R}(h)\big] = R(h)

because $\hat R(h)$ averages $n$ i.i.d. terms each with mean $R(h)$ .

Now consider the minimum over a finite set $\mathcal{H} = \{h_1, \dots, h_m\}$ . For every $j$ ,

\min_{k} \hat{R}(h_k) \leq \hat{R}(h_j)

Take expectations — the inequality survives — and then choose $j$ to be the index of $h^*$ :

\E_S\Big[\min_k \hat{R}(h_k)\Big] \leq \E_S\big[\hat{R}(h^*)\big] = R(h^*)

So the smallest training error we observe is, on average, below the true risk of the best hypothesis. The minimum of noisy estimates is biased downward, because minimisation preferentially selects whichever hypothesis got lucky on this particular sample.

The size of that luck grows with $m$ . If the $\hat R(h_k)$ were independent with standard deviation $\sigma/\sqrt{n}$ , the expected minimum of $m$ such estimates sits roughly $\sigma\sqrt{2\ln m}/\sqrt{n}$ below the mean. Two consequences read straight off that expression:

The optimism grows like $\sqrt{\ln m}$ — more candidate models, more self-deception.
It shrinks like $1/\sqrt{n}$ — more data, less self-deception.

This is why the same model comparison that looks decisive on 200 examples is meaningless, and on 200,000 examples is trustworthy.

Uniform convergence, informally

For ERM to work we need the training error to approximate the true error simultaneously for every hypothesis in $\mathcal{H}$ — not just for one. That condition is called uniform convergence:

\sup_{h \in \mathcal{H}} \big\lvert \hat{R}(h) - R(h) \big\rvert \;\leq\; \epsilon

If it holds, then minimising $\hat R$ cannot be far from minimising $R$ .

Why uniform convergence implies ERM is nearly optimalAdvanced

Suppose the supremum above is at most $\epsilon$ . Then for our selected $\hat h$ and the true best $h^*$ :

R(\hat{h}) \leq \hat{R}(\hat{h}) + \epsilon \qquad\text{(uniform convergence applied to } \hat h)

\hat{R}(\hat{h}) \leq \hat{R}(h^*) \qquad\text{(because } \hat h \text{ minimises } \hat R)

\hat{R}(h^*) \leq R(h^*) + \epsilon \qquad\text{(uniform convergence applied to } h^*)

Chaining the three:

R(\hat{h}) \;\leq\; R(h^*) + 2\epsilon

So ERM's estimation error is at most twice the uniform-convergence gap. The whole project of statistical learning theory is bounding $\epsilon$ in terms of $n$ and a complexity measure of $\mathcal{H}$ — which is what VC dimension provides.

Surrogate losses

The loss we care about is often unusable for optimisation. Classification accuracy corresponds to the 0–1 loss, which is discontinuous and has zero gradient everywhere it is defined — gradient descent cannot move.

So we minimise a surrogate: a differentiable loss that upper-bounds or approximates the one we want.

Target	Surrogate used for fitting	Why
0–1 loss	Logistic / cross-entropy	Convex, smooth, calibrated probabilities
0–1 loss	Hinge	Convex, margin-maximising
Ranking quality	Pairwise logistic	NDCG is not differentiable
Accuracy on imbalanced data	Weighted cross-entropy	Reweights the rare class

Solved problem 1 · Quantifying the optimism

A team fits 50 candidate models on $n = 400$ examples and reports the best training accuracy, 0.93. The standard deviation of the 0–1 loss for a single example is approximately $0.5$ for models around this accuracy. Estimate the optimism, and say what the honest expected test accuracy is.

Step 1 — standard error of one model's training estimate

\text{SE} = \frac{\sigma}{\sqrt{n}} = \frac{0.5}{\sqrt{400}} = \frac{0.5}{20} = 0.025

Step 2 — expected downward bias of the minimum over 50 models

Using the approximation from the derivation above:

\text{optimism} \approx \text{SE} \times \sqrt{2 \ln m} = 0.025 \times \sqrt{2 \ln 50}

\ln 50 \approx 3.912 \quad\Longrightarrow\quad 2\ln 50 \approx 7.824 \quad\Longrightarrow\quad \sqrt{7.824} \approx 2.797

\text{optimism} \approx 0.025 \times 2.797 \approx 0.070

Step 3 — corrected expectation

\text{expected test accuracy} \approx 0.93 - 0.07 = 0.86

Step 4 — sanity-check the direction and scale

The correction must be downward, and it is. Note how large it is: seven accuracy points of the reported 93% are an artefact of trying 50 models on 400 examples.

If the same search were run on $n = 40{,}000$ , the standard error would fall by a factor of 10 to $0.0025$ , and the optimism to about $0.007$ — under one point.

Answer

Roughly 7 points of optimism; honest expectation about 0.86, not 0.93. The fix is not a correction formula but a held-out set that the model search never saw.

ERM in six lines

Nothing is hidden inside a library here — this is the principle, literally:

python

import numpy as np

def empirical_risk(h, X, y, loss):
    """R̂(h) — mean loss over the sample."""
    return np.mean([loss(yi, h(xi)) for xi, yi in zip(X, y)])

def erm(hypotheses, X, y, loss):
    """Pick the hypothesis with the lowest empirical risk."""
    return min(hypotheses, key=lambda h: empirical_risk(h, X, y, loss))

squared = lambda y, yhat: (y - yhat) ** 2

X = np.array([1.0, 2.0, 3.0, 4.0])
y = np.array([2.1, 3.9, 6.2, 7.8])          # roughly y = 2x

candidates = [lambda x, s=s: s * x for s in (1.5, 1.9, 2.0, 2.1, 2.5)]
best = erm(candidates, X, y, squared)
print(f"chosen slope ≈ {best(1.0):.2f}")     # 2.00
print(f"training risk = {empirical_risk(best, X, y, squared):.4f}")

Every training loop later in this curriculum replaces the explicit list of candidates with a continuous parameter space and the min with gradient descent. The principle does not change.

Exercise 1

A model achieves 0.02 training error and 0.31 test error. Which term of the decomposition is large, and what are two concrete remedies?

Show solution

Estimation error. The model can clearly represent the training data — approximation error is near zero, since training error is 0.02 — but it has fitted sample-specific noise, so the gap to true risk is enormous.

Two remedies, both targeting estimation error:

Shrink $\mathcal{H}$ — regularisation, fewer parameters, shallower trees, stronger weight decay. Accepts a little approximation error to buy a large reduction in estimation error.
Increase $n$ — more data, or augmentation. Estimation error shrinks like $1/\sqrt{n}$ while approximation error is untouched, so this dominates the first option when data is obtainable.

What will not help: a more flexible model, a longer training run, or a different optimiser. Those all reduce training error, which is already 0.02.

Exercise 2

Both training and test error are 0.30. Diagnose, and explain why more data will not help.

Show solution

Large approximation error — underfitting. The near-zero gap between training and test error shows estimation error is small, so the model is not chasing noise. It simply cannot represent the underlying relationship.

More data will not help because approximation error, $R(h^*) - R(f^*)$ , depends only on $\mathcal{H}$ . Even with infinite data ERM converges to $h^*$ , whose risk is already 0.30 above the optimum.

The remedy is a richer $\mathcal{H}$ : more features, interaction or polynomial terms, a kernel, a deeper model. First, though, check the irreducible noise floor — if the Bayes error genuinely is 0.30, the model is already optimal and nothing will improve it.

Next: Generalisation, Overfitting and Underfitting, which turns this decomposition into the diagnostic curves you will actually read off a training run.