The Bias-Variance Tradeoff

Table of Contents

1. Learning Objectives
2. Prerequisites
3. Notation
4. Core Intuition
5. Problem Setup and Expected Prediction Error
6. The Bias-Variance Decomposition Theorem
7. Bias, Variance, and Irreducible Error
8. Examples: Linear Regression and Ridge
9. k-Nearest Neighbors and Model Complexity
10. The Classical U-Curve and Model Selection
11. Regularization as Bias-Variance Control
12. Double Descent in Overparameterized Models
13. Beyond Squared Loss: Classification and Other Losses
14. Connection to Machine Learning Practice
15. Common Pitfalls and Misconceptions
16. Research Perspective
17. Summary of Takeaways
18. Exercises

---

Learning Objectives

After reading this chapter, you should be able to:

1. Define expected prediction error (EPE) and decompose it into irreducible noise, bias squared, and variance.
2. Prove the bias-variance decomposition for squared loss with no gaps in the cross-term arguments.
3. Compute bias and variance for linear regression (OLS and Ridge) and interpret their dependence on model complexity.
4. Explain how $k$ in k-NN controls the bias-variance tradeoff.
5. Describe the classical U-curve of test error vs model complexity and how regularization navigates it.
6. State the double descent phenomenon and explain implicit regularization in overparameterized models.
7. Connect the decomposition to Maximum Likelihood Estimation, overfitting, and generalization in deep learning.

---

Prerequisites

• Maximum Likelihood Estimation: MLE, Gaussian noise model leading to MSE, finite-sample behavior.
• Bayes' Theorem: posterior vs point estimates, irreducible Bayes error.
• The Multivariate Gaussian: linear regression noise models, conditional expectation.
• Positive Definite Matrices: Ridge regression, $(\mathbf{X}^T\mathbf{X} + \lambda\mathbf{I})^{-1}$.
• Gradient Descent: SGD as implicit regularization.

---

Notation

• $f(\mathbf{x})$ — True regression function
• $\hat{f}(\mathbf{x}; \mathcal{D})$ — Estimator trained on dataset $\mathcal{D}$
• $\mathbb{E}_{\mathcal{D}}[\cdot]$ — Expectation over training data
• $\mathrm{Bias}, \mathrm{Var}$ — Bias and variance of an estimator
• $\sigma^2$ — Irreducible noise variance

---

Core Intuition

Why does a model that fits the training data perfectly often fail on new data? Why does a linear model underfit nonlinear patterns? The bias-variance tradeoff provides a precise answer: every prediction error has three sources, and simpler vs more complex models allocate error differently between them.

• Bias captures systematic error — the model family cannot represent the truth.
• Variance captures sensitivity to the particular training sample — the model overfits noise.
• Irreducible noise is inherent randomness no model can eliminate.

The classical story: as model complexity increases, bias decreases but variance increases. Test error follows a U-shape, minimized at intermediate complexity. Modern deep learning complicates this picture: massively overparameterized networks can generalize well despite interpolating training data — the double descent phenomenon.

This chapter derives the decomposition rigorously and applies it to linear models, k-NN, regularization, and contemporary overparameterized regimes.

Series context. This is Part VI of Chapter 3 (Probability & Statistical Learning) in Volume I. It synthesizes MLE, Bayes' Theorem, and prepares for regularization and generalization theory in Volume II.

---

Problem Setup and Expected Prediction Error

Data generating process. Observations $(x_i, y_i)$ are drawn i.i.d. from a joint distribution. We model:

$$Y = f(X) + \epsilon, \quad \epsilon \sim (0, \sigma^2), \quad \epsilon \perp X, \tag{1}$$

where $f(x) = \mathbb{E}[Y \mid X = x]$ is the regression function (conditional mean). Noise $\epsilon$ has mean zero and variance $\sigma^2$.

Learning. Given training set $\mathcal{D} = \{(x_i, y_i)\}_{i=1}^n$, we learn a predictor $\hat{f}_\mathcal{D}(x)$ — a function of both the data and the query point $x$.

