Why training error lies

Six patients tried a new treatment, and the clinic recorded for each of them whether the treatment worked: yes, no, yes, yes, no, yes. A rule that answers yes for every patient gets four of the six right, while a rule that keeps a lookup table of the six recorded answers gets all six right. Which of the two competing rules would you trust with the next patient who walks in?

The lookup table wins on the only evaluation it has ever seen, because a model here is any rule that turns a row's inputs into an answer, and fitting it means choosing its details from rows you hold. That score is the training set score, meaning the score on the rows the model was fitted to, the rows whose answers set its details, computed on the same six answers that built the table. It is optimistic by construction, because the table was assembled by reading those answers and nothing else, and the section question concerns exactly how large that optimism can become. !Two curves against model flexibility. The training error falls without exception as the model gains freedom, while the test error falls on the rigid side, reaches a minimum, and rises as the model begins to fit noise. The vertical distance between the curves is the optimism of the training score. It is smallest near the bottom of the U and widens to the right, where a model can drive its training error to zero while its test error climbs. The figure is schematic: the curves are drawn to show the shapes, not measured. Status: schematic.

The short answer is the gap between the two scores: the copying rule is wrong zero times on the six rows it saw and twice on six new rows, so its optimism is 2/6. The chapter asks how we know a model will work on new data, and the first step is to stop scoring a model on its own homework.

Two averages matter, and they differ in which rows they use. The empirical risk R-hat is the average loss over the n rows you hold, a set written D. Each row adds a cost ell that compares the recorded answer, the label, with the predictor's answer y-hat on that particular row. The predictor is the fitted model, and the hat marks a value the model produced rather than one you recorded.

$${\hat{R}}_D=\frac{1}{n}\sum _{i=1}^n\ell (y_i,{\hat{y}}_i).$$

The expression says that you accumulate the cost of every individual answer on the rows you hold and then divide the total by the number of rows. The subscript $D$ names the set of rows, the index $i$ names one row, $n$ is how many rows there are, the hat marks an estimate, and the sum runs from row 1 to row $n$.

The true risk R is the same average taken over the population the model will meet, meaning every row it could ever be asked about rather than the rows in one clinic. You cannot compute it, because you do not hold that population, so you estimate it on rows the model did not see during fitting. That is why a test set is kept apart from the rows used to fit the model [S:50:41]. The training average is straightforward to compute, and the test average is the one we actually care about, because it describes the answers the model will actually give next [S:50:41].

A model can drive its empirical risk to zero and still be completely useless, because one free parameter per row — one number the fitting is free to set — is enough to memorise every individual label. Statisticians call this overfitting: a small training error that comes with a large test error [S:50:43]. Almost every learning method aims, directly or indirectly, at a small training error, so the training number is usually the smaller of the two even when nothing has gone wrong [S:50:43].

The resulting pattern is regular enough to remember as a shape rather than as a formula, but the shape is not the whole curve. While the model is still too small to fit the rows, gaining flexibility — the range of shapes the model can take — lowers the training error while the test error traces a U [S:50:43]. The left arm of the U is underfitting, where the model is too rigid to follow the genuine relationship in the data rather than its noise. The right arm is overfitting, where the model is free enough to explain noise. The bottom is the amount of freedom that pays for itself on new rows, meaning the point where extra flexibility buys more accuracy on new rows than it costs.

Once the model is large enough to fit every training row, the U stops describing what happens: further increases in size can lower test error again [S:311:2]. A reader who treats the U as universal will reject the larger model that would have done better.

Think of a student who memorises last year's exam answers and then meets a new paper. The comparison breaks at the point that matters, because a student can also learn the subject, while a lookup table has no subject to learn. Its only knowledge is the rows it was given, and that knowledge expires the moment the rows change.

Worked example. Here are the six rows as a table, with the two rules beside them.

Rule A answers yes every time, and rule B copies the recorded answer for each patient. On these rows A is wrong twice, so its training error is 2/6, or one in three, while B is wrong zero times.

Now apply both rules to six new patients whose recorded answers are yes, yes, no, yes, no, yes. Rule A is wrong twice, and rule B has no row to copy, so it falls back on the majority answer in its table, which is yes, and it is wrong twice as well. Training error ranked the two rules, and the new rows tied them.

Rule B's optimism is the discrepancy between its two scores: zero on the rows it memorised and 2/6 on new rows, a gap of one in three. Rule A's gap is zero, because its rule did not change when the data did, and a score reported without the gap hides the difference that matters most to the patient.

The fix is not free, and its cost shapes the rest of the chapter. A held-out score is one sample from the scores you would get by holding out different rows. With six new rows, a single extra error therefore moves the estimate by 1/6, and a different selection of six rows would move it again. Holding rows back also costs training data, which matters when rows are scarce.

