Simple Algorithm
Artificial Intelligence · Hidden Layer · 22 min

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 kk-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 KK-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 (x,y)(\mathbf x,y) drawn i.i.d. from an unknown distribution PP. A predictor ff with loss ℓ\ell has a risk, its expected loss on new data, and an empirical risk, its average loss on the nn examples of the training set:

R(f)=E(x,y)∼P[ℓ(f(x),y)],R^n(f)=1n∑i=1nℓ(f(xi),yi).R(f)=\E_{(\mathbf x,y)\sim P}\big[\ell(f(\mathbf x),y)\big],\qquad \hat R_n(f)=\frac1n\sum_{i=1}^n\ell\big(f(\mathbf x_i),y_i\big).

Empirical risk minimization (ERM) picks f^∈arg min⁡f∈FR^n(f)\hat f\in\argmin_{f\in\mathcal F}\hat R_n(f) from a model class F\mathcal F. Generalization is about the gap R(f^)−R^n(f^)R(\hat f)-\hat R_n(\hat f).

For a predictor fixed before the data are drawn, R^n(f)\hat R_n(f) is an unbiased estimate of R(f)R(f), which is why a fresh test set works. For f^\hat f it is biased downward. Let f∘f^\circ be the best predictor in F\mathcal F. Since f^\hat f minimizes the empirical risk, R^n(f^)≤R^n(f∘)\hat R_n(\hat f)\le\hat R_n(f^\circ); since f∘f^\circ minimizes the risk, R(f∘)≤R(f^)R(f^\circ)\le R(\hat f). Taking expectations,

E[R^n(f^)] ≤ E[R^n(f∘)]=R(f∘) ≤ E[R(f^)].\E\big[\hat R_n(\hat f)\big]\ \le\ \E\big[\hat R_n(f^\circ)\big]=R(f^\circ)\ \le\ \E\big[R(\hat f)\big].

Training error is optimistic on average, for every model class and every loss.

R(f^)−R∗=R(f^)−R(f∘)⏟estimation error+R(f∘)−R∗⏟approximation errorR(\hat f)-R^*=\underbrace{R(\hat f)-R(f^\circ)}_{\text{estimation error}}+\underbrace{R(f^\circ)-R^*}_{\text{approximation error}}
R∗R^* is the Bayes risk, the lowest risk of any function at all. For squared loss the Bayes predictor is f∗(x)=E[y∣x]f^*(\mathbf x)=\E[y\mid\mathbf x] and R∗R^* is the average noise variance (the projection argument is in Probability Essentials). Enlarging F\mathcal F shrinks the approximation error and inflates the estimation error.

The bias–variance decomposition

Fix a test input x0\mathbf x_0 and write y=f(x0)+εy=f(\mathbf x_0)+\varepsilon with Eε=0\E\varepsilon=0 and Var⁡ε=σ2\Var\varepsilon=\sigma^2. The prediction f^D(x0)\hat f_\data(\mathbf x_0) is random because the training set D\data is, and the test noise ε\varepsilon is independent of D\data. Write fˉ(x0)=ED[f^D(x0)]\bar f(\mathbf x_0)=\E_\data\big[\hat f_\data(\mathbf x_0)\big] for the prediction averaged over training sets.

