Thai-Nam Hoang

Every statistics course teaches the same lesson: models that are too complex overfit. Add enough parameters and you will memorize the training data, producing a model that generalizes poorly. The cure is regularization, cross-validation, early stopping — any technique that reins in complexity.

Modern deep learning ignores this advice completely. Neural networks routinely have more parameters than training points, are trained to zero training loss, and yet generalize remarkably well. This is not a minor violation of classical theory — it is a fundamental contradiction.

This post develops both sides: the classical theory that predicts catastrophe, and the modern empirical reality that contradicts it. The gap between them is still not fully explained, but understanding where the classical theory breaks down is the first step.

1. The Classical Bias-Variance Trade-Off

The Decomposition

Let the true relationship be $Y = f(x) + \varepsilon$ where $\varepsilon \sim (0, \sigma^2)$ is irreducible noise. We learn an estimator $\hat{f}$ from training data $S$ drawn i.i.d. from the data distribution. The test error at a fixed point $x$ decomposes as:

Theorem (Bias-Variance Decomposition). For squared loss:

$\mathbb{E}_S\left[(Y - \hat{f}(x))^2\right] = \underbrace{(f(x) - \mathbb{E}_S[\hat{f}(x)])^2}_{\text{Bias}^2} + \underbrace{\mathbb{E}_S\left[(\hat{f}(x) - \mathbb{E}_S[\hat{f}(x)])^2\right]}_{\text{Variance}} + \underbrace{\sigma^2}_{\text{irreducible}}$

Proof. Let $\bar{f}(x) = \mathbb{E}_S[\hat{f}(x)]$ and write:

$Y - \hat{f}(x) = (Y - f(x)) + (f(x) - \bar{f}(x)) + (\bar{f}(x) - \hat{f}(x))$

$= \varepsilon + \text{Bias}(x) + (\bar{f}(x) - \hat{f}(x))$

Squaring and taking $\mathbb{E}_S[\cdot]$ , the cross terms vanish: $\mathbb{E}_S[\varepsilon \cdot (\bar{f}-\hat{f})] = 0$ since $\varepsilon$ is independent of $S$ , and $\mathbb{E}_S[\varepsilon] = 0$ ; similarly $\text{Bias}(x) \cdot \mathbb{E}_S[\bar{f}-\hat{f}] = 0$ since $\bar{f}(x)$ is deterministic and $\mathbb{E}_S[\hat{f}] = \bar{f}$ . So:

$\mathbb{E}_S[(Y-\hat{f})^2] = \sigma^2 + \text{Bias}(x)^2 + \mathbb{E}_S[(\bar{f}-\hat{f})^2] \qquad \square$

The Classical Implication

Bias measures systematic error — how far the average prediction is from the truth. Simple models (e.g., linear) have high bias if the truth is nonlinear.

Variance measures sensitivity to the training set — how much $\hat{f}$ fluctuates across different datasets. Complex models (e.g., high-degree polynomials) fit the training data tightly, so they fluctuate wildly.

As model complexity increases:

Bias decreases (the model can approximate more complex functions)
Variance increases (the model fits noise in the training data)

The sum produces a U-shaped risk curve: test error is high for very simple models (high bias), decreases as complexity grows (bias reduction wins), then increases again (variance takes over). The optimal model sits at the bottom of the U.

This is Occam's Razor formalized: prefer the simplest model consistent with the data. In classical statistics, this principle has a rigorous theoretical foundation.

2. What Actually Happens with Neural Networks

The Interpolation Threshold

Define the interpolation threshold as the model complexity at which the model can exactly fit all $n$ training points — zero training loss. In classical terms, this is the worst possible point: maximum variance, and the U-curve predicts maximum test error here.

In practice, something different happens.

As model size increases past the interpolation threshold, test error does peak — confirming the classical prediction. But for sufficiently overparameterized models, test error descends again, often reaching lower values than any model on the classical U-curve.

This is the double descent curve:

Test
Error
  |         classical       second
  |          regime         descent
  |
  |    ╲                    
  |     ╲      ╱╲          ╲
  |      ╲    ╱  ╲          ╲___
  |       ╲__╱    ╲
  |                ↑
  |          interpolation
  |            threshold
  |________________________________
                          Model size / complexity

The phenomenon was named and systematized by Belkin et al. (2019), though related observations go back to the 1990s in ensemble methods and kernel machines.

Empirical Reality

On standard benchmarks (CIFAR-10, ImageNet):

ResNet models with increasing width show classic double descent as width grows
Test error at the interpolation threshold can be 10–20% worse than both smaller and larger models
Sufficiently large models achieve test error comparable to or better than the classical optimum
Training longer (more epochs) also produces double descent as a function of training time

This is not noise or a quirk of specific architectures. Double descent appears across datasets, architectures, and training procedures. It is a structural feature of modern machine learning.

3. Benign Overfitting

Double descent suggests that interpolating the training data is not inherently harmful. Benign overfitting makes this precise.

Definition. An estimator $\hat{f}$ exhibits benign overfitting if:

$\hat{f}$ interpolates the training data: $\hat{f}(x_i) = y_i$ for all $i$ (zero training error)
$\hat{f}$ achieves near-optimal test error

The Linear Case: Minimum-Norm Interpolation

Consider linear regression with $d > n$ : the system $Xw = y$ (where $X \in \mathbb{R}^{n \times d}$ ) is underdetermined — infinitely many $w$ achieve zero training loss.