Goal. Minimize expected prediction error (EPE) at a new test point $(X_0, Y_0)$:

$$\text{EPE}(x_0) = \mathbb{E}_{\mathcal{D}, Y_0 \mid X_0=x_0}\left[(Y_0 - \hat{f}_\mathcal{D}(x_0))^2\right], \tag{2}$$

where expectation is over: (i) random training set $\mathcal{D}$, (ii) test noise $Y_0 - f(x_0)$ given $X_0 = x_0$.

Definition 1 (Average EPE). The average expected prediction error is:

$$\text{EPE} = \mathbb{E}_{X_0}[\text{EPE}(X_0)]. \tag{3}$$

We derive the decomposition at fixed $x_0$; averaging over $X_0$ gives the global version.

---

The Bias-Variance Decomposition Theorem

Definition 2 (Average Predictor). The average predictor at $x_0$ is:

$$\bar{f}(x_0) = \mathbb{E}_\mathcal{D}[\hat{f}_\mathcal{D}(x_0)], \tag{4}$$

the mean prediction over all possible training sets of size $n$.

Definition 3 (Bias). The bias of $\hat{f}$ at $x_0$ is:

$$\text{Bias}(\hat{f}(x_0)) = \bar{f}(x_0) - f(x_0). \tag{5}$$

Definition 4 (Variance). The variance of $\hat{f}$ at $x_0$ is:

$$\text{Var}(\hat{f}(x_0)) = \mathbb{E}_\mathcal{D}[(\hat{f}_\mathcal{D}(x_0) - \bar{f}(x_0))^2]. \tag{6}$$

Theorem 1 (Bias-Variance Decomposition). Under the model (1), for fixed $x_0$:

$$\text{EPE}(x_0) = \underbrace{\sigma^2}_{\text{irreducible noise}} + \underbrace{[\text{Bias}(\hat{f}(x_0))]^2}_{\text{bias}^2} + \underbrace{\text{Var}(\hat{f}(x_0))}_{\text{variance}}. \tag{7}$$

Proof. Write $Y_0 = f(x_0) + \epsilon$ where $\mathbb{E}[\epsilon] = 0$, $\text{Var}(\epsilon) = \sigma^2$, and $\epsilon$ is independent of $\mathcal{D}$ and $\hat{f}_\mathcal{D}$.

Step 1 — Add and subtract terms. Insert $\bar{f}(x_0)$ and $f(x_0)$:

$$Y_0 - \hat{f}_\mathcal{D}(x_0) = \underbrace{(Y_0 - f(x_0))}_{\epsilon} + \underbrace{(f(x_0) - \bar{f}(x_0))}_{-\text{Bias}} + \underbrace{(\bar{f}(x_0) - \hat{f}_\mathcal{D}(x_0))}_{\text{deviation from mean}}. \tag{8}$$

Step 2 — Square and take expectation.

$$\text{EPE}(x_0) = \mathbb{E}[(\epsilon - \text{Bias} + (\bar{f} - \hat{f}))^2], \tag{9}$$

where $\text{Bias} = f(x_0) - \bar{f}(x_0)$ is a constant (not random w.r.t. $\mathcal{D}$).

Step 3 — Expand the square.

$$= \mathbb{E}[\epsilon^2] + \text{Bias}^2 + \mathbb{E}[(\bar{f} - \hat{f})^2] + 2\mathbb{E}[\epsilon \cdot (-\text{Bias})] + 2\mathbb{E}[\epsilon(\bar{f}-\hat{f})] + 2\mathbb{E}[(-\text{Bias})(\bar{f}-\hat{f})]. \tag{10}$$

Step 4 — Show cross-terms vanish.

(Cross-term 1.) $\mathbb{E}[\epsilon \cdot (-\text{Bias})] = -\text{Bias} \cdot \mathbb{E}[\epsilon] = 0$ since $\epsilon$ is independent of everything and mean zero.