DerivationSquared error splits three ways
  1. E[(y−f^D(x0))2]=E[(ε+f(x0)−f^D(x0))2]=σ2+E[(f(x0)−f^D(x0))2]\E\big[(y-\hat f_\data(\mathbf x_0))^2\big]=\E\big[(\varepsilon+f(\mathbf x_0)-\hat f_\data(\mathbf x_0))^2\big]=\sigma^2+\E\big[(f(\mathbf x_0)-\hat f_\data(\mathbf x_0))^2\big]

    Expand around the truth. The cross term vanishes because ε\varepsilon has mean zero and is independent of D\data:

  2. E[(f−f^D)2]=(f−fˉ)2+E[(fˉ−f^D)2]\E\big[(f-\hat f_\data)^2\big]=(f-\bar f)^2+\E\big[(\bar f-\hat f_\data)^2\big]

    Add and subtract fˉ(x0)\bar f(\mathbf x_0). This cross term vanishes too, because ED[fˉ(x0)−f^D(x0)]=0\E_\data\big[\bar f(\mathbf x_0)-\hat f_\data(\mathbf x_0)\big]=0 (everything is evaluated at x0\mathbf x_0):

  3. E[(y−f^D(x0))2]=σ2⏟irreducible+(f(x0)−fˉ(x0))2⏟bias2+Var⁡D[f^D(x0)]⏟variance\E\big[(y-\hat f_\data(\mathbf x_0))^2\big]=\underbrace{\sigma^2}_{\text{irreducible}}+\underbrace{\big(f(\mathbf x_0)-\bar f(\mathbf x_0)\big)^2}_{\text{bias}^2}+\underbrace{\Var_\data\big[\hat f_\data(\mathbf x_0)\big]}_{\text{variance}}

    So the expected squared error at x0\mathbf x_0 is noise plus squared bias plus variance:

  4. E[test MSE]=σ2+Ex0[bias2(x0)+variance(x0)]\E[\text{test MSE}]=\sigma^2+\E_{\mathbf x_0}\big[\text{bias}^2(\mathbf x_0)+\text{variance}(\mathbf x_0)\big]

    Average over x0∼Px\mathbf x_0\sim P_{\mathbf x} 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 kk training inputs x(1),…,x(k)\mathbf x_{(1)},\dots,\mathbf x_{(k)} nearest to x0\mathbf x_0, so its variance is that of an average of kk independent noises:

E[(y−f^k(x0))2]=σ2+[f(x0)−1k∑ℓ=1kf(x(ℓ))]2+σ2k\E\big[(y-\hat f_k(\mathbf x_0))^2\big]=\sigma^2+\Big[f(\mathbf x_0)-\frac1k\sum_{\ell=1}^kf(\mathbf x_{(\ell)})\Big]^2+\frac{\sigma^2}{k}
Larger kk divides the variance by kk but averages over farther, less relevant neighbors, which usually grows the bias.

Least squares with pp coefficients predicts y^=Hy\hat{\mathbf y}=H\mathbf y with the hat matrix H=X(X⊤X)−1X⊤H=X(X^\top X)^{-1}X^\top, a projection of rank pp. Its variance averaged over the training inputs is 1n∑iVar⁡(y^i)=σ2tr⁡(H)/n=pσ2/n\frac1n\sum_i\Var(\hat y_i)=\sigma^2\operatorname{tr}(H)/n=p\sigma^2/n. If the model is correctly specified, the residual sum of squares has mean σ2(n−p)\sigma^2(n-p), so

E[training MSE]=σ2(1−pn),E[error on fresh labels at the same inputs]=σ2(1+pn).\E[\text{training MSE}]=\sigma^2\Big(1-\frac pn\Big),\qquad \E[\text{error on fresh labels at the same inputs}]=\sigma^2\Big(1+\frac pn\Big).

The gap 2pσ2/n2p\sigma^2/n is the optimism of the training error, which Mallows' CpC_p and AIC add back.

Predict before you look

A correctly specified linear model with p=4p=4 coefficients is fitted by least squares to n=12n=12 points. By what percentage does its expected training MSE fall below the noise variance σ2\sigma^2?

Show the answer

33 %

E[training MSE]=σ2(n−p)/n=23σ2\E[\text{training MSE}]=\sigma^2(n-p)/n=\tfrac23\sigma^2: 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 σ2(1+p/n)=43σ2\sigma^2(1+p/n)=\tfrac43\sigma^2, so the optimism is 2pσ2/n=23σ22p\sigma^2/n=\tfrac23\sigma^2.

