ML

Overfitting, Underfitting & Regularization

A rigorous treatment of model complexity control: why overparameterized models memorize, how regularization constrains the hypothesis class, Tikhonov regularization as MAP estimation, and the double descent phenomenon.

Intermediate

Prerequisites

Table of Contents

  1. Learning Objectives
  2. Notation
  3. Core Intuition
  4. The Overfitting Phenomenon
  5. Regularized Risk Minimization
  6. Tikhonov (L2) Regularization
  7. L1 Regularization and Sparsity
  8. Elastic Net
  9. Bayesian Interpretation of Regularization
  10. Early Stopping as Implicit Regularization
  11. Double Descent and Modern Interpolation
  12. Common Pitfalls
  13. Summary
  14. Exercises

Learning Objectives

  1. Formally define overfitting and underfitting in terms of the generalization gap.
  2. Derive the ridge regression (L2) solution in closed form and interpret its spectral shrinkage.
  3. Derive the L1 penalty and explain why it induces sparsity via subgradient geometry.
  4. Show that L2 regularization is equivalent to MAP estimation with a Gaussian prior.
  5. Explain early stopping as implicit L2 regularization in gradient descent.
  6. Describe the double descent curve and reconcile it with classical bias-variance theory.

Notation

  • R^n(f)\hat{R}_n(f) — empirical risk, R(f)R(f) — population risk
  • λ≥0\lambda \geq 0 — regularization strength
  • Ω(f)\Omega(f) — regularizer (penalty functional)
  • ∥w∥22=∑jwj2\lVert \mathbf{w} \rVert_2^2 = \sum_j w_j^2 — squared L2 norm
  • ∥w∥1=∑j∣wj∣\lVert \mathbf{w} \rVert_1 = \sum_j |w_j| — L1 norm
  • X∈Rn×d\mathbf{X} \in \mathbb{R}^{n \times d} — design matrix (rows are samples)
  • y∈Rn\mathbf{y} \in \mathbb{R}^n — target vector

Core Intuition

A model that is too simple (few parameters, restricted F\mathcal{F}) cannot capture the underlying pattern — this is underfitting. A model that is too complex can memorize noise in the training data — this is overfitting. Regularization adds a penalty for complexity, effectively constraining the search to "simpler" solutions within F\mathcal{F}.

Regularization Path

λ (regularization)coefficient
β₁ = 1.70
β₂ = -1.00
β₃ = 0.40
β₄ = -0.10
λ
0.80
β₁β₂β₃β₄Current λ
Explore: L1 (Lasso) drives coefficients exactly to zero — producing sparse models. Watch β lines hit the x-axis.

The Overfitting Phenomenon

Definition. A model f^n\hat{f}_n overfits if:

R^n(f^n)≪R(f^n),(1)\hat{R}_n(\hat{f}_n) \ll R(\hat{f}_n), \tag{1}

i.e., the training error is much smaller than the test error. The generalization gap is:

gap(f^n)=R(f^n)−R^n(f^n)≥0.(2)\text{gap}(\hat{f}_n) = R(\hat{f}_n) - \hat{R}_n(\hat{f}_n) \geq 0. \tag{2}

For a polynomial of degree dd fitting nn points: if d≥n−1d \geq n-1, the polynomial interpolates perfectly (R^n=0\hat{R}_n = 0) but oscillates wildly between points, yielding large RR.

Regularized Risk Minimization

Instead of pure ERM, we solve:

f^λ=arg⁡min⁡f∈F[R^n(f)+λ Ω(f)],(3)\hat{f}_\lambda = \arg\min_{f \in \mathcal{F}} \left[ \hat{R}_n(f) + \lambda \, \Omega(f) \right], \tag{3}

where Ω(f)≥0\Omega(f) \geq 0 penalizes complexity and λ\lambda controls the tradeoff.

Tikhonov (L2) Regularization

For linear models f(x)=wTxf(\mathbf{x}) = \mathbf{w}^T\mathbf{x} with squared loss:

w^λ=arg⁡min⁡w12n∥Xw−y∥22+λ2∥w∥22.(4)\hat{\mathbf{w}}_\lambda = \arg\min_{\mathbf{w}} \frac{1}{2n}\lVert \mathbf{X}\mathbf{w} - \mathbf{y} \rVert_2^2 + \frac{\lambda}{2}\lVert \mathbf{w} \rVert_2^2. \tag{4}

