Generalization & Overfitting
Bias, variance, regularization and validation.
A model can score perfectly on its training data and still fail on the next example. This lesson takes that gap apart: it derives the bias–variance decomposition, shows how ridge, the lasso and early stopping trade a little bias for much less variance, and turns cross-validation into an honest way to choose among models.
What you’ll learn
- Define risk, empirical risk and the generalization gap, prove that training error is optimistic on average, and split excess risk into estimation and approximation error.
- Derive the bias–variance decomposition of squared error and evaluate it for -nearest-neighbor and least-squares regression.
- Derive ridge regression in closed form, explain its shrinkage through the SVD, and contrast it with the lasso's soft thresholding.
- Run -fold cross-validation without leaks, and prove the one-fit leave-one-out formula for linear smoothers.
Risk, empirical risk and the gap
Supervised learning assumes examples drawn i.i.d. from an unknown distribution . A predictor with loss has a risk, its expected loss on new data, and an empirical risk, its average loss on the examples of the training set:
Empirical risk minimization (ERM) picks from a model class . Generalization is about the gap .
For a predictor fixed before the data are drawn, is an unbiased estimate of , which is why a fresh test set works. For it is biased downward. Let be the best predictor in . Since minimizes the empirical risk, ; since minimizes the risk, . Taking expectations,
Training error is optimistic on average, for every model class and every loss.
The bias–variance decomposition
Fix a test input and write with and . The prediction is random because the training set is, and the test noise is independent of . Write for the prediction averaged over training sets.
Expand around the truth. The cross term vanishes because has mean zero and is independent of :
Add and subtract . This cross term vanishes too, because (everything is evaluated at ):
So the expected squared error at is noise plus squared bias plus variance:
Average over to get the expected test MSE. The split is exact for squared loss; for 0–1 loss, bias and variance interact non-additively and several competing definitions exist.
The bias–variance trade-off becomes explicit when the training inputs are held fixed and only the noise is random. k-nearest-neighbor regression predicts the average label of the training inputs nearest to , so its variance is that of an average of independent noises:
Least squares with coefficients predicts with the hat matrix , a projection of rank . Its variance averaged over the training inputs is . If the model is correctly specified, the residual sum of squares has mean , so
The gap is the optimism of the training error, which Mallows' and AIC add back.
A correctly specified linear model with coefficients is fitted by least squares to points. By what percentage does its expected training MSE fall below the noise variance ?
Show the answer
33 %
: 33% below the noise level, although the model is exactly right. Four coefficients have absorbed part of the twelve noise values. On fresh labels at the same inputs the expected error is , so the optimism is .
Regularization: shrinkage, sparsity and early stopping
Regularization adds a penalty to the fit, , and trades bias for variance with one knob, the hyperparameter . Ridge regression uses , the lasso (inputs are usually standardized first, and the intercept is left unpenalized).
Set the gradient to zero. For the matrix is positive definite, so the solution exists and is unique even when :
Write the thin SVD with singular values and left singular vectors . The fitted values become a filtered expansion:
Least squares () keeps every component. Ridge multiplies component by and crushes the directions in which the inputs barely vary (small ), where coefficients are worst determined and noisiest. The trace of this linear smoother, its effective degrees of freedom, falls from at toward :
| Method | Penalty | Estimate of | Effect |
|---|---|---|---|
| Least squares | none | unbiased; largest variance | |
| Ridge | shrinks every coefficient by the same factor; none reaches zero | ||
| Lasso | soft thresholding: small coefficients become exactly zero | ||
| Best subset | at most nonzero | hard thresholding: keep the largest |
Other regularizers act implicitly. Early stopping halts gradient descent before convergence: started from it fits the large- directions first, and after steps of size it behaves much like ridge with . Dropout zeroes random units during training; for linear regression its expected loss is exactly a ridge-type penalty. Weight decay shrinks the weights a little at every step.
A penalty is also a prior in disguise: a Gaussian prior on the weights gives ridge and a Laplace prior the lasso (MAP estimation, in Bayesian Reasoning), and ridge is the posterior mean with for prior variance (Gaussian Processes & Bayesian ML).
Validation and cross-validation
Choosing , or a degree is itself a kind of fitting, and choosing by test error makes the test error optimistic. The standard protocol splits the data three ways: fit on the training set, choose settings on a validation set, and touch the test set once, at the end. (How adaptive reuse of a test set inflates scores, and what to do about it, is in Measuring Intelligence & AGI.) When data are scarce, cross-validation lets every example serve in both roles:
CROSS-VALIDATE(data D, candidate settings Λ, folds K)
split D at random into folds F_1..F_K # stratify classes; keep groups and time order intact
for each setting λ in Λ:
for k = 1..K:
fit EVERY data-dependent step (scaling, feature selection, model) on D \ F_k
err[λ][k] = average loss of that fit on F_k
CV(λ) = mean over k of err[λ][k]; SE(λ) = std over k of err[λ][k] / sqrt(K)
λ* = argmin CV(λ) # or the simplest λ with CV(λ) ≤ CV(λ*) + SE(λ*)
refit with λ* on all of D
estimate its error with an outer loop (nested CV) or an untouched test setThe second choice of is the one-standard-error rule: among settings statistically tied with the best, take the most regularized.
Write , so and . Deleting example subtracts the rank-one term , which the Sherman–Morrison formula inverts:
The leave-one-out fit also drops from :
Subtract from . One fit yields all leave-one-out residuals. Replacing each by the average gives generalized cross-validation (Craven & Wahba, 1979).
How many folds? Leave-one-out () is nearly unbiased for the error of a model trained on points, but its fits overlap almost completely, so its errors are strongly correlated and the estimate can be variable; outside linear smoothers it also costs fits. or is the usual compromise: slightly pessimistic (each fit sees less data), cheaper and more stable. The spread across folds understates the real uncertainty, and no unbiased estimator of the variance of -fold cross-validation exists (Bengio & Grandvalet, 2004).
With 50 samples, 5,000 features and labels assigned by coin flip, an analyst keeps the 100 features most correlated with the labels on the full dataset, then runs 5-fold cross-validation of a classifier on those 100 features. What will the cross-validated error look like?
- Close to 50%, the honest error for random labels
- Far below 50%, because the screening step saw the labels of every fold
- Well above 50%, because 100 features overfit
- Unbiased, because cross-validation always is
Show the answer
B. Far below 50%, because the screening step saw the labels of every fold
The screening picked features that happen to correlate with these particular labels, including the labels later held out, so information leaked into every fold. Every data-dependent step, screening included, must be repeated inside each fold; done that way, the estimate is near 50%. Hastie, Tibshirani & Friedman (2009, §7.10.2) call this the wrong and the right way to do cross-validation.
Learning curves and the road ahead
A learning curve plots training and validation error against the training-set size . Training error rises with (memorizing gets harder) and validation error falls; both approach the floor set by bias plus noise, and the vertical gap between them is the variance. For a correctly specified linear model the excess risk shrinks like ; distribution-free bounds for classification shrink like , as the Deep Layer lesson on PAC learning proves.
| Diagnosis | Symptom | What helps |
|---|---|---|
| High bias (underfitting) | training and validation error both high, and close | a richer model, better features, less regularization; more data helps little |
| High variance (overfitting) | low training error, a large gap | more data, stronger regularization, a simpler model, averaging (bagging) |
| Leak or shift | validation looks fine, deployment does not | audit the split, the preprocessing and how deployment data differ (Evaluating Models) |
Key takeaways
- Training error is optimistic on average, . Excess risk splits into estimation error, which grows with capacity, and approximation error, which shrinks with it.
- For squared loss, expected test error is exactly noise + bias² + variance. -NN has variance ; least squares with coefficients has average in-sample variance and training optimism .
- Ridge, , multiplies each singular direction by ; the lasso soft-thresholds and sets coefficients exactly to zero; early stopping and dropout regularize implicitly.
- Choose hyperparameters by validation or -fold cross-validation with every data-dependent step inside the folds. For linear smoothers, leave-one-out costs one fit: the residuals are .
- Learning curves separate bias from variance. Overparameterized models that interpolate and still generalize strain the U-shaped picture, which the Deep Layer lessons take up.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
In -NN regression with fixed training inputs and noise variance , what happens as grows?
- Bias and variance both fall
- The variance falls as , while the bias typically grows
- The variance grows as , while the bias falls
- Only the irreducible noise changes
Show the answer
B. The variance falls as , while the bias typically grows
The prediction averages labels with independent noise, so its variance is . The neighbors also lie farther from , so their true values drift away from and the bias grows.
Ridge regression shrinks the least-squares fit most along which directions?
- The directions with the largest singular values of
- All directions by the same factor
- The directions with the smallest singular values of , where the inputs vary least
- Only the intercept direction
Show the answer
C. The directions with the smallest singular values of , where the inputs vary least
Component of the fit is multiplied by , which is near 1 when and near 0 when . Low-variance directions are where least-squares coefficients have the largest variance, , so that is where shrinkage pays most.
Why does the lasso produce coefficients that are exactly zero, while ridge does not?
- The penalty has a kink at zero: its subgradient there is a whole interval, so zero remains optimal for a range of data
- The lasso uses a larger value of
- Ridge needs standardized inputs and the lasso does not
- The lasso discards the features with the smallest variance before fitting
Show the answer
A. The penalty has a kink at zero: its subgradient there is a whole interval, so zero remains optimal for a range of data
For orthonormal inputs the lasso solves per coordinate, giving : exactly zero whenever . Ridge's smooth penalty only rescales, to , which is never zero unless is.
You choose by 10-fold cross-validation over 200 candidate values and report the smallest CV error as your model's expected error. Is that number trustworthy?
- Yes, because cross-validation is nearly unbiased
- Yes, provided the folds were stratified
- No, because 10 folds are too few; leave-one-out would fix it
- No: the minimum over 200 noisy estimates is biased downward; use nested cross-validation or an untouched test set
Show the answer
D. No: the minimum over 200 noisy estimates is biased downward; use nested cross-validation or an untouched test set
Each CV estimate is nearly unbiased for its own , but the smallest of 200 noisy estimates is selected partly for luck, the same selection effect that makes training error optimistic. An outer loop that repeats the whole search, or a final test set, gives an honest number.
Training error and validation error are both about 30%, nearly equal, and far above what you need. Which change is most likely to help?
- Collect ten times more data
- Use a more flexible model or better features
- Increase the regularization strength
- Switch from 10-fold to leave-one-out cross-validation
Show the answer
B. Use a more flexible model or better features
A small gap with high error on both sets is high bias: the model cannot represent the pattern. More flexibility, better features or weaker regularization lower the floor; more data mainly shrinks the gap, which is already small.
Go deeper
- PAC Learning & VC Dimension · When can you learn from finitely many examples?
- Regularization Theory · Ridge, lasso, priors and implicit regularization.
- Double Descent & Modern Generalization · Why huge models can still generalize.
Further reading
- T. Hastie, R. Tibshirani & J. Friedman, The Elements of Statistical Learning, 2nd ed. (Springer, 2009), chapters 3 and 7.
- S. Geman, E. Bienenstock & R. Doursat, "Neural networks and the bias/variance dilemma," Neural Computation 4(1), 1–58 (1992).
- R. Tibshirani, "Regression shrinkage and selection via the lasso," Journal of the Royal Statistical Society B 58(1), 267–288 (1996).
- M. Stone, "Cross-validatory choice and assessment of statistical predictions," Journal of the Royal Statistical Society B 36(2), 111–147 (1974).