Why does training error fall monotonically as capacity grows while test error is U-shaped?

## Two curves, drawn against the same x-axis Put capacity on the horizontal axis - polynomial degree 1, 2, 3, ..., 15 fitted to the same 60 apartment-rent listings, or tree depth 1, 2, 3, ..., 30 on the same 5,000 listings. Plot two things: the error the fitted model achieves on the listings it was fitted to, and the error it achieves on listings held back. They behave completely differently, and understanding why is the core of this topic. ## Why training error only goes down The argument is a containment argument, not a statistical one. Suppose the classes are **nested**: every function expressible at degree 5 is also expressible at degree 6 (set the extra coefficient to zero); every partition a depth-3 tree can make is also available to a depth-4 tree. Now the fitting procedure minimises training loss over the class. Moving to the larger class hands the optimiser a superset of the options it already had, so the minimum it can reach is at least as good. Therefore minimum training error is non-increasing as capacity grows, and in practice strictly decreasing because the extra freedom is almost always worth a little on the sample at hand. Push this to the extreme and training error reaches zero: with 60 listings, a polynomial of degree 59 can in general pass exactly through all of them, and a tree grown until every leaf holds one listing reproduces the training set perfectly. Perfect training error is not an achievement; it is what unlimited capacity does by construction. Two caveats a good answer includes. First, the monotonicity needs nesting - comparing two *different* families (a shallow tree against a linear model) gives you no such guarantee. Second, it needs the optimiser to actually reach the minimum; with a procedure that stops early or gets stuck, a larger class can come out slightly worse on the training data. ## Why test error turns around Held-out error is not measured on the data that was optimised, so the containment argument does not apply to it. Instead two effects run in opposite directions as capacity grows: - **Systematic error falls.** A larger class contains functions closer to the true relationship, so the best-case approximation improves. On the rent data, moving from a straight line to a gentle curve genuinely captures how price per square metre changes with size. - **Sensitivity to the sample rises.** A larger class can fit the particular 60 listings you drew - the odd landlord, the mistyped floor area. Draw a different 60 listings and you get a visibly different curve. That instability is error on new data even when the class is, on average, well-centred. Early on, the first effect is large and the second is small, so held-out error drops. Later, the class is already rich enough to express the pattern, so there is little systematic error left to remove, while every extra degree of freedom adds instability. The curve bottoms out and rises. The minimum is the capacity you want, and its location is a property of *this* dataset, not a universal constant. ## The consequence that matters in practice Because the training curve falls monotonically, it has no minimum to read off. Choosing capacity by training error always selects the largest class you offered it. This is precisely why a held-out estimate exists at all: it is the only one of the two curves that has an interior minimum to find. Any workflow that tunes a capacity dial while looking at training numbers is not tuning anything - it is just walking to the right-hand edge of the plot. ## Reading the gap The vertical distance between the two curves is informative on its own. - **Small gap, both errors high** - you are left of the minimum; the class is too restrictive. - **Large gap, training error near zero** - you are right of the minimum; the fit is tracking sample-specific structure. - **Small gap, both errors low** - you are near the bottom. A warning about that last case: a small gap is not proof of a good model if the held-out split is not really independent - duplicated listings, or the same building appearing on both sides of the split, will shrink the gap for reasons that have nothing to do with capacity. ## What the classical picture assumes The U-shape as described assumes you fit each capacity setting to convergence on a fixed sample and evaluate on data from the same distribution. It is a statement about the sample size you have: with more data the curve's minimum sits further right, and the whole held-out curve sits lower. It is not a claim that some absolute degree or depth is universally correct.