(Cross-term 2.) $\mathbb{E}[\epsilon(\bar{f}-\hat{f})] = \mathbb{E}[\epsilon] \cdot \mathbb{E}[\bar{f}-\hat{f}] = 0$ by independence of test noise from training data.

(Cross-term 3.) $\mathbb{E}[(-\text{Bias})(\bar{f}-\hat{f})] = -\text{Bias} \cdot \mathbb{E}[\bar{f}-\hat{f}] = 0$ since $\mathbb{E}_\mathcal{D}[\hat{f}] = \bar{f}$ implies $\mathbb{E}[\bar{f}-\hat{f}] = 0$.

Step 5 — Identify remaining terms.

$$\mathbb{E}[\epsilon^2] = \sigma^2, \quad \mathbb{E}[(\bar{f}-\hat{f})^2] = \text{Var}(\hat{f}(x_0)). \tag{11}$$

Therefore (7) holds. $\blacksquare$

Remark. The decomposition is exact for squared loss and the additive noise model (1). It does not require linearity of $\hat{f}$ or $f$.

---

Bias, Variance, and Irreducible Error

Irreducible noise $\sigma^2$. The variance of $Y_0$ given $X_0 = x_0$ that cannot be reduced by any predictor. This is the Bayes error for squared loss — the error of the optimal predictor $f(x_0) = \mathbb{E}[Y \mid X = x_0]$.

Bias². Measures systematic mis-specification. If the model family $\{\hat{f}\}$ cannot represent $f$, then $\bar{f} \neq f$ even with infinite data. Example: fitting a line to quadratic data.

Variance. Measures instability across training sets. High variance: small changes in $\mathcal{D}$ produce large changes in $\hat{f}(x_0)$. Example: $k=1$ nearest neighbor (memorization).

The tradeoff (classical view). Increasing model complexity:

• Decreases bias — richer function class approximates $f$ better.
• Increases variance — more parameters fit noise in $\mathcal{D}$.

Total error $\sigma^2 + \text{Bias}^2 + \text{Var}$ may be minimized at intermediate complexity.

Proposition 1. For squared loss, the oracle predictor minimizing EPE at $x_0$ is $f(x_0)$, with error exactly $\sigma^2$.

---

Examples: Linear Regression and Ridge

Ordinary Least Squares (Fixed Design)

Model: $\hat{f}(x) = \mathbf{x}^T \hat{\boldsymbol\beta}_\mathcal{D}$ with $\hat{\boldsymbol\beta} = (\mathbf{X}^T\mathbf{X})^{-1}\mathbf{X}^T\mathbf{y}$.

Assume the true relationship is linear: $Y = \mathbf{x}^T \boldsymbol\beta^* + \epsilon$.

Bias. $\mathbb{E}[\hat{\boldsymbol\beta}] = \boldsymbol\beta^*$, so $\text{Bias}(x_0) = \mathbf{x}_0^T \boldsymbol\beta^* - f(x_0) = 0$ when $f(x) = \mathbf{x}^T \boldsymbol\beta^*$.

If the true $f$ is nonlinear, OLS has nonzero bias — the best linear approximation.

Variance. With $\text{Var}(\epsilon) = \sigma^2$:

$$\text{Var}(\hat{f}(x_0)) = \sigma^2 \mathbf{x}_0^T (\mathbf{X}^T\mathbf{X})^{-1} \mathbf{x}_0. \tag{12}$$

Proof sketch. $\hat{f}(x_0) = \mathbf{x}_0^T (\mathbf{X}^T\mathbf{X})^{-1}\mathbf{X}^T\mathbf{y}$. Since $\mathbf{y} = \mathbf{X}\boldsymbol\beta^* + \boldsymbol\epsilon$:

$$\hat{f}(x_0) = \mathbf{x}_0^T \boldsymbol\beta^* + \mathbf{x}_0^T(\mathbf{X}^T\mathbf{X})^{-1}\mathbf{X}^T\boldsymbol\epsilon. \tag{13}$$

