Before any algorithm: a precise statement of the problem all of them are trying to solve. Risk, empirical risk, hypothesis classes, and the single rule that separates real machine learning from fooling yourself.
There is a world. It produces pairs \((\vx,y)\): a house and its price, an image and its label, a sentence and its next word. We model that world as a fixed but unknown probability distribution \(\mathcal{D}\) over \(\mathcal{X}\times\mathcal{Y}\).
We are given a finite sample from it:
\[S = \big\{(\vx_1,y_1),\dots,(\vx_n,y_n)\big\} \;\sim\; \mathcal{D}^n \quad\text{(independent draws)},\]
and we must produce a function \(f:\mathcal{X}\to\mathcal{Y}\) that will do well on future draws from \(\mathcal{D}\) that we have never seen. That last clause is the entire problem. Fitting the data we have is easy — a lookup table does it perfectly.
A loss function \(\ell(\hat y, y)\ge0\) measures how bad a prediction is. The true risk (or generalisation error, or expected loss) of a function \(f\) is
\[ R(f) \;=\; \E_{(\vx,y)\sim\mathcal{D}}\big[\ell(f(\vx),\,y)\big]. \]The empirical risk (or training error) on the sample \(S\) is
\[ \hat R_S(f) \;=\; \frac1n\sum_{i=1}^{n}\ell\big(f(\vx_i),\,y_i\big). \]Empirical risk minimisation (ERM) is the strategy of choosing \(\hat f = \argmin_{f\in\mathcal{H}} \hat R_S(f)\), where \(\mathcal{H}\) is a set of candidate functions called the hypothesis class.
Three things are worth pinning down straight away, because almost every confusion in the subject is a confusion between them.
Suppose you generate 1000 random functions with no relationship to the data whatsoever, and pick the one with lowest training error. Its training error will look impressive. Its true risk is exactly what a random function's should be. You did not find a good function — you found the luckiest one, and you measured its luck rather than its quality. Every model selection procedure is a milder version of this, and everything in Phase C is machinery for bounding how much you fooled yourself.
Why restrict to a class \(\mathcal{H}\) at all? Why not search over all functions?
Because searching over all functions gives you the lookup table: the function that returns \(y_i\) at each \(\vx_i\) and anything at all elsewhere. It achieves \(\hat R_S=0\) and tells you nothing about new points. There are infinitely many functions consistent with any finite dataset, and they disagree everywhere else.
Averaged over all possible data-generating distributions, every learning algorithm has the same expected off-training-set error. No algorithm is universally better than any other — including "predict at random".
What this does and does not mean. It does not mean all algorithms are equally good in practice: real problems are not drawn uniformly from all possible problems. It means that whatever advantage an algorithm has comes from assumptions it makes about which functions are plausible, and those assumptions can be wrong. There is no assumption-free learning.
The inductive bias of a learning algorithm is the set of assumptions it uses to generalise beyond the training data. Choosing \(\mathcal{H}\) is the most explicit form of it.
Read that list again as a list of claims about the world, because that is what it is. Model selection is choosing which claim you believe. When a model underperforms, the first question is not "which hyperparameter should I tune" but "is my inductive bias wrong for this problem".
There are exactly three jobs, and conflating any two of them corrupts your estimate.
Four ways people leak test information without noticing. Each of these is common, and each silently inflates the reported number.
This figure explains several things at once, and they are all the same thing.
That last block is a habit worth forming permanently. A test-set number without an uncertainty is not a result. With \(n_{\text{test}}\) points, the standard error of your metric is roughly \(s/\sqrt{n_{\text{test}}}\) — by Phase A Lecture 13 — and two models whose intervals overlap have not been distinguished. A great deal of reported "improvement" in applied work is one model beating another by less than a standard error.
For each scenario, name what is wrong and how to fix it.
1. Preprocessing leak. The training-set transformation has absorbed information
about the test inputs. The effect is usually small for standardisation with large \(n\), but it is unbounded
in general — imputation, PCA and target encoding leak far more. Fix: split first; fit every
transformation on the training split; apply the fitted transformation to validation and test. In
scikit-learn, put every step in a Pipeline so this is enforced structurally rather than by
memory.
2. Group leak. Images of the same patient appear on both sides, so the model can succeed
by recognising the patient rather than the pathology. Reported accuracy will be far above what it achieves on
a new patient — the only thing anyone cares about. Fix: split by patient
(GroupKFold/GroupShuffleSplit), never by image.
3. Selection bias, and no test set. With \(n_{\text{val}}=60\) the standard error of each estimate is large, and the minimum over 40 noisy estimates is systematically optimistic — exactly the second figure above. Fix: hold out a genuine test set touched once; use \(k\)-fold cross-validation instead of a single small validation split (Lecture 07); and try fewer configurations, or use a search method that accounts for the noise.
4. Temporal leak. A random split trains on Wednesday and Friday to predict Thursday. The model exploits information from the future, which it will not have at deployment. This is the single most common way financial and forecasting results are inflated. Fix: split chronologically — train on the past, test on the future — and use rolling-origin or walk-forward validation. Be careful too with features computed over windows that straddle the boundary.
Prove that for a fixed \(f\) chosen independently of \(S\), \(\E_S[\hat R_S(f)] = R(f)\).
Then explain precisely which step of your proof fails when \(f=\hat f\) is chosen by minimising \(\hat R_S\) over a class \(\mathcal{H}\).
Proof. The sample is \(n\) independent draws from \(\mathcal{D}\), so by linearity of expectation (Phase A Lecture 13 — no independence needed for this step):
\[\E_S\big[\hat R_S(f)\big] = \E_S\left[\frac1n\sum_{i=1}^n \ell(f(\vx_i),y_i)\right] = \frac1n\sum_{i=1}^n \E_{(\vx_i,y_i)\sim\mathcal{D}}\big[\ell(f(\vx_i),y_i)\big] = \frac1n\cdot n\cdot R(f) = R(f). \qquad\blacksquare\]Where it fails. The step \(\E[\ell(f(\vx_i),y_i)]=R(f)\) requires \(f\) to be a fixed function — one that does not depend on \((\vx_i,y_i)\). If it did, the loss term and the sample point are dependent random variables and the expectation of the term is not \(R(f)\).
When \(\hat f = \argmin_{f\in\mathcal{H}}\hat R_S(f)\), the chosen function depends on every point of \(S\). The estimator has been steered towards whatever happened to be easy in this particular sample, so
\[\E_S\big[\hat R_S(\hat f)\big] \;\le\; \min_{f\in\mathcal{H}} R(f) \;\le\; \E_S\big[R(\hat f)\big],\]where the first inequality holds because \(\hat R_S(\hat f) \le \hat R_S(f^\star)\) for the best fixed \(f^\star\), and taking expectations preserves it. Training error is biased downwards, and the size of the bias grows with how much freedom \(\mathcal{H}\) gave the minimiser.
Bounding \(\sup_{f\in\mathcal{H}}|R(f)-\hat R_S(f)|\) — uniformly over the class, so it holds for whichever \(f\) gets selected — is exactly the programme of Phase C, and it is where VC dimension and Rademacher complexity come from.
The Bayes-optimal predictor minimises \(R(f)\) over all functions.
1. Condition on \(\mX\) and use the tower property \(\E[Z]=\E[\E[Z\mid\mX]]\):
\[R(f) = \E\big[(f(\mX)-Y)^2\big] = \E_{\mX}\Big[\ \E_{Y\mid \mX}\big[(f(\vx)-Y)^2\big]\ \Big].\]For each fixed \(\vx\), the inner expectation is a function of the single number \(c=f(\vx)\), and by Phase A Lecture 13's exercise the constant minimising \(\E[(c-Y)^2]\) is \(c=\E[Y]\) — here \(\E[Y\mid\mX=\vx]\). Since we may choose \(f(\vx)\) independently at every \(\vx\) (we are optimising over all functions), minimising the inner expectation pointwise minimises the outer one. Hence \(f^\star(\vx)=\E[Y\mid\mX=\vx]\). ∎
2. Substituting, the inner minimum value is \(\E[(Y-\E[Y\mid\vx])^2\mid \mX=\vx] = \Var(Y\mid \mX=\vx)\). Averaging over \(\vx\),
\[R(f^\star)=\E_{\mX}\big[\Var(Y\mid \mX)\big].\]This is the irreducible error or Bayes risk: the part of \(Y\) that \(\mX\) simply does not determine. No model, no amount of data, and no amount of compute can go below it. ∎
3. In the code, \(y = \vx^\top\vw + \epsilon\) with \(\epsilon\sim\mathcal{N}(0,1)\) independent of \(\vx\). So \(\E[Y\mid\mX=\vx]=\vx^\top\vw\) — the true linear function is the Bayes-optimal predictor — and \(\Var(Y\mid\mX)=1\) everywhere, giving Bayes risk \(=1.0\).
So a test MSE of 1.0 is perfect, and the printed value slightly above it is the whole story of how much estimation error remains. This is why the code prints the noise level: knowing the floor turns a meaningless number into a diagnosis. On real data you never know the floor, which is why "is 0.9 MSE good?" is an unanswerable question without context — and why comparing against a strong baseline is the practical substitute.
Coding. Quantify the selection bias from the second figure.
import numpy as np
rng = np.random.default_rng(0)
sigma, reps = 1.4, 20000
print(f"{'K':>6} {'m':>6} {'empirical':>11} {'sqrt(2lnK)/sqrt(m)':>20}")
for K in (1, 5, 20, 100, 1000):
for m in (50, 500, 5000):
se = sigma/np.sqrt(m)
scores = 1.0 + se*rng.normal(size=(reps, K))
emp = 1.0 - scores.min(axis=1).mean()
theory = sigma*np.sqrt(2*np.log(K))/np.sqrt(m) if K > 1 else 0.0
print(f"{K:6d} {m:6d} {emp:11.5f} {theory:20.5f}")2 & 3. Typical results with \(\sigma=1.4\):
The \(\sigma\sqrt{2\ln K}/\sqrt m\) approximation overshoots by roughly 15–30% (it is an asymptotic upper bound on the expected maximum, and the true expectation is a little smaller), but it captures both scalings exactly: bias grows like \(\sqrt{\ln K}\) and shrinks like \(1/\sqrt m\).
4. Setting \(\sigma\sqrt{2\ln 1000}/\sqrt m = 0.01\) gives \(\sqrt m = 1.4\times 3.717/0.01 = 520\), so \(m \approx 2.7\times10^{5}\). Empirically it is a bit less, around \(1.5\times10^{5}\), but the order of magnitude stands: you need a validation set in the hundreds of thousands before you can trust the best of a thousand candidates to a hundredth of a unit.
The practical reading. Note the two dependencies are very different. The \(\sqrt{\ln K}\) is gentle — going from 10 candidates to 1000 only doubles the bias — so broad hyperparameter search is not catastrophic. The \(1/\sqrt m\) is the binding constraint: a small validation set is what makes selection dangerous. Given a fixed data budget, moving points from training into validation reduces selection bias but increases estimation error. Cross-validation (Lecture 07) exists to get both, by reusing every point in both roles.
Next: the first algorithm. Linear regression is where Phase A Lecture 10's normal equations become a working model — with feature engineering, polynomial bases, and the first honest look at when a linear model is and is not the right inductive bias.