Regularization: shrinkage, sparsity and early stopping

Regularization adds a penalty to the fit, w^=arg min⁡w ∥y−Xw∥2+λ Ω(w)\hat{\mathbf w}=\argmin_{\mathbf w}\ \norm{\mathbf y-X\mathbf w}^2+\lambda\,\Omega(\mathbf w), and trades bias for variance with one knob, the hyperparameter λ≥0\lambda\ge0. Ridge regression uses Ω(w)=∥w∥22\Omega(\mathbf w)=\norm{\mathbf w}_2^2, the lasso Ω(w)=∥w∥1\Omega(\mathbf w)=\norm{\mathbf w}_1 (inputs are usually standardized first, and the intercept is left unpenalized).

DerivationRidge in closed form, and what it shrinks
  1. −2X⊤(y−Xw)+2λw=0⟹w^λ=(X⊤X+λI)−1X⊤y-2X^\top(\mathbf y-X\mathbf w)+2\lambda\mathbf w=0\quad\Longrightarrow\quad\hat{\mathbf w}_\lambda=(X^\top X+\lambda I)^{-1}X^\top\mathbf y

    Set the gradient to zero. For λ>0\lambda>0 the matrix X⊤X+λIX^\top X+\lambda I is positive definite, so the solution exists and is unique even when p>np>n:

  2. Xw^λ=∑j=1ruj dj2dj2+λ uj⊤yX\hat{\mathbf w}_\lambda=\sum_{j=1}^r\mathbf u_j\,\frac{d_j^2}{d_j^2+\lambda}\,\mathbf u_j^\top\mathbf y

    Write the thin SVD X=UDV⊤X=UDV^\top with singular values d1≥⋯≥dr>0d_1\ge\dots\ge d_r>0 and left singular vectors uj\mathbf u_j. The fitted values become a filtered expansion:

  3. df(λ)=tr⁡[X(X⊤X+λI)−1X⊤]=∑j=1rdj2dj2+λ\mathrm{df}(\lambda)=\operatorname{tr}\big[X(X^\top X+\lambda I)^{-1}X^\top\big]=\sum_{j=1}^r\frac{d_j^2}{d_j^2+\lambda}

    Least squares (λ=0\lambda=0) keeps every component. Ridge multiplies component jj by dj2/(dj2+λ)d_j^2/(d_j^2+\lambda) and crushes the directions in which the inputs barely vary (small djd_j), where coefficients are worst determined and noisiest. The trace of this linear smoother, its effective degrees of freedom, falls from rr at λ=0\lambda=0 toward 00:

MethodPenaltyEstimate of wjw_jEffect
Least squaresnonezjz_junbiased; largest variance
Ridgeλ∥w∥22\lambda\norm{\mathbf w}_2^2zj/(1+λ)z_j/(1+\lambda)shrinks every coefficient by the same factor; none reaches zero
Lasso2λ∥w∥12\lambda\norm{\mathbf w}_1sign⁡(zj) (∣zj∣−λ)+\sign(z_j)\,(\abs{z_j}-\lambda)_+soft thresholding: small coefficients become exactly zero
Best subsetat most MM nonzerozj 1{∣zj∣≥∣z∣(M)}z_j\,\mathbf 1\{\abs{z_j}\ge\abs{z}_{(M)}\}hard thresholding: keep the MM largest
With orthonormal inputs (X⊤X=IX^\top X=I, least-squares coefficients zj=xj⊤yz_j=\mathbf x_j^\top\mathbf y) the penalties decouple coordinate by coordinate. The lasso zeroes coefficients because ∣w∣\abs w has a kink at 00: its subgradient there is the whole interval [−1,1][-1,1], so wj=0w_j=0 stays optimal whenever ∣zj∣≤λ\abs{z_j}\le\lambda. Geometrically, the corners of the ℓ1\ell_1 ball stick out along the axes, and the error ellipses usually touch the ball first at a corner.