The second term has mean zero and variance $\sigma^2 \mathbf{x}_0^T(\mathbf{X}^T\mathbf{X})^{-1}\mathbf{x}_0$. $\blacksquare$

Interpretation. Variance is large when $x_0$ lies in directions where $\mathbf{X}^T\mathbf{X}$ has small eigenvalues — extrapolation beyond the training hull.

Ridge Regression

$\hat{\boldsymbol\beta}_\lambda = (\mathbf{X}^T\mathbf{X} + \lambda\mathbf{I})^{-1}\mathbf{X}^T\mathbf{y}$.

Bias increases: $\mathbb{E}[\hat{\boldsymbol\beta}_\lambda] = (\mathbf{X}^T\mathbf{X} + \lambda\mathbf{I})^{-1}\mathbf{X}^T\mathbf{X}\boldsymbol\beta^* \neq \boldsymbol\beta^*$ — shrinkage toward zero.

Variance decreases: Eigenvalues of $(\mathbf{X}^T\mathbf{X} + \lambda\mathbf{I})^{-1}$ are smaller than those of $(\mathbf{X}^T\mathbf{X})^{-1}$.

Theorem 2 (Ridge Bias-Variance Tradeoff). There exists $\lambda^* \geq 0$ that minimizes $\text{EPE}$ (averaged over $x_0$) when $\lambda = 0$ (OLS) has excessive variance.

See Positive Definite Matrices for the geometry of Ridge as perturbing the Gram matrix.

---

k-Nearest Neighbors and Model Complexity

Predictor. $\hat{f}(x) = \frac{1}{k}\sum_{x_i \in N_k(x)} y_i$ — average of $k$ nearest neighbors.

Complexity parameter. $k$ controls model flexibility:

• $k = 1$ — Low (zero on training) — High — Interpolation, memorization
• $k = n$ — High (predicts $\bar{y}$) — Zero — Constant prediction
• Intermediate — Moderate — Moderate — Smoothing

Proposition 2. As $k \to 1$: $\text{Var}(\hat{f}(x)) \to \text{Var}(Y \mid X \approx x)$ and $\text{Bias}(\hat{f}(x)) \to 0$ (under smoothness).

As $k \to n$: $\text{Var} \to 0$ and $\text{Bias}(\hat{f}(x)) \to f(x) - \mathbb{E}[Y]$.

Optimal $k$. Typically $k^* = O(n^{4/(4+d)})$ for $d$-dimensional features — curse of dimensionality increases optimal $k$.

---

The Classical U-Curve and Model Selection

Model complexity can be measured by: number of parameters, VC dimension, $k$ in k-NN, degree of polynomial, tree depth, etc.

Classical U-curve. Plot test EPE vs complexity:

1. Underfitting region (low complexity): High bias, low variance, high total error.
2. Sweet spot: Bias and variance balanced, minimum test error.
3. Overfitting region (high complexity): Low bias, high variance, high total error.

Model selection. Choose complexity (or regularization strength $\lambda$) to minimize estimated test error — cross-validation, AIC, BIC. AIC/BIC connect to Maximum Likelihood Estimation via penalized log-likelihood.

Proposition 3. Training error decreases monotonically with complexity (for nested models), but test error is U-shaped (classically).

---

Regularization as Bias-Variance Control

Principle. Regularization increases bias (shrinks toward simpler models) to decrease variance, reducing total error when variance dominates.

Examples.

• Ridge ($L_2$) — Penalty $\lambda \lVert\boldsymbol\beta\rVert_2^2$ — Shrinks coefficients, reduces variance
• Lasso ($L_1$) — Penalty $\lambda \lVert\boldsymbol\beta\rVert_1$ — Sparsity, reduces effective complexity
• Early stopping — Stop gradient descent before convergence — Limits effective model capacity
• Dropout — Random neuron masking — Ensemble-like variance reduction
• Weight decay — $L_2$ on neural network weights — Ridge analog in deep learning