Closed-form solution. Setting the gradient to zero:

1nXT(Xw−y)+λw=0\frac{1}{n}\mathbf{X}^T(\mathbf{X}\mathbf{w} - \mathbf{y}) + \lambda\mathbf{w} = 0 w^λ=(XTX+nλI)−1XTy.(5)\hat{\mathbf{w}}_\lambda = (\mathbf{X}^T\mathbf{X} + n\lambda\mathbf{I})^{-1}\mathbf{X}^T\mathbf{y}. \tag{5}

Spectral interpretation. Let X=UΣVT\mathbf{X} = \mathbf{U}\boldsymbol\Sigma\mathbf{V}^T (SVD). Then:

w^λ=∑j=1dσj2σj2+nλ⋅ujTyσj⋅vj.(6)\hat{\mathbf{w}}_\lambda = \sum_{j=1}^d \frac{\sigma_j^2}{\sigma_j^2 + n\lambda} \cdot \frac{\mathbf{u}_j^T\mathbf{y}}{\sigma_j} \cdot \mathbf{v}_j. \tag{6}

The factor σj2σj2+nλ\frac{\sigma_j^2}{\sigma_j^2 + n\lambda} shrinks each component toward zero. Small singular values (noise directions) are shrunk most aggressively.

Effect on bias-variance:

  • Increases bias (moves solution away from OLS).
  • Decreases variance (stabilizes against noise in y\mathbf{y}).
  • Optimal λ\lambda minimizes their sum.

L1 Regularization and Sparsity

w^λ=arg⁡min⁡w12n∥Xw−y∥22+λ∥w∥1.(7)\hat{\mathbf{w}}_\lambda = \arg\min_{\mathbf{w}} \frac{1}{2n}\lVert \mathbf{X}\mathbf{w} - \mathbf{y} \rVert_2^2 + \lambda\lVert \mathbf{w} \rVert_1. \tag{7}

No closed-form solution exists; solved via coordinate descent or proximal methods.

Why sparsity? The L1 ball {w:∥w∥1≤t}\{\mathbf{w}: \lVert\mathbf{w}\rVert_1 \leq t\} has corners on coordinate axes. The ellipsoidal contours of the quadratic loss are most likely to first touch the constraint at a corner, setting some wj=0w_j = 0 exactly.

Soft-thresholding. For orthogonal design (XTX=nI\mathbf{X}^T\mathbf{X} = n\mathbf{I}), the solution has the explicit form:

w^j=sign(w^jOLS)⋅max⁡(∣w^jOLS∣−nλ,0).(8)\hat{w}_j = \text{sign}(\hat{w}_j^{\text{OLS}}) \cdot \max(|\hat{w}_j^{\text{OLS}}| - n\lambda, 0). \tag{8}

Elastic Net

Combines L1 and L2:

Ω(w)=α∥w∥1+1−α2∥w∥22,α∈[0,1].(9)\Omega(\mathbf{w}) = \alpha\lVert\mathbf{w}\rVert_1 + \frac{1-\alpha}{2}\lVert\mathbf{w}\rVert_2^2, \quad \alpha \in [0,1]. \tag{9}

Benefits: sparsity from L1, grouping effect from L2 (correlated features get similar weights).

Bayesian Interpretation of Regularization

Theorem. L2 regularization ⇔\Leftrightarrow MAP estimation with Gaussian prior.

Proof. Let w∼N(0,τ2I)\mathbf{w} \sim \mathcal{N}(\mathbf{0}, \tau^2\mathbf{I}) and yi∣xi,w∼N(wTxi,σ2)y_i \mid \mathbf{x}_i, \mathbf{w} \sim \mathcal{N}(\mathbf{w}^T\mathbf{x}_i, \sigma^2). The MAP estimate is:

w^MAP=arg⁡max⁡w[log⁡p(y∣X,w)+log⁡p(w)]\hat{\mathbf{w}}_{\text{MAP}} = \arg\max_{\mathbf{w}} \left[\log p(\mathbf{y} \mid \mathbf{X}, \mathbf{w}) + \log p(\mathbf{w})\right] =arg⁡min⁡w[12σ2∥Xw−y∥2+12τ2∥w∥2].(10)= \arg\min_{\mathbf{w}} \left[\frac{1}{2\sigma^2}\lVert\mathbf{X}\mathbf{w} - \mathbf{y}\rVert^2 + \frac{1}{2\tau^2}\lVert\mathbf{w}\rVert^2\right]. \tag{10}