Other regularizers act implicitly. Early stopping halts gradient descent before convergence: started from w=0\mathbf w=0 it fits the large-djd_j directions first, and after tt steps of size η\eta it behaves much like ridge with λ≈1/(ηt)\lambda\approx1/(\eta t). 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 λ=σ2/τ2\lambda=\sigma^2/\tau^2 for prior variance τ2\tau^2 (Gaussian Processes & Bayesian ML).

Validation and cross-validation

Choosing λ\lambda, kk 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:

text
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 set

The second choice of λ∗\lambda^* is the one-standard-error rule: among settings statistically tied with the best, take the most regularized.

DerivationProof (Sherman–Morrison)
  1. (A−xixi⊤)−1=A−1+A−1xixi⊤A−11−h⟹xi⊤(A−xixi⊤)−1=xi⊤A−11−h(A-\mathbf x_i\mathbf x_i^\top)^{-1}=A^{-1}+\frac{A^{-1}\mathbf x_i\mathbf x_i^\top A^{-1}}{1-h}\quad\Longrightarrow\quad\mathbf x_i^\top(A-\mathbf x_i\mathbf x_i^\top)^{-1}=\frac{\mathbf x_i^\top A^{-1}}{1-h}

    Write A=X⊤X+λΩA=X^\top X+\lambda\Omega, so y^i=xi⊤A−1X⊤y\hat y_i=\mathbf x_i^\top A^{-1}X^\top\mathbf y and h=Hii=xi⊤A−1xi<1h=H_{ii}=\mathbf x_i^\top A^{-1}\mathbf x_i<1. Deleting example ii subtracts the rank-one term xixi⊤\mathbf x_i\mathbf x_i^\top, which the Sherman–Morrison formula inverts:

  2. f^(−i)(xi)=xi⊤A−1(X⊤y−xiyi)1−h=y^i−h yi1−h\hat f^{(-i)}(\mathbf x_i)=\frac{\mathbf x_i^\top A^{-1}\big(X^\top\mathbf y-\mathbf x_iy_i\big)}{1-h}=\frac{\hat y_i-h\,y_i}{1-h}

    The leave-one-out fit also drops xiyi\mathbf x_iy_i from X⊤yX^\top\mathbf y:

  3. yi−f^(−i)(xi)=yi(1−h)−y^i+h yi1−h=yi−y^i1−hy_i-\hat f^{(-i)}(\mathbf x_i)=\frac{y_i(1-h)-\hat y_i+h\,y_i}{1-h}=\frac{y_i-\hat y_i}{1-h}

    Subtract from yiy_i. One fit yields all nn leave-one-out residuals. Replacing each HiiH_{ii} by the average tr⁡(H)/n\operatorname{tr}(H)/n gives generalized cross-validation (Craven & Wahba, 1979).

How many folds? Leave-one-out (K=nK=n) is nearly unbiased for the error of a model trained on n−1n-1 points, but its nn fits overlap almost completely, so its errors are strongly correlated and the estimate can be variable; outside linear smoothers it also costs nn fits. K=5K=5 or 1010 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 KK-fold cross-validation exists (Bengio & Grandvalet, 2004).