Theorem 3 (Explicit Bias-Variance for Ridge — Sketch). For linear model with $\lambda > 0$:

$$\text{EPE} = \sigma^2 + \text{Bias}_\lambda^2 + \text{Var}_\lambda, \tag{14}$$

where $\text{Var}_\lambda \leq \text{Var}_{\text{OLS}}$ and $\text{Bias}_\lambda^2$ increases with $\lambda$.

Connection to MAP. Ridge regression is MAP under Gaussian prior $\boldsymbol\beta \sim \mathcal{N}(\mathbf{0}, \tau^2\mathbf{I})$ — see Bayes' Theorem. The prior introduces bias intentionally.

---

Double Descent in Overparameterized Models

Classical U-curve breaks down when model complexity exceeds sample size $n$ (interpolation threshold).

Three regimes.

1. Underparameterized ($p < n$): Classical U-curve — optimal complexity in the middle.
2. Interpolation threshold ($p \approx n$): Test error spikes — model can interpolate noise.
3. Overparameterized ($p \gg n$): Test error decreases again — "double descent."

Explanation (minimum-norm interpolation). Among all $\boldsymbol\beta$ satisfying $\mathbf{X}\boldsymbol\beta = \mathbf{y}$ (exact fit), gradient descent converges to the minimum $\ell_2$ norm solution:

$$\hat{\boldsymbol\beta}_{\text{min-norm}} = \underset{\boldsymbol\beta : \mathbf{X}\boldsymbol\beta = \mathbf{y}}{\text{argmin}} \|\boldsymbol\beta\|_2. \tag{15}$$

This implicit regularization reduces variance despite zero training error.

Neural networks. Massive overparameterization ($p \gg n$) with SGD, weight decay, and architectural biases (convolutions, skip connections) yields low test error — effective complexity is controlled by implicit rather than explicit parameter count.

Proposition 4. Double descent is not a violation of the bias-variance decomposition — it reflects that the decomposition still holds but variance can decrease in the overparameterized regime due to implicit regularization.

Remark. The bias-variance tradeoff remains valid at each fixed training procedure; what changes is how complexity maps to $(\text{Bias}, \text{Var})$ in modern architectures.

---

Beyond Squared Loss: Classification and Other Losses

Classification. For 0-1 loss, a similar decomposition exists but with different structure. For squared loss on probability estimates (Brier score), the decomposition applies to calibrated probabilities.

Connection to cross-entropy. From KL Divergence, minimizing cross-entropy relates to bias in probability estimates. Overconfident wrong predictions indicate high bias in the softmax outputs; instability across training runs indicates variance.

Bayes error for classification. Irreducible error is $1 - \max_c P(Y = c \mid X)$ — the error of the Bayes classifier.

---

Connection to Machine Learning Practice

Diagnosing Underfitting and Overfitting

• High training error: High bias (underfitting) — increase capacity, reduce regularization.
• Low training error, high validation error: High variance (overfitting) — regularize, more data, reduce capacity.
• Both low: Good generalization (modulo $\sigma^2$).

Ensembling and Variance Reduction

Bagging averages predictors trained on bootstrap samples — reduces variance without increasing bias much. Random forests extend this. Bias-variance analysis: $\text{Var}(\bar{f}) = \text{Var}(f)/B + \text{Cov terms}$; averaging independent models divides variance by $B$.

Data Size and the Tradeoff

As $n \to \infty$: variance $\to 0$ for consistent estimators; bias remains (model mis-specification). More data helps variance-dominated problems most.

Deep Learning

Modern networks operate in the overparameterized, double-descent regime. Generalization depends on:

• Implicit bias of Gradient Descent (SGD noise, early stopping)
• Architecture (inductive bias reducing effective complexity)
• Regularization (weight decay, dropout, data augmentation)