The next section turns that cost into a method, and the sections after it measure how large the uncertainty of such an estimate really is. Every estimate of test performance in this section is therefore an estimate of a quantity nobody can observe directly; the training error is not, because you compute it from the rows you hold. The remainder of the chapter is about making the test-performance estimates honest.

The formal statement. Fix the rows $D$ you hold, with $n$ of them, and a predictor $h$. The empirical risk averages the loss over those rows, and the true risk averages it over the population, so the gap between them is the quantity the section is about [S:64:247]. For a predictor fixed before you see the rows, Hoeffding's inequality bounds that gap with probability at least $1-\alpha$. The bound is

$$R(h)-{\hat{R}}_D(h)\le \sqrt{\frac{\log (1/\alpha )}{2n}}.$$

The line says that, with probability at least $1-\alpha$, the true risk exceeds the empirical risk by at most that amount: the empirical risk underestimates the true risk by no more than the bound, and the bound shrinks like the reciprocal of the square root of the number of rows [S:59:120]. It does not say that the predictor sits above its true risk; the true risk is the predictor's risk, and the inequality compares an estimate with the quantity it estimates.

The derivation. Normalise the loss to lie in $[0,1]$ and take the rows independent. Hoeffding's inequality then bounds the chance that a sample average departs from its mean by $\exp (-2n{\epsilon }^2)$ [S:59:118]. Set that equal to $\alpha$ and solve for the deviation, and the line above follows. For a loss bounded in $[a,b]$ instead, the right-hand side is multiplied by $b-a$, and dependent rows need a different argument. The step I omit is the one that makes the bound apply to your model. Your predictor was chosen using $D$, so the calculation covers one fixed predictor and not the winner of a search, which is exactly where it stops applying [S:59:120].

The edge case. L1 draws the U only while the model is too small to fit the rows. Once the model can interpolate, so that training error reaches zero, further increases in size can lower test error again [S:311:2]. The right arm of the U is therefore not the end of the curve, and a reader who forgets the qualification will reject the larger model that would have done better.

What L1 hid. L1 treated the gap as a property of a model. It is a property of a model and a set of rows, and the expected gap of the model you selected is larger than the gap of a model fixed in advance, because selection favours candidates whose training error is unusually low; on one dataset the realized gap can be smaller or larger. For best-subset selection of $d$ inputs from $p$ under squared error, the effective number of parameters exceeds $d$ [S:64:250]. A general search inflates the optimism by an amount that depends on its size and structure, so the count of fitted parameters stops measuring complexity once you have selected. L1 was safe because it compared two rules on one table with no search over a family.

Where the analogy breaks. The student analogy suggests that memorising and learning sit on one scale of effort. The formal object has no such scale. A lookup table is a function with one free value per row, and its gap is a statement about a sampling distribution. The analogy also suggests that the student who memorised could have chosen otherwise, while the fitting rule fixes what the table does.

Original sources. The formal home of the section's idea is the optimism of the training error. Hastie, Tibshirani and Friedman define the optimism as the difference between the in-sample error and the training error [S:64:248]. They state that a fitting method adapts to its rows, so the training error is an overly optimistic estimate of the generalization error [S:64:247]. Hardt and Recht define the gap and derive its rate from Hoeffding's inequality [S:59:120]. The corpus does not name an earlier origin for the distinction, so the text should not claim one.

An open question. The field has not settled why overparameterised networks generalise. Zhang and colleagues train standard architectures on randomly permuted labels and reach zero training error, while test error is no better than chance, and they report that the usual complexity measures do not explain the gap [S:303:2]. Double descent adds a second puzzle, because past the interpolation threshold test error falls as the model grows [S:311:2]. A candidate answer is a complexity measure computed from the fitted model that predicts test error across architectures, datasets and training times. Evidence that would settle it: a measure fixed before the test set is scored, whose predictions hold on models it was not fitted to.

A frontier result. Double descent is the frontier result that depends on this section's idea. It is a statement about the shape of test error as model size grows, and it can be stated only once training error and test error are kept apart [S:311:2]. The practical consequence is that the U-shaped curve is a local picture rather than a law, and that a larger model is not automatically a worse one.

What to read next. Read Hastie, Tibshirani and Friedman §7.4 for the definition of optimism and §7.5 for the corrections built on it [S:64:247]. Then read Hardt and Recht's chapter for the stability view and the Hoeffding calculation [S:59:120] [S:59:122]. For the modern puzzle, read Zhang and colleagues for the random-label experiment [S:303:2] and Nakkiran and colleagues for double descent [S:311:2].