Check your understanding

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?

  1. Close to 50%, the honest error for random labels
  2. Far below 50%, because the screening step saw the labels of every fold
  3. Well above 50%, because 100 features overfit
  4. 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 nn. Training error rises with nn (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 pσ2/np\sigma^2/n; distribution-free bounds for classification shrink like complexity/n\sqrt{\text{complexity}/n}, as the Deep Layer lesson on PAC learning proves.

DiagnosisSymptomWhat helps
High bias (underfitting)training and validation error both high, and closea richer model, better features, less regularization; more data helps little
High variance (overfitting)low training error, a large gapmore data, stronger regularization, a simpler model, averaging (bagging)
Leak or shiftvalidation looks fine, deployment does notaudit the split, the preprocessing and how deployment data differ (Evaluating Models)

Key takeaways

  • Training error is optimistic on average, ER^n(f^)≤R(f∘)≤ER(f^)\E\hat R_n(\hat f)\le R(f^\circ)\le\E R(\hat f). 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. kk-NN has variance σ2/k\sigma^2/k; least squares with pp coefficients has average in-sample variance pσ2/np\sigma^2/n and training optimism 2pσ2/n2p\sigma^2/n.
  • Ridge, (X⊤X+λI)−1X⊤y(X^\top X+\lambda I)^{-1}X^\top\mathbf y, multiplies each singular direction by dj2/(dj2+λ)d_j^2/(d_j^2+\lambda); the lasso soft-thresholds and sets coefficients exactly to zero; early stopping and dropout regularize implicitly.
  • Choose hyperparameters by validation or KK-fold cross-validation with every data-dependent step inside the folds. For linear smoothers, leave-one-out costs one fit: the residuals are (yi−y^i)/(1−Hii)(y_i-\hat y_i)/(1-H_{ii}).
  • 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.

Question 1

In kk-NN regression with fixed training inputs and noise variance σ2\sigma^2, what happens as kk grows?

  1. Bias and variance both fall
  2. The variance falls as σ2/k\sigma^2/k, while the bias typically grows
  3. The variance grows as kσ2k\sigma^2, while the bias falls
  4. Only the irreducible noise changes
Show the answer

B. The variance falls as σ2/k\sigma^2/k, while the bias typically grows

The prediction averages kk labels with independent noise, so its variance is σ2/k\sigma^2/k. The neighbors also lie farther from x0\mathbf x_0, so their true values f(x(ℓ))f(\mathbf x_{(\ell)}) drift away from f(x0)f(\mathbf x_0) and the bias grows.

Question 2

Ridge regression shrinks the least-squares fit most along which directions?

  1. The directions with the largest singular values of XX
  2. All directions by the same factor
  3. The directions with the smallest singular values of XX, where the inputs vary least
  4. Only the intercept direction
Show the answer

C. The directions with the smallest singular values of XX, where the inputs vary least

Component jj of the fit is multiplied by dj2/(dj2+λ)d_j^2/(d_j^2+\lambda), which is near 1 when dj2≫λd_j^2\gg\lambda and near 0 when dj2≪λd_j^2\ll\lambda. Low-variance directions are where least-squares coefficients have the largest variance, σ2/dj2\sigma^2/d_j^2, so that is where shrinkage pays most.

Question 3

Why does the lasso produce coefficients that are exactly zero, while ridge does not?

  1. The ℓ1\ell_1 penalty has a kink at zero: its subgradient there is a whole interval, so zero remains optimal for a range of data
  2. The lasso uses a larger value of λ\lambda
  3. Ridge needs standardized inputs and the lasso does not
  4. The lasso discards the features with the smallest variance before fitting
Show the answer

A. The ℓ1\ell_1 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 min⁡w(w−z)2+2λ∣w∣\min_w(w-z)^2+2\lambda\abs w per coordinate, giving sign⁡(z)(∣z∣−λ)+\sign(z)(\abs z-\lambda)_+: exactly zero whenever ∣z∣≤λ\abs z\le\lambda. Ridge's smooth penalty only rescales, to z/(1+λ)z/(1+\lambda), which is never zero unless zz is.

Question 4

You choose λ\lambda 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?

  1. Yes, because cross-validation is nearly unbiased
  2. Yes, provided the folds were stratified
  3. No, because 10 folds are too few; leave-one-out would fix it
  4. 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 λ\lambda, 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.

Question 5

Training error and validation error are both about 30%, nearly equal, and far above what you need. Which change is most likely to help?

  1. Collect ten times more data
  2. Use a more flexible model or better features
  3. Increase the regularization strength
  4. 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

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).