The classical U-curve is insufficient alone — but bias, variance, and $\sigma^2$ still decompose the error.

---

Common Pitfalls and Misconceptions

Pitfall 1: Applying the decomposition to training error. The theorem concerns expected test error, not training error. Training error has a different (optimistic) bias.

Pitfall 2: Assuming bias and variance always trade off monotonically in complexity. Double descent shows variance can decrease after the interpolation threshold.

Pitfall 3: Confusing high variance with high noise. $\sigma^2$ is irreducible noise in $Y$; variance of $\hat{f}$ is reducible with more data or regularization.

Pitfall 4: Ignoring model mis-specification. Zero variance with wrong model class still yields high bias — ensembling wrong models does not fix systematic error.

Pitfall 5: Treating the decomposition as only for squared loss. Extensions exist for other losses; the squared-loss version is the cleanest and most used.

Pitfall 6: Equating parameter count with effective complexity. Overparameterized networks have many parameters but low effective complexity due to implicit regularization.

---

Research Perspective

The bias-variance decomposition for squared loss was formalized by Geman, Bienenstock, and Doursat (1992) in the neural network context, though components appeared earlier in statistics (Hoerl & Kennard, 1970 for Ridge). The classical U-curve guided model selection for decades.

Double descent was documented systematically by Belkin et al. (2019) and Spigler et al. (2019), reviving interest in interpolation and benign overfitting. Neural tangent kernel theory and implicit regularization of SGD aim to explain why deep networks generalize despite massive capacity.

Open questions: tight bias-variance estimates for deep networks, role of data augmentation, and whether scaling laws (Kaplan et al., 2020) reflect fundamental bias-variance tradeoffs or new phenomena.

---

Summary of Takeaways

• Irreducible noise $\sigma^2$ — $\text{Var}(Y \mid X)$ — Inherent randomness

• Bias² — $(\mathbb{E}[\hat{f}] - f)^2$ — Model mis-specification

• Variance — $\text{Var}(\hat{f})$ — Sensitivity to training data

• EPE — $\sigma^2 + \text{Bias}^2 + \text{Var}$ — Total expected test error

• Complexity ↑ — Bias ↓, Var ↑ (classically) — U-curve

• Regularization — Bias ↑, Var ↓ — Navigate U-curve

• Double descent — Var ↓ again when $p \gg n$ — Implicit regularization

• Underfitting — High — Low — High

• Classical optimum — Medium — Medium — Lowest

• Overfitting (interpolating) — Low — High — High

• Overparameterized (modern) — Low — Moderate* — Good

*With SGD, weight decay, architecture.

Next in Volume II: Linear Regression — applying these principles to the foundational supervised learning algorithm.

---

Exercises

Exercise 1 (Proof). Verify all three cross-terms in the proof of Theorem 1 vanish, stating independence assumptions explicitly.

Exercise 2 (OLS variance). Derive (12) completely for fixed design matrix $\mathbf{X}$.

Exercise 3 (Ridge). Express $\mathbb{E}[\hat{\boldsymbol\beta}_\lambda]$ and $\text{Cov}(\hat{\boldsymbol\beta}_\lambda)$ in terms of $(\mathbf{X}^T\mathbf{X} + \lambda\mathbf{I})^{-1}$.

Exercise 4 (k-NN). For $k=1$ and deterministic $f$, show $\hat{f}(x_i) = y_i$ on training data and characterize variance at a training point.

Exercise 5 (Bias). Fit $Y = \beta_0 + \beta_1 X + \epsilon$ when true $f(x) = x^2$. Compute asymptotic bias of OLS at $x_0 = 1$.

Exercise 6 (Double descent). Explain why $\hat{\boldsymbol\beta}_{\text{min-norm}}$ has lower norm than a generic interpolating solution and why this reduces variance.

Exercise 7 (Conceptual). Why does bagging reduce variance but not bias?

Exercise 8 (Extension). State how the irreducible error term changes for classification with 0-1 loss.