Overfitting, Underfitting & Capacity
Training vs. generalization error, learning curves, and double descent.
On this page
Beginner: an underfit model is too simple to capture the real pattern in the data — it does badly on the training data and on new data, because it never learned the pattern in the first place (think: fitting a straight line to something that's obviously curved). An overfit model is the opposite problem — it's flexible enough to memorize the training data almost perfectly, including its noise and one-off quirks, so it looks fantastic on the data it was trained on and then falls apart on anything new. Both are failures to generalize; they just fail in opposite directions.
Intermediate: the underlying dial being turned here is capacity — an informal but useful notion of how flexible or expressive a hypothesis class is. A straight line has low capacity: it can only ever represent one shape (a line). A 20th-degree polynomial has enormous capacity: with 21 free coefficients it can bend and twist through almost any scatter of points you hand it. Plot test error against capacity and, classically, you get a U-shape: too little capacity and the model can't represent the true pattern (underfitting, high bias); too much capacity and the model represents the training noise as if it were signal (overfitting, high variance). The bottom of the U is the capacity that actually matches the complexity of the true underlying relationship.
A concrete walk-through: pick one specific training point — say the one sitting at x = 0.4 in the diagram below, with its noisy observed value y = trueFn(0.4) + noise. At degree 1, the fitted line has nowhere near enough freedom to pass through that point exactly; it settles somewhere in the middle of the whole scatter, so this point contributes a real, nonzero residual to the training error — but the line's value near x = 0.4 is also close to the *true* curve's value there, because a low-degree fit is forced to average out this one point's noise together with all the others. Now push the degree up. Somewhere around degree 14–15 — enough free coefficients to satisfy every one of the 22 training points as an individual constraint — the curve bends specifically so it passes through (0.4, y) almost exactly, driving that point's training residual to (near) zero. That looks like a win in the training-error column. But look at what the curve had to do to get there: forcing it through this point's specific noisy value, and through every neighboring point's specific noisy value too, means the curve has to oscillate sharply between them (a Runge's phenomenon–style wiggle) rather than following the smooth true trend. So evaluate that same high-degree curve at a nearby unseen test input, say x = 0.41, and it is often far from trueFn(0.41) — sometimes worse than the low-degree line was. The model didn't get better at predicting near x = 0.4; it got better at reproducing one sample's specific noise, at the direct expense of everywhere nearby. That trade — training residual at a point down to zero, error at neighboring unseen points up — is overfitting happening at the resolution of a single data point, and it's exactly what the diagram's slider lets you watch happen in aggregate across all 22 training points at once.
Advanced: that clean U-shape was, for decades, treated as the whole story — until modern heavily over-parameterized models (deep neural networks with far more weights than training examples) started breaking it. Push capacity past the point where the model can perfectly fit every training point, and test error does first rise, exactly as the classical picture predicts — but then, past a certain point, it can start falling again, producing a second dip at extremely high capacity. This is double descent, and it is genuinely still an active area of research, not a settled textbook fact. The leading intuition (not a proof) is that once a model has more than enough capacity to interpolate the training data exactly, the specific solution the optimizer actually lands on — out of the infinitely many that fit the training data perfectly — matters. Gradient descent on very wide networks tends to land on comparatively smooth, low-norm interpolating solutions rather than wild ones, which behaves like an implicit form of regularization the classical bias-variance story never accounted for.
Why the second descent doesn't actually contradict the classical picture for the models this module is about: the classical U-shape derivation (worked through in full in the Derivation section below) leans on H = X(XᵗX)⁻¹Xᵗ being a genuine rank-p projection, which requires XᵗX to be invertible — and that in turn requires p ≤ n, more data rows than fitted parameters. Every classical model this course treats — bounded-degree polynomial regression, decision trees at any depth that still leaves multiple training rows per leaf, k-nearest-neighbors, standard kernel machines at ordinary capacity — lives comfortably inside p ≤ n, and inside that regime the U-shape isn't just a rule of thumb, it's the direct consequence of a theorem with those exact assumptions. Double descent's second dip only shows up once p is pushed past n — at which point XᵗX is singular by construction (more unknowns than equations), so "the OLS estimator" as this derivation defines it no longer exists; what a modern over-parameterized network's training procedure actually produces is a different mathematical object — informally, a minimum-norm solution selected out of an entire subspace of parameter settings that all fit the training data exactly, chosen implicitly by how gradient descent moves through that subspace. So the second descent isn't the classical theorem being violated; it's a statement about a regime (p > n, with a different estimator entirely) that the theorem's own assumptions simply don't cover in the first place — the two pictures describe two different objects, not one theory correcting another.
R(f) is the true (generalization) risk — the expected loss over the entire data-generating distribution, most of which you will never actually see. R̂(f) is the empirical risk — the average loss measured on some finite sample. When that sample is the training set itself, this gap is exactly what the Derivation below shows is optimistically biased toward zero. A learning curve plots training and test error side by side, as a function of either training-set size or capacity:
where n is the number of training examples and c is model capacity (e.g. polynomial degree, tree depth, number of parameters). Reading these two curves against each other — not either one alone — is the entire diagnostic toolkit behind "is my model underfitting or overfitting."
Take the cleanest case where this can be worked out exactly: a linear model fit by ordinary least squares. Assume the true relationship is linear in p parameters plus independent noise of variance σ²:
where X is an n×p design matrix (n training rows, p fitted parameters). The OLS fit is a projection: writing H = X(XᵗX)⁻¹Xᵗ (briefly: this is the matrix that projects any vector onto the p-dimensional column space of X — the same kind of projection operator the Linear Algebra chapter builds up when it discusses orthogonal projections and the SVD), the fitted values and residuals are:
Because H projects onto the column space of X, and Xβ already lives entirely inside that column space, applying H to it changes nothing — so (I−H)Xβ = 0. Substituting y = Xβ + ε into the residual expression, the entire Xβ term cancels and only the noise survives:
The residuals are exactly the true noise, projected onto the (n−p)-dimensional space left over once the p-dimensional column space of X is removed — the orthogonal complement of what the model was allowed to fit. The residual sum of squares is then a quadratic form in that noise:
(using that I−H is idempotent and symmetric, i.e. a genuine projection matrix, so (I−H)ᵗ(I−H) = (I−H)). Taking the expectation of a quadratic form in zero-mean noise with covariance σ²I gives σ²·tr(I−H). A projection matrix's eigenvalues are only ever 0 or 1, so its trace equals its rank — and H has rank exactly p, the dimension of the space it projects onto. So tr(I−H) = n−p, and:
That's the phenomenon in its purest form: the average squared training residual underestimates the true noise variance σ² by a factor of exactly (1 − p/n). Push p toward n — as many parameters as data points — and the training error can be driven to (almost) zero even though the model has learned nothing beyond memorizing the specific noise realized in this one sample; a fresh sample would show the same σ² all over again, unimproved.
This same degrees-of-freedom logic extends (cited here rather than re-derived in full, since it holds for any estimator that is linear in y, not only OLS) to the classical "optimism of the training error" theorem: the expected gap between true risk and training risk for such an estimator is
— training error is optimistic by an amount that grows linearly in p/n, the same ratio driving the RSS result above (the constant differs, 2 versus 1, because this version measures a covariance between the fit and the data used to produce it, rather than a plain residual variance — but the mechanism, "each extra parameter is one more degree of freedom to bend toward this sample's specific noise," is identical). This exact quantity, 2σ²p/n, is what Mallow's Cₚ and Akaike's Information Criterion add back on top of the training score to correct for it — a connection developed fully in the later Model Evaluation module, without needing to re-derive it here.
Where this is used: this is precisely why held-out validation sets and cross-validation exist at all — for anything beyond a simple linear-in-y estimator, p (the "effective" number of parameters) isn't even well-defined, so there is no formula left to correct the training score with; the only universally valid fix is to measure risk on data the fitting procedure never touched. And it's why information criteria are built the way they are: take the (optimistic) training likelihood or RSS, then explicitly subtract a penalty proportional to model complexity — exactly undoing the bias this derivation quantifies.
Watch the intro play automatically once — degree sweeping from 1 up to 15 and settling back to 5 — then drag the polynomial-degree slider yourself: the purple fitted curve straightens out at low degree (underfitting) and starts wiggling through every training dot at high degree (overfitting), while the train/test MSE readout above tracks exactly what's happening numerically.
import numpy as np
rng = np.random.default_rng(0)
# True underlying function: a smooth curve plus independent Gaussian noise.
def true_fn(x):
return np.sin(2.2 * x) + 0.3 * x
n = 60
x = rng.uniform(-1, 1, size=n)
y = true_fn(x) + 0.16 * rng.standard_normal(n)
# Manual train/test split -- no sklearn involved.
idx = rng.permutation(n)
split = int(0.7 * n)
train_idx, test_idx = idx[:split], idx[split:]
x_train, y_train = x[train_idx], y[train_idx]
x_test, y_test = x[test_idx], y[test_idx]
def design_matrix(x_vals, degree):
# Vandermonde-style design matrix: columns are x^0, x^1, ..., x^degree.
return np.column_stack([x_vals ** k for k in range(degree + 1)])
def fit_and_score(degree):
X_train = design_matrix(x_train, degree)
X_test = design_matrix(x_test, degree)
# Normal equations: (X^T X) beta = X^T y. A tiny ridge keeps this solvable
# even once X^T X becomes nearly singular at high degree.
XtX = X_train.T @ X_train + 1e-8 * np.eye(degree + 1)
Xty = X_train.T @ y_train
beta = np.linalg.solve(XtX, Xty)
train_pred = X_train @ beta
test_pred = X_test @ beta
train_mse = np.mean((train_pred - y_train) ** 2)
test_mse = np.mean((test_pred - y_test) ** 2)
return train_mse, test_mse
print(f"{'degree':>6} {'train MSE':>12} {'test MSE':>12}")
for degree in range(1, 16):
train_mse, test_mse = fit_and_score(degree)
print(f"{degree:>6} {train_mse:>12.4f} {test_mse:>12.4f}")
# Train MSE falls almost monotonically -- more parameters can only fit the
# training points better. Test MSE falls, bottoms out near the true curve's
# real complexity, then climbs back up: underfit -> good fit -> overfit,
# read directly off the printed table.- A deep, unpruned decision tree on a small tabular dataset is the textbook overfitting machine — grown deep enough, it creates a leaf for nearly every training row, achieving near-zero training error by essentially memorizing the training set row by row. On a dataset with a few hundred rows and a dozen features this happens fast, which is exactly why gradient-boosted-tree libraries default to shallow trees (depth 3–8) and why random forests average many such overfit trees together rather than trusting any single deep one.
- A linear model fit to non-linear physics — trying to predict, say, projectile trajectories (genuinely quadratic in time) with a straight-line model — is the textbook underfitting case: no amount of more training data fixes it, because the hypothesis class itself cannot represent the true relationship. More rows just make the "best possible straight line" a more precisely wrong line.
- High-degree polynomial fits to noisy sensor or calibration data — a classic trap in instrumentation and metrology. Given a scatter of noisy thermocouple or pressure-sensor readings, fitting a degree-10+ polynomial "because it hugs the data points more closely" produces a curve that oscillates wildly between calibration points (the same Runge's-phenomenon wiggle the diagram above shows directly) — a sensor calibrated this way can read badly wrong at input values just slightly off from the calibration points, which is why calibration curves in practice use low-degree polynomials or piecewise splines instead.
k-nearest-neighbors withk = 1is the cleanest possible illustration of maximal variance: the "model" is just "predict whatever the single closest training point says," so the decision boundary bends around every individual training point, including mislabeled or noisy ones, with zero smoothing. Training error is essentially zero (every training point is its own nearest neighbor), while test error is typically much higher — increasingkis, concretely, turning the same capacity dial this whole lesson is about.- Watching the validation-loss curve during training is the day-to-day practical ritual built directly on this lesson's learning-curve idea, and it isn't unique to neural networks — gradient-boosted trees, matrix factorization models, and iterative solvers of all kinds get monitored the same way. Training loss keeps falling essentially by construction; the moment the validation curve stops falling and turns upward while training loss keeps dropping, that inflection point is the U-shape's minimum being crossed in real time, made visible on a plot instead of derived on paper. Early stopping is simply the automated version of this: freeze the model's weights at that inflection point rather than continuing to optimize toward zero training loss.
- Double descent in modern, heavily over-parameterized deep networks is the one place the classical U-shape story genuinely needs revision, not just careful interpretation. These networks routinely have far more weights than training examples and still generalize well in practice — the real-world observation that motivated double descent research in the first place, since the classical story alone predicts they should overfit catastrophically once capacity crosses the interpolation threshold, and mostly they don't. As the Advanced note above and the Expert note below both stress, this isn't the classical theorem being wrong — it's a different, much higher-capacity regime that the classical derivation's own assumptions never covered.
- Judging a model by its training error alone. Training error can only ever go down (or stay flat) as capacity increases — it tells you nothing about generalization by itself, which is exactly what the Derivation above quantifies.
- Assuming "more capacity always means more overfitting." Regularization, early stopping, and the implicit bias of the optimizer itself can all keep a high-capacity model well-behaved — capacity is a ceiling on what a model could do, not a prediction of what it will do.
- Treating double descent as replacing the classical U-shaped curve everywhere. For most classical, non-deep-learning models (linear/polynomial regression, decision trees, standard kernel methods at moderate capacity) the classical U-shape is still the right mental model in practice — the double-descent wrinkle mainly matters in the heavily over-parameterized regime that deep learning operates in.
Going deeper
The point where test error peaks in a double-descent curve tends to sit right at the interpolation threshold — the exact capacity at which the model has just enough parameters to fit every training point perfectly (zero training error) for the first time. Just below that threshold, small changes in the training data can swing the fit wildly (classic high variance). Just above it, there are suddenly many different parameter settings that all achieve zero training error, and gradient-based optimizers empirically tend to land on a comparatively simple one among them — informally, something close to the minimum-norm interpolating solution — which behaves like an implicit regularizer nobody explicitly asked for.
Be honest with yourself about how settled this is: there is real theory for specific, simplified cases (linear regression in certain over-parameterized regimes, some kernel methods), and there is a large body of empirical observation in deep networks, but a complete, general theory of why and exactly when the second descent occurs is still being actively worked out. Treat the mechanism described here as the current best intuition, not a settled theorem.
Model A has 10 parameters and 0.20 training error. Model B has 10,000 parameters and 0.01 training error, trained on the same dataset. Which model is guaranteed to have lower test error?
Neither — training error alone never determines test error, which is exactly what this lesson's derivation formalizes: more parameters relative to sample size makes the training error more optimistically biased, not more trustworthy. Model B's lower training error could mean it genuinely captured more real structure, or it could mean it's simply overfitting harder (p/n is far larger for B). The only way to actually compare them is to measure both on a held-out set neither model was fit on — and even then, if B is heavily over-parameterized, its held-out error should be interpreted with the double-descent picture in mind rather than the classical U-shape alone.
Training error is not a measurement of how good your model is — it's a biased, optimistic proxy that gets more optimistic the more capacity you add relative to your sample size, which is precisely why held-out data is non-negotiable. The classical underfit-to-overfit U-shape is still the right default mental model for nearly everything you'll build; keep double descent in your back pocket as the honest caveat for the heavily over-parameterized regime, not as a reason to distrust the U-shape everywhere else.