Setting λ=σ2/(nτ2)\lambda = \sigma^2 / (n\tau^2) recovers ridge regression. ■\blacksquare

Corollary. L1 regularization corresponds to a Laplace prior: p(wj)=12be−∣wj∣/bp(w_j) = \frac{1}{2b}e^{-|w_j|/b}.

Early Stopping as Implicit Regularization

Consider gradient descent on the unregularized objective starting from w0=0\mathbf{w}_0 = \mathbf{0}:

wt+1=wt−η∇R^n(wt).(11)\mathbf{w}_{t+1} = \mathbf{w}_t - \eta \nabla \hat{R}_n(\mathbf{w}_t). \tag{11}

Proposition (Ali et al., 2019). For squared loss with step size η\eta, after TT iterations:

wT≈(I−(I−ηXTX/n)T)(XTX/n)−1XTy/n.(12)\mathbf{w}_T \approx \left(\mathbf{I} - (\mathbf{I} - \eta\mathbf{X}^T\mathbf{X}/n)^T\right)(\mathbf{X}^T\mathbf{X}/n)^{-1}\mathbf{X}^T\mathbf{y}/n. \tag{12}

This is equivalent to ridge regression with λ≈1ηT\lambda \approx \frac{1}{\eta T}. Stopping early ⇔\Leftrightarrow larger implicit λ\lambda ⇔\Leftrightarrow more regularization.

Double Descent and Modern Interpolation

Classical theory predicts: as model complexity increases past the interpolation threshold (d≈nd \approx n), test error explodes. But modern observations show:

test error={decreasing (underfitting)d≪npeak (interpolation threshold)d≈ndecreasing again (overparameterized)d≫n(13)\text{test error} = \begin{cases} \text{decreasing (underfitting)} & d \ll n \\ \text{peak (interpolation threshold)} & d \approx n \\ \text{decreasing again (overparameterized)} & d \gg n \end{cases} \tag{13}

Explanation. In the overparameterized regime, gradient descent selects the minimum-norm interpolant (see Gradient Flow). This implicit bias toward simplicity acts as regularization, even though training loss is zero.

Common Pitfalls

Pitfall 1. Regularizing the bias term. Typically the intercept should not be penalized — it shifts predictions but doesn't add complexity.

Pitfall 2. Not standardizing features before applying L1/L2. The penalty treats all coordinates equally; if features are on different scales, regularization acts unevenly.

Pitfall 3. Treating λ\lambda as a fixed hyperparameter. It should be tuned via cross-validation; the optimal λ\lambda depends on noise level, sample size, and feature correlation.

Summary

  • Overfitting = large generalization gap; underfitting = high training error.
  • L2 regularization shrinks coefficients spectrally; equivalent to Gaussian prior MAP.
  • L1 regularization induces sparsity via corner geometry; equivalent to Laplace prior MAP.
  • Early stopping implicitly regularizes with strength ∝1/(ηT)\propto 1/(\eta T).
  • Double descent reconciles interpolation with good generalization in overparameterized models.

Exercises

Exercise 1. Derive the ridge regression solution (equation 5) by differentiating the objective and setting to zero.

Exercise 2. Show that as λ→∞\lambda \to \infty, w^λ→0\hat{\mathbf{w}}_\lambda \to \mathbf{0}, and as λ→0\lambda \to 0, w^λ→w^OLS\hat{\mathbf{w}}_\lambda \to \hat{\mathbf{w}}_{\text{OLS}}.

Exercise 3. For a diagonal design matrix XTX=diag(σ12,…,σd2)\mathbf{X}^T\mathbf{X} = \text{diag}(\sigma_1^2, \ldots, \sigma_d^2), compute the ridge estimator's bias and variance for each coordinate.

Exercise 4. Prove that the Lasso solution for orthogonal design is the soft-thresholding operator (equation 8).

Exercise 5. Show that gradient descent with step size η\eta for TT steps on quadratic loss is equivalent to ridge with λ=1/(ηT)\lambda = 1/(\eta T) in the limit of small η\eta.

Next

Gaussian Processes