Among all interpolating solutions, the minimum-norm interpolator is:

$w_{MN} = \arg\min_{w: Xw=y} \|w\|_2 = X^T(XX^T)^{-1}y = X^\dagger y$

where $X^\dagger$ is the Moore-Penrose pseudoinverse. This is what gradient descent on a zero-initialized linear model finds (we will prove this in Post 10).

When does $w_{MN}$ generalize? Suppose the true model is $w^* \in \mathbb{R}^d$ and $y = Xw^* + \varepsilon$ . The test error of $w_{MN}$ is:

$\mathbb{E}[\|w_{MN} - w^*\|^2] = \mathbb{E}[\|X^\dagger \varepsilon\|^2] + \|(\mathbb{I} - X^\dagger X)w^*\|^2$

The first term is the variance (noise amplification by $X^\dagger$ ). The second is the bias (the component of $w^*$ in the null space of $X$ , which $w_{MN}$ cannot recover).

Key insight for benign overfitting: When $d \gg n$ and the rows of $X$ are isotropic (e.g., i.i.d. Gaussian with dimension $d$ ), the smallest singular values of $X$ are $\Theta(\sqrt{d-n})$ , so $\|X^\dagger\|^2 = O(1/(d-n))$ . The variance term scales as:

$\mathbb{E}[\|X^\dagger \varepsilon\|^2] = \sigma^2 \|X^\dagger\|_F^2 \approx \sigma^2 \cdot \frac{n}{d-n} \to 0 \text{ as } d \to \infty$

When $d \gg n$ , the noise is spread across many directions and the minimum-norm solution absorbs it harmlessly. Meanwhile, the bias term goes to zero when $w^*$ is in the row space of $X$ (which happens with probability 1 for random $X$ ).

The intuition: in very high dimensions, there are many "orthogonal directions" available to absorb the noise without corrupting the signal directions. The minimum-norm interpolator exploits this — it fits the noise in directions irrelevant to the true signal.

4. Rademacher Complexity and Its Failure

Definition

The Rademacher complexity of a function class $\mathcal{F}$ on a sample $S = \{x_1, \ldots, x_n\}$ is:

$\mathcal{R}_n(\mathcal{F}) = \mathbb{E}_{\sigma}\left[\sup_{f \in \mathcal{F}} \frac{1}{n}\sum_{i=1}^n \sigma_i f(x_i)\right]$

where $\sigma_i \sim \text{Uniform}(\{-1, +1\})$ i.i.d. are Rademacher variables (random signs).

Intuition. Rademacher complexity measures how well functions in $\mathcal{F}$ can correlate with random $\pm 1$ labels. If $\mathcal{F}$ is rich enough to fit any labeling, the supremum is $1$ and $\mathcal{R}_n = 1$ . If $\mathcal{F}$ is restricted (e.g., linear functions with small norm), the supremum is controlled.

High Rademacher complexity = the class can fit noise = the model is likely to overfit.

The Generalization Bound

Theorem. With probability $\geq 1-\delta$ over the draw of training set $S$ :

$L(f) \leq \hat{L}(f) + 2\mathcal{R}_n(\mathcal{F}) + 3\sqrt{\frac{\log(2/\delta)}{2n}}$

where $L(f)$ is test loss and $\hat{L}(f)$ is training loss.

Proof sketch. The proof uses McDiarmid's inequality applied to the supremum of the empirical process $\sup_f (L(f) - \hat{L}(f))$ , symmetrized using Rademacher variables. The resulting bound on $\mathbb{E}[\sup_f(L-\hat{L})]$ is $2\mathcal{R}_n(\mathcal{F})$ . The high-probability bound follows from concentration. $\square$

The Paradox

For overparameterized neural networks, $\mathcal{R}_n(\mathcal{F}) \approx 1$ . Networks with enough parameters can fit any labeling of $n$ points — this has been verified empirically (Zhang et al., 2017: networks trained on random labels achieve zero training error). So the generalization bound becomes:

$L(f) \leq \hat{L}(f) + 2 + O\!\left(\sqrt{\frac{\log(1/\delta)}{n}}\right) \approx 3$

Since losses are typically in $[0,1]$ , this bound is completely vacuous. It says nothing. Yet the networks generalize with test error of $5\%$ on CIFAR-10.

Classical Rademacher complexity theory fails to explain deep learning generalization. The bound is tight in the worst case (there exist networks that memorize random labels), but real networks trained on real data find solutions with much better generalization than the worst case. The classical theory has no way to distinguish these cases.

5. What Actually Explains Generalization?

The classical framework asks: what is the complexity of the function class? Modern evidence suggests this is the wrong question. The right question is: which solution does the optimizer find?

Among all networks that interpolate the training data (and there are infinitely many), gradient descent finds a specific one. That specific solution tends to generalize well. The generalization is not a property of the architecture or the function class — it is a property of the optimization trajectory.

This realization motivates the next post. Gradient descent has an implicit bias — a hidden preference for particular solutions among all minimizers of the training loss. For linear models and matrix factorization, this bias can be characterized exactly. For neural networks, it remains an active area of research, but the outlines are becoming clear.

The modern view: deep learning works not despite overparameterization but because of it. Overparameterization creates a large manifold of zero-loss solutions, and gradient descent navigates this manifold in a structured way that happens to favor generalizing solutions. Regularization is implicit, not explicit.

Part of the Mathematics of Data series — mathematical notes on EE-556 at EPFL.

Double Descent and the Failure of Classical Generalization Theory