---
title: Generalization Theory
module: Theory & Frontiers
moduleNumber: 6
lessonNumber: 1
order: 601
summary: >
  Classical learning theory bounds the gap between training and test error by a
  model's capacity (VC dimension, Rademacher complexity), and predicts that a
  model with more parameters than data should overfit catastrophically. Modern
  networks do the opposite: they interpolate, even fit pure noise, and still
  generalize. We derive the classical bounds, work the bias-variance
  decomposition, show why the bounds go vacuous, and survey what replaced them:
  double descent, the interpolation threshold, margin and norm-based bounds, and
  the implicit bias of the optimizer itself.
topics: [Theory & Frontiers]
sources:
  - book: Goodfellow
    ref: "§5.2 — Capacity, Overfitting and Underfitting; §5.4.2 VC Dimension"
  - book: Goodfellow
    ref: "Ch. 7 — Regularization for Deep Learning"
  - book: Goodfellow
    ref: "§5.5 — Maximum Likelihood Estimation; §5.4 Estimators, Bias, Variance"
---

Everything else in this subject is machinery for driving the **training** loss
down. Generalization theory addresses the question that remains once the training
loss is small: does a low loss on the sample $\mathcal{D} = \{(x_i, y_i)\}_{i=1}^n$
say anything about loss on data we have not seen? Write the two quantities the
theory compares, the **empirical risk** on the sample and the **population risk**
under the true distribution $\mathcal{P}$,

$$
\hat R(\theta) = \frac{1}{n}\sum_{i=1}^n \ell\parens{f_\theta(x_i), y_i},
\qquad
R(\theta) = \mathbb{E}_{(x,y)\sim\mathcal{P}}\brackets{\ell(f_\theta(x), y)}.
$$

Training minimizes $\hat R$; we care about $R$. The **generalization gap** is the
difference $R(\theta) - \hat R(\theta)$, and the entire classical program is one
move: bound that gap by something we can compute or control.

> **Definition (Generalization gap).** For a model $f_\theta$ with empirical risk
> $\hat R(\theta)$ on $n$ i.i.d. samples and population risk $R(\theta)$, the
> generalization gap is $R(\theta) - \hat R(\theta)$. A learner generalizes when
> this gap is small; it overfits when $\hat R$ is small but the gap is large.

The empirical risk is an unbiased estimate of the population risk for any _fixed_
$\theta$ chosen before seeing the data: $\mathbb{E}_{\mathcal D}[\hat R(\theta)] =
R(\theta)$ by linearity, since each term $\ell(f_\theta(x_i),y_i)$ is an i.i.d.
draw with mean $R(\theta)$. The difficulty is that training _chooses_ $\hat\theta$
by looking at the sample, so $\hat\theta$ and $\mathcal{D}$ are dependent and the
unbiasedness breaks. The learner picks whichever function happened to fit the
particular noise in this sample, and $\hat R(\hat\theta)$ is optimistically low.
Every bound below accounts for that dependence by controlling the gap
_uniformly_ over the whole class the optimizer could have selected from, not just
at one fixed point.

## Classical theory: capacity controls the gap

The classical answer is that the gap is governed not by the single function the
optimizer returns but by the **richness of the hypothesis class** $\mathcal{H}$ it
was chosen from.[^gf-capacity] A learner that searches a tiny class cannot overfit
much, because there are not enough functions to fit the noise; a learner with a
vast class can fit anything, including the noise, and the noise does not transfer
to test data.

> **Definition (Capacity).** The capacity of a hypothesis class $\mathcal{H}$ is a
> measure of how many distinct labelings of a dataset its members can realize.
> Higher capacity means $\mathcal{H}$ can fit more intricate patterns, and more
> noise. Goodfellow §5.2 frames the whole bias–variance story around it.

The sharpest combinatorial measure of capacity for binary classifiers is the
**Vapnik–Chervonenkis dimension**: the size of the largest set of points the class
can label in _every_ possible way.

> **Definition (Shattering, VC dimension).** A set $S = \{x_1,\dots,x_m\}$ is
> shattered by $\mathcal{H}$ if for every one of the $2^m$ labelings of $S$ there
> is some $h \in \mathcal{H}$ realizing it. The VC dimension $d_{\mathrm{VC}}
> (\mathcal{H})$ is the cardinality of the largest shattered set (possibly
> infinite).

Take the concrete case of linear classifiers in the plane. Three points in general
position can be shattered: for each of the $2^3 = 8$ sign patterns there is a line
putting the $+$ points on one side and the $-$ points on the other. Four points
cannot: label two diagonal points $+$ and the other two $-$ (the XOR pattern) and
no line separates them. So $d_{\mathrm{VC}} = 3$ for lines in $\mathbb{R}^2$, and
in general $d_{\mathrm{VC}} = d + 1$ for a linear classifier in $\mathbb{R}^d$ with
a bias term.

$$
% caption: VC dimension of lines in the plane. Any of the $2^3=8$ labelings of three points is realized by some line, so three points are shattered; the XOR labeling of four points admits no separating line, so $d_{\mathrm{VC}}=3$.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{grn}{HTML}{1F9D4D}
  \definecolor{rd}{HTML}{C0392B}
  % ---- left panel: 3 points, one labeling, separated by a line ----
  \begin{scope}[shift={(0,0)}]
    \node[anchor=south, font=\footnotesize] at (1.5,2.7) {\texttt{3 points: shattered}};
    \draw[black] (0,0) rectangle (3,2.4);
    % separating line
    \draw[acc, very thick] (0.3,2.1) -- (2.7,0.15);
    % + points (green, white plus), - point (red, white minus)
    \fill[grn] (0.7,0.6) circle (5pt);
    \node[white, font=\scriptsize] at (0.7,0.6) {+};
    \fill[grn] (1.35,0.5) circle (5pt);
    \node[white, font=\scriptsize] at (1.35,0.5) {+};
    \fill[rd] (2.1,1.7) circle (5pt);
    \draw[white, line width=1pt] (1.94,1.7) -- (2.26,1.7);
  \end{scope}
  % ---- right panel: 4 points, XOR, no separating line ----
  \begin{scope}[shift={(4.4,0)}]
    \node[anchor=south, font=\footnotesize] at (1.5,2.7) {\texttt{4 points: XOR}};
    \draw[black] (0,0) rectangle (3,2.4);
    % corners
    \fill[grn] (0.5,0.5) circle (5pt);
    \node[white, font=\scriptsize] at (0.5,0.5) {+};
    \fill[rd] (2.5,0.5) circle (5pt);
    \draw[white, line width=1pt] (2.34,0.5) -- (2.66,0.5);
    \fill[rd] (0.5,1.9) circle (5pt);
    \draw[white, line width=1pt] (0.34,1.9) -- (0.66,1.9);
    \fill[grn] (2.5,1.9) circle (5pt);
    \node[white, font=\scriptsize] at (2.5,1.9) {+};
    % a candidate line that fails
    \draw[acc, very thick, dashed] (0.15,1.3) -- (2.85,1.1);
    \node[acc, anchor=north, font=\footnotesize] at (1.5,1.0) {\texttt{no line works}};
  \end{scope}
\end{tikzpicture}
$$

Capacity for this family equals the parameter count, and that coincidence is
the intuition classical theory leans on. The central result turns VC dimension into
a uniform bound on the gap.

> **Theorem (VC generalization bound).** Let $\mathcal{H}$ have VC dimension
> $d_{\mathrm{VC}} = C$ and let $\hat R, R$ be the empirical and population
> $0\text{–}1$ risk on $n$ i.i.d. samples. Then with probability at least
> $1-\delta$, _simultaneously for every_ $h \in \mathcal{H}$,
> $$
> R(h) \;\le\; \hat R(h) \;+\; O\!\parens{\sqrt{\frac{C\,\log(n/C) + \log(1/\delta)}{n}}}.
> $$

Deep networks break the mechanism behind the "simultaneously for every $h$"
guarantee. If $\mathcal{H}$ were a _finite_ set of $M$
functions, each fixed $h$ has $\Pr[R(h) - \hat R(h) > \varepsilon] \le e^{-2n
\varepsilon^2}$ by Hoeffding's inequality (the empirical risk is an average of $n$
bounded i.i.d. terms). A union bound over all $M$ functions gives $\Pr[\exists h :
R(h) - \hat R(h) > \varepsilon] \le M e^{-2n\varepsilon^2}$; setting the right side
to $\delta$ and solving for $\varepsilon$ yields a uniform gap of order
$\sqrt{(\log M + \log(1/\delta))/n}$. The log-cardinality $\log M$ is the capacity.
The Sauer–Shelah lemma extends this to infinite classes: a class of VC dimension
$C$ realizes at most $O(n^C)$ distinct labelings on any $n$ points, so
$\log M \rightsquigarrow C\log n$ takes the place of $\log M$, giving the theorem's
$\sqrt{C\log(n/C)/n}$.

Stripped of the logarithmic and confidence terms, the bound has the shape the
whole field quotes:

$$
\;R(\theta) \;\le\; \hat R(\theta) \;+\; O\!\parens{\sqrt{\tfrac{C}{n}}}\;
\qquad
\begin{aligned}
&C = \text{capacity (e.g. } d_{\mathrm{VC}}),\\
&n = \text{number of samples.}
\end{aligned}
$$

Two terms trade off: $\hat R$ falls as capacity $C$ rises
(a richer class fits the sample better), while the gap term $\sqrt{C/n}$ rises with
$C$. Their sum is U-shaped in capacity, minimized at an intermediate "sweet spot",
the classical bias–variance tradeoff.[^gf-biasvar]

$$
% caption: Classical bias--variance: training risk falls and the gap term grows with capacity, so test risk is U-shaped with an intermediate sweet spot.
\begin{tikzpicture}[>=stealth, font=\footnotesize, scale=1.0]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9D4D}
  \definecolor{red}{HTML}{C0392B}
  % axes
  \draw[->, thick] (0,0) -- (7.4,0) node[right, font=\footnotesize] {capacity};
  \draw[->, thick] (0,0) -- (0,4.6) node[above, font=\footnotesize] {risk};
  % training risk: decreasing
  \draw[green, very thick] plot[domain=0.35:7, samples=60] (\x, {3.6/(\x*0.7+0.5)});
  \node[green, anchor=west] at (5.0,0.3) {\texttt{train risk}};
  % gap term sqrt(C/n): increasing
  \draw[acc, very thick] plot[domain=0.2:7, samples=60] (\x, {1.05*sqrt(\x)});
  \node[acc, anchor=north, align=center, font=\footnotesize] at (5.3,1.85) {\texttt{gap term}\\\texttt{(grows with C)}};
  % test risk = sum: U-shaped
  \draw[red, very thick] plot[domain=0.35:7, samples=70] (\x, {3.6/(\x*0.7+0.5) + 1.05*sqrt(\x)});
  \node[red, anchor=west] at (4.2,3.95) {\texttt{test risk}};
  % sweet spot marker at the U minimum (x ~ 3.5, where red curve bottoms)
  \draw[black, dashed] (3.5,0) -- (3.5,3.18);
  \node[black, anchor=north, font=\footnotesize] at (3.5,-0.05) {\texttt{sweet spot}};
  \fill[red] (3.5,3.18) circle (2.4pt);
\end{tikzpicture}
$$

### The bias–variance decomposition

The U-shape has an exact algebraic source. Fix a query point $x$, let $y = g(x) +
\epsilon$ with noise $\mathbb{E}[\epsilon]=0$, $\mathrm{Var}(\epsilon)=\sigma^2$,
and let $\hat f = \hat f_{\mathcal{D}}$ be the model fit on a random training set
$\mathcal{D}$. The expected squared error at $x$, averaged over both the label noise
and the draw of $\mathcal{D}$, decomposes into three non-negative pieces:

$$
\mathbb{E}_{\mathcal{D},\epsilon}\!\brackets{(y - \hat f(x))^2}
=
\underbrace{\parens{g(x) - \mathbb{E}_{\mathcal D}[\hat f(x)]}^2}_{\text{bias}^2}
\;+\;
\underbrace{\mathbb{E}_{\mathcal D}\!\brackets{\parens{\hat f(x) - \mathbb{E}_{\mathcal D}[\hat f(x)]}^2}}_{\text{variance}}
\;+\;
\underbrace{\sigma^2}_{\text{noise}}.
$$

The cross terms vanish: $\epsilon$ is independent of $\hat f$ and mean-zero, and
the split of $(g - \hat f)$ around $\mathbb{E}[\hat f]$ leaves a zero-mean residual
that is uncorrelated with the constant bias. **Bias** is the error a low-capacity
class cannot avoid even with infinite data — its best member is still far from $g$.
**Variance** is how much $\hat f$ swings as the sample is redrawn — a high-capacity
class chases the sample noise, so its predictions are unstable. **Noise** $\sigma^2$
is irreducible. Raising capacity lowers bias and raises variance; the sum is
U-shaped, and the sweet spot is where the two derivatives cancel. This is the same
U as the VC budget, seen through squared error instead of a uniform bound.[^gf-biasvar]

A second, distribution-aware measure replaces the worst-case combinatorics of VC
with an average over the actual data: **Rademacher complexity** measures how well
the class can fit a labeling of pure random signs.

> **Definition (Rademacher complexity).** For a sample $S = \{x_1,\dots,x_n\}$ and
> independent random signs $\varsigma_i \in \{-1,+1\}$ drawn uniformly, the
> empirical Rademacher complexity of $\mathcal{H}$ is
> $$
> \widehat{\mathfrak{R}}_S(\mathcal{H})
> = \mathbb{E}_{\varsigma}\!\brackets{\sup_{h\in\mathcal{H}} \frac{1}{n}\sum_{i=1}^n \varsigma_i\, h(x_i)}.
> $$
> It is the expected best correlation between a class member and a random
> labeling, large when $\mathcal{H}$ can mimic noise.

Consider two extreme cases. A single constant function has
$\widehat{\mathfrak{R}}_S = 0$: the sum $\frac1n\sum \varsigma_i h(x_i) = h\cdot
\frac1n\sum\varsigma_i$ has expectation zero because the signs average out. A class
that can hit any target on the sample has $\widehat{\mathfrak{R}}_S = 1$: it sets
$h(x_i) = \varsigma_i$ for every draw, so the correlation is $\frac1n\sum
\varsigma_i^2 = 1$. Rademacher complexity thus interpolates between $0$ and $1$ as
the class goes from trivial to able-to-shatter, and it plugs straight into a bound.

> **Theorem (Rademacher generalization bound).** With probability at least
> $1-\delta$, simultaneously for all $h \in \mathcal{H}$ with loss in $[0,1]$,
> $$
> R(h) \;\le\; \hat R(h) \;+\; 2\,\widehat{\mathfrak{R}}_S(\mathcal{H})
> \;+\; 3\sqrt{\frac{\log(2/\delta)}{2n}}.
> $$

For linear predictors with $\norm{w}\le B$ over inputs with $\norm{x}\le X$, one
can show $\widehat{\mathfrak{R}}_S \le BX/\sqrt{n}$: the complexity is controlled
by the _norm_ $B$, not the ambient dimension $d$. That norm dependence is what
carries over to the modern setting: it remains meaningful in high dimension, where
the dimension-based VC bound does not.

Both theorems are valid and both are tight for the classes they were built for:
linear models, kernel machines, shallow trees. Their common shape, gap $\le
O(\sqrt{C/n})$, predicts that capacity exceeding the sample size is fatal. Deep
networks break that prediction so completely that the bounds become numbers larger
than one and tell us nothing.

## The deep-learning puzzle

Modern networks live in a regime classical theory was never meant to describe.
Their parameter count $p$ (and any reasonable capacity surrogate) vastly exceeds
the sample size $n$. They are **overparameterized**.[^postdate]

> **Definition (Overparameterization).** A model is overparameterized when it has
> more free parameters than training examples, $p \gg n$, so that infinitely many
> parameter settings achieve zero training loss. The set of such global minimizers
> is a high-dimensional manifold, not a point.

For example, a residual image network can carry
$p \approx 2.5\times 10^7$ parameters and train on $n \approx 5\times 10^4$
labeled images, so $p/n \approx 500$. The VC dimension of a piecewise-linear
network grows at least linearly in $p$, so $\sqrt{d_{\mathrm{VC}}/n} \gtrsim
\sqrt{500} \approx 22$: the bound guarantees a gap of at most $22$, on a risk that
lives in $[0,1]$. The bound is vacuous.

Two facts about these models cannot both be accommodated by the classical bound,
and together they are the central tension of the field. The post-2016 literature
that established them is more recent than Goodfellow's textbook, which still
presents capacity control as the operative theory.

> **Fact (Networks fit random labels).** A standard image network trained on a
> dataset whose labels have been replaced by uniform random noise reaches _zero_
> training error. Its effective capacity is therefore large enough to memorize an
> arbitrary labeling of the training set — exactly the condition VC theory calls
> "able to shatter the sample."

If the class can shatter the training set, then $\widehat{\mathfrak{R}}_S \approx 1$
and $d_{\mathrm{VC}} \gtrsim n$, so the bound term $\sqrt{C/n}$ is $\Omega(1)$: the
guaranteed gap is at least a constant, and $R(\theta) \le \hat R(\theta) + 1$ is
vacuous because risk already lives in $[0,1]$.

> **Fact (...yet they generalize on real data).** The _same_ architecture, _same_
> optimizer, and _same_ epoch budget that memorizes random labels instead learns a
> function with a small generalization gap when trained on the _true_ labels. The
> model has the capacity to memorize but, on structured data, does not have to.

The two facts isolate the puzzle precisely: capacity is necessary to explain the
random-label result and useless to explain the real-data result. Whatever controls
the gap on real data, it is not the size of $\mathcal{H}$.

$$
% caption: The model drives training risk to zero on both real and random labels, yet the test gap is small on real labels and near-chance on random ones.
\begin{tikzpicture}[>=stealth, font=\footnotesize, scale=1.0]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9D4D}
  \definecolor{red}{HTML}{C0392B}
  % axes
  \draw[->, thick] (0,0) -- (7.4,0) node[right, font=\footnotesize] {training epoch};
  \draw[->, thick] (0,0) -- (0,4.4) node[above, font=\footnotesize] {error};
  \node[anchor=east, font=\footnotesize] at (-0.05,4.0) {\texttt{high}};
  \node[anchor=east, font=\scriptsize] at (-0.05,0.0) {0};
  % train error real: -> 0
  \draw[green, very thick] plot[domain=0.2:7, samples=50] (\x, {4.0*exp(-1.1*\x)});
  \node[green, anchor=west, font=\footnotesize] at (1.7,0.35) {\texttt{train (real)}};
  % train error random: -> 0 slower
  \draw[green, very thick, dashed] plot[domain=0.2:7, samples=50] (\x, {4.0*exp(-0.55*\x)});
  \node[green, anchor=west, font=\footnotesize] at (2.55,1.85) {\texttt{train (random)}};
  % test error real: settles low
  \draw[acc, very thick] plot[domain=0.2:7, samples=50] (\x, {0.9 + 1.6*exp(-1.0*\x)});
  \node[acc, anchor=west, font=\footnotesize] at (5.1,0.74) {\texttt{test (real)}};
  % test error random: stays high (chance)
  \draw[red, very thick] plot[domain=0.2:7, samples=50] (\x, {3.5 - 0.12*\x});
  \node[red, anchor=south, font=\footnotesize] at (3.0,3.1) {\texttt{test (random)}};
\end{tikzpicture}
$$

## Double descent

The cleanest empirical refutation of the classical U-curve is **double descent**.
Sweep model size from tiny to huge and plot test error. At first the classical
story holds: test error falls, then rises as the model begins to overfit, peaking
right where the model becomes just barely able to fit the training set. Past that
point, the regime classical theory forbids, test error _falls again_, often
below the classical sweet spot.

> **Definition (Interpolation threshold).** The model size at which the network
> first achieves zero training error — it exactly _interpolates_ the training set.
> Below it the model is underparameterized and cannot fit the data; above it the
> model is overparameterized and many zero-error solutions exist. The double-descent
> peak sits at this threshold.

$$
% caption: Double descent: test risk follows the classical U, spikes at the interpolation threshold, then descends a second time in the overparameterized regime $p > n$.
\begin{tikzpicture}[>=stealth, font=\footnotesize, scale=1.0]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \definecolor{green}{HTML}{1F9D4D}
  % axes
  \draw[->, thick] (0,0) -- (9.0,0) node[right, font=\footnotesize] {model size (params)};
  \draw[->, thick] (0,0) -- (0,4.6) node[above, font=\footnotesize] {test risk};
  % interpolation threshold marker
  \draw[black, dashed] (4.3,0) -- (4.3,4.3);
  \node[black, anchor=south, align=center, font=\footnotesize] at (4.3,4.25) {\texttt{interpolation}\\\texttt{threshold}};
  % regime labels
  \node[black, anchor=north, font=\footnotesize] at (2.1,-0.05) {\texttt{under-param.}};
  \node[black, anchor=north, font=\footnotesize] at (6.7,-0.05) {\texttt{over-param.} ($p > n$)};
  % classical U (left of threshold): down then up to spike
  \draw[red, very thick] plot[domain=0.4:4.3, samples=60]
    (\x, {1.1 + 1.7/(\x+0.4) + 0.42*(\x)*(\x)/4.0});
  % spike continues into descent (right of threshold): steep drop then flat-ish
  \draw[red, very thick] plot[domain=4.3:8.6, samples=70]
    (\x, {1.05 + 2.3*exp(-1.3*(\x-4.3)) });
  % marker dots: classical min (left U bottom ~ x=1.6) and modern min
  \fill[red] (1.6,2.07) circle (2.2pt);
  \node[red, anchor=west, font=\footnotesize] at (0.45,1.45) {\texttt{classical min}};
  \fill[green] (8.2,1.06) circle (2.6pt);
  \node[green, anchor=south, font=\footnotesize] at (7.7,1.7) {\texttt{modern min}};
\end{tikzpicture}
$$

Why the second descent happens is the active question. The working explanation is
that beyond the threshold there is a _choice_ of zero-error solution, and the
optimizer picks a simple one rather than an arbitrary one. At the threshold
itself there is essentially a unique interpolating solution and the optimizer is
forced into it, however contorted; that forced, brittle fit is the spike. With
more parameters, the optimizer finds a smoother interpolant, and test error drops.

The same peak appears when the axis is _training time_ or _data size_ rather than
model width, which is why the phenomenon is read as being about the ratio of
effective capacity to sample size, $C/n$, crossing $1$ — not about parameter count
alone. The peak sits wherever the model is _just_ able to interpolate, whichever
knob pushed it there.

> **Remark (A capacity surrogate that does not double-descend).** The phenomenon
> motivates measuring capacity by quantities the optimizer actually controls — the
> _norm_ of the learned weights, or the _margin_, rather than the parameter count.
> Norm-based complexity grows then shrinks across the threshold, tracking the
> double-descent curve where parameter-counting fails.

## Margin and norm-based bounds

The Rademacher bound already hinted at the fix: for linear predictors the
complexity was $BX/\sqrt n$, controlled by the weight norm $B$ and not the
dimension. The margin turns this into a bound that stays finite for interpolating
networks. Define the **margin** of a correctly classified example as the gap
between the score of the true class and the best competing class,

$$
\gamma_i = f_{y_i}(x_i) - \max_{k \ne y_i} f_k(x_i),
$$

and let $\gamma$ be the margin achieved on the whole sample. A predictor that
separates the data with a large margin sits far from every decision boundary, so
small perturbations of the input do not flip its label — a smoothness property that
transfers to unseen points.

> **Theorem (Margin bound, schematic).** For a network with weight matrices of
> spectral norms $\norm{W_\ell}$, with probability $\ge 1-\delta$ the
> misclassification risk obeys
> $$
> R_{0/1}(f) \;\le\; \hat R_\gamma(f) \;+\; \tilde O\!\parens{\frac{\prod_\ell \norm{W_\ell}\,\cdot\, r}{\gamma\,\sqrt n}},
> $$
> where $\hat R_\gamma$ is the fraction of training points with margin below
> $\gamma$ and $r$ collects the (weaker) dependence on architecture.

The numerator measures the size of the function; the denominator, its distance
from the boundary. Two networks with identical parameter counts can differ
by orders of magnitude in $\prod_\ell\norm{W_\ell}/\gamma$: the one the optimizer
happens to find on real data has small weight norm and large margin, so its bound
is small; the one that memorizes random labels needs enormous weights to force the
contorted fit, so its bound is large. Parameter counting cannot tell them apart;
the norm-over-margin ratio can. This is the same quantity that shrinks past the
interpolation threshold and tracks the second descent.

$$
% caption: A large-margin separator (right) leaves a wide corridor around the boundary, so nearby test points keep their labels; a small-margin fit (left) threads between points and flips labels under tiny shifts.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{grn}{HTML}{1F9D4D}
  \definecolor{rd}{HTML}{C0392B}
  % ---- left: small margin ----
  \begin{scope}[shift={(0,0)}]
    \node[anchor=south, font=\footnotesize] at (1.6,3.2) {\texttt{small margin}};
    \draw[black] (0,0) rectangle (3.2,3.0);
    % wiggly tight boundary
    \draw[acc, very thick] (0.1,2.6) .. controls (1.4,1.2) and (1.8,2.2) .. (3.1,0.6);
    % points close to boundary
    \fill[grn] (0.6,0.7) circle (2.6pt);
    \fill[grn] (1.5,0.9) circle (2.6pt);
    \fill[grn] (1.1,1.5) circle (2.6pt);
    \fill[rd] (1.9,2.4) circle (2.6pt);
    \fill[rd] (2.5,1.6) circle (2.6pt);
    \fill[rd] (0.9,2.3) circle (2.6pt);
    \node[black, anchor=north, font=\footnotesize] at (1.6,-0.05) {\texttt{flips easily}};
  \end{scope}
  % ---- right: large margin ----
  \begin{scope}[shift={(4.6,0)}]
    \node[anchor=south, font=\footnotesize] at (1.6,3.2) {\texttt{large margin}};
    \draw[black] (0,0) rectangle (3.2,3.0);
    % straight boundary
    \draw[acc, very thick] (0.3,2.7) -- (2.9,0.3);
    % margin corridor
    \draw[acc!45, dashed] (0.75,2.85) -- (3.05,0.75);
    \draw[acc!45, dashed] (-0.05,2.25) -- (2.55,-0.05);
    % points far from boundary
    \fill[grn] (0.55,0.55) circle (2.6pt);
    \fill[grn] (1.15,0.5) circle (2.6pt);
    \fill[grn] (0.5,1.1) circle (2.6pt);
    \fill[rd] (2.6,2.4) circle (2.6pt);
    \fill[rd] (2.0,2.6) circle (2.6pt);
    \fill[rd] (2.65,1.8) circle (2.6pt);
    \node[black, anchor=north, font=\footnotesize] at (1.6,-0.05) {\texttt{stable}};
  \end{scope}
\end{tikzpicture}
$$

## Implicit regularization

The missing ingredient is that the **optimizer is not neutral**. Among the
infinitely many parameter vectors that interpolate the training data, gradient
descent does not return a random one; its trajectory is biased toward a particular,
well-behaved corner of the solution manifold. This is **implicit regularization**:
a preference for simple solutions that nobody wrote into the loss.[^gf-reg]

> **Definition (Implicit regularization).** The tendency of an optimization
> procedure (gradient descent, SGD) to converge to solutions with special
> structure (low norm, large margin, flat curvature) among all those that minimize
> the training loss, without any explicit penalty term enforcing that structure.

The canonical exact result is for the simplest interpolating problem, where the bias
can be named precisely.

> **Theorem (Implicit bias of gradient descent, separable case).** For logistic
> regression on linearly separable data, gradient descent on the (unregularized)
> empirical loss drives $\norm{w_t} \to \infty$, but the _direction_
> $w_t / \norm{w_t}$ converges to the **maximum-margin** separator — the same
> solution a hard-margin SVM returns. The optimizer regularizes toward maximum
> margin with no margin term in the objective.

> **Proof (sketch).** On separable data no finite $w$ achieves zero logistic loss,
> so $\norm{w_t}$ diverges as the loss is pushed toward $0$. The loss is
> dominated by the example with the _smallest_ margin $y_i\, w^\top x_i$, since the
> logistic tail $\log(1+e^{-z})\approx e^{-z}$ decays fastest for the largest $z$.
> Minimizing therefore pours all reduction into raising the worst-case margin, i.e.
> maximizing $\min_i y_i\,(w/\norm{w})^\top x_i$. The normalized iterate
> converges to the maximizer of that minimum margin. $\qed$

To see the tail argument in coordinates, write the gradient of the logistic loss,
$\nabla \hat R(w) = -\frac1n\sum_i y_i x_i\, \sigma(-y_i w^\top x_i)$ with $\sigma$
the logistic sigmoid. Once the data is separated, every $y_i w^\top x_i > 0$, and
$\sigma(-z) \approx e^{-z}$ for large $z$, so the weight $e^{-y_i w^\top x_i}$ on
example $i$ is exponentially smaller for well-separated points than for the
worst-margin point. The gradient is therefore, up to a vanishing remainder, a
combination of the few smallest-margin examples — the support vectors — and $w_t$
grows in exactly the direction that pushes those margins up. The endpoint is the
max-margin direction, reached with no penalty term.

For deep networks no such clean theorem exists, but the same flavor of bias is
observed empirically and connects directly to the geometry of the loss surface from
[the optimization landscape](/deep-learning/optimization/the-optimization-landscape):
SGD prefers **flat minima**, regions where the loss is insensitive to small
parameter perturbations, over sharp ones. Flatness is a stability property, and
stability bounds generalization: a function that barely changes when the parameters
wobble also barely changes when the training set is resampled.

The minibatch noise supplies the mechanism. An SGD update is the full gradient plus
a zero-mean stochastic term whose covariance scales with the local loss curvature.
In a sharp basin that noise kicks the iterate up the steep walls and out; in a wide
flat basin the same noise is absorbed. The stationary distribution of the SGD
iterate therefore concentrates in flat regions — an entropic pull toward flatness
that is stronger the larger the learning-rate-to-batch-size ratio.

$$
% caption: Implicit bias: among the many interpolating minima, minibatch noise drives SGD into the wide flat basin rather than the narrow sharp one.
\begin{tikzpicture}[>=stealth, font=\footnotesize, scale=1.0]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9D4D}
  \definecolor{red}{HTML}{C0392B}
  % axes
  \draw[->, thick] (0,0) -- (9.0,0) node[right, font=\footnotesize] {parameters};
  \draw[->, thick] (0,0) -- (0,3.9) node[above, font=\footnotesize] {train loss};
  % a double-well landscape: sharp minimum (left) and flat minimum (right)
  % sharp narrow well around x=2
  \draw[black, very thick] plot[domain=0.3:3.3, samples=80]
    (\x, {0.35 + 2.6*(\x-2.0)*(\x-2.0)});
  % flat wide well around x=6.4
  \draw[black, very thick] plot[domain=4.2:8.6, samples=90]
    (\x, {0.35 + 0.28*(\x-6.4)*(\x-6.4)});
  % connecting ridge
  \draw[black, very thick] plot[domain=3.3:4.2, samples=30]
    (\x, {0.35 + 2.6*(3.3-2.0)*(3.3-2.0) - (\x-3.3)/0.9*((2.6*(3.3-2.0)*(3.3-2.0)) - (0.28*(4.2-6.4)*(4.2-6.4)))});
  % sharp minimum point + label
  \fill[red] (2.0,0.35) circle (2.6pt);
  \node[red, anchor=south, align=center, font=\footnotesize] at (2.55,0.62) {\texttt{sharp min}\\\texttt{(poor test)}};
  % flat minimum point selected by SGD + label
  \fill[green] (6.4,0.35) circle (2.8pt);
  \node[green, anchor=south, align=center, font=\footnotesize] at (6.4,0.62) {\texttt{flat min}\\\texttt{(SGD picks this)}};
  % zero-train-loss line
  \draw[acc, dashed] (0,0.35) -- (8.7,0.35);
  \node[acc, anchor=south west, font=\footnotesize] at (0.15,0.42) {\texttt{train loss} $= 0$};
\end{tikzpicture}
$$

Optimization and generalization are therefore **entangled** in deep learning in a
way they are not in convex learning. For a convex objective every minimizer is
equally good and the optimizer is just a means to reach the unique answer; for an
overparameterized network the optimizer _selects_ which of many zero-loss answers
you get, so the choice of algorithm is itself a regularizer. There is no clean
separation between "how we optimize" and "how well we generalize."

## The interpolation regime

The practical upshot inverts the classical rule: zero
training error is not, by itself, a sign of overfitting. In the
overparameterized regime, pushing the model past the interpolation threshold and
_continuing_ to grow it keeps improving test error even though training error has
already bottomed out at zero.

$$
% caption: Past the interpolation threshold train error stays at zero while test error keeps falling as the model grows: bigger is better.
\begin{tikzpicture}[>=stealth, font=\footnotesize, scale=1.0]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9D4D}
  \definecolor{red}{HTML}{C0392B}
  % axes
  \draw[->, thick] (0,0) -- (8.6,0) node[right, font=\footnotesize] {model size};
  \draw[->, thick] (0,0) -- (0,4.4) node[above, font=\footnotesize] {error};
  % interpolation threshold
  \draw[black, dashed] (3.2,0) -- (3.2,4.1);
  \node[black, anchor=south, align=center, font=\footnotesize] at (3.2,4.05) {\texttt{threshold}};
  % train error: falls to 0 at threshold then stays 0
  \draw[green, very thick] plot[domain=0.3:3.2, samples=40] (\x, {3.6*exp(-1.3*\x)});
  \draw[green, very thick] (3.2,{3.6*exp(-1.3*3.2)}) -- (8.3,0.06);
  \node[green, anchor=south, font=\footnotesize] at (5.8,0.12) {\texttt{train error} $= 0$};
  % test error: keeps falling past threshold
  \draw[acc, very thick] plot[domain=0.3:8.3, samples=70] (\x, {0.85 + 2.6*exp(-0.45*\x)});
  \node[acc, anchor=west, font=\footnotesize] at (5.9,0.62) {\texttt{test error}};
  % arrow emphasizing continued improvement
  \draw[red, ->, thick] (4.0,1.95) -- (7.2,1.02);
  \node[red, anchor=south west, font=\footnotesize] at (4.7,2.0) {\texttt{bigger still helps}};
\end{tikzpicture}
$$

This is why the dominant practical recipe is to make models as large as compute
allows and lean on [regularization](/deep-learning/regularization/regularization-overview),
explicit (weight decay, [dropout](/deep-learning/regularization/dropout-and-data-augmentation))
and implicit (SGD, [early stopping](/deep-learning/regularization/early-stopping-and-parameter-sharing)),
to steer the interpolating solution toward the well-behaved corner, rather than
to shrink the model to fit a capacity budget.[^chollet-overfit] The regularizers do
not reduce capacity; they bias the search _within_ the huge class toward the
low-norm, large-margin, flat solutions the bounds above favor.

> **Takeaway.** In the overparameterized regime, zero training error is not
> overfitting — it is interpolation, and the test error is set by _which_
> interpolating solution the optimizer lands on. Grow the model, then bias the
> search (SGD, weight decay, early stopping) toward low norm and large margin;
> do not shrink the model to fit a VC budget.

## Classical versus modern

The two views disagree on every major question. The classical column
is Goodfellow §5.2; the modern column post-dates Goodfellow (2016).

| Question | Classical view | Modern (overparameterized) view |
| --- | --- | --- |
| What controls the gap? | hypothesis-class capacity ($d_{\mathrm{VC}}$, Rademacher) | implicit bias of the optimizer (norm, margin, flatness) |
| Effect of more parameters than data | catastrophic overfitting | often _improves_ test error (second descent) |
| Test error vs. model size | U-shaped; stop at the sweet spot | double descent; grow past the threshold |
| Zero training error means | overfitting (a red flag) | interpolation (routine, often optimal) |
| Role of the optimizer | a neutral means to a unique minimum | a regularizer that _selects_ among many minima |
| Are the bounds tight? | yes, for linear / kernel / tree classes | vacuous for deep nets ($\sqrt{C/n} = \Omega(1)$) |
| How to control overfitting | restrict the class (fewer parameters) | keep the class huge; bias the search (SGD, weight decay) |

## The papers behind the puzzle

Goodfellow §5.2 presents capacity control as the operative theory; every result in
this lesson that contradicts it comes from the public literature that appeared after
the 2016 text, and the citations are worth naming. The empirical trigger was
**"Understanding deep learning requires rethinking generalization"** (Zhang et al.,
2017), the random-label experiment above: the demonstration that standard networks
memorize pure noise to zero training error, which is what rendered the VC and
Rademacher bounds vacuous in the regime that matters. **Double descent** was named
and generalized by Belkin et al. (2019) and mapped across model size, data size, and
training time by Nakkiran et al. (2020), establishing that the classical U-curve is
only the left half of the picture.

The constructive replies came in two families. **Margin- and norm-based bounds**
(Bartlett, Foster & Telgarsky, 2017) replaced the parameter count with the product
of spectral norms over the margin — the $\prod_\ell\norm{W_\ell}/\gamma$ quantity
above — giving a complexity measure that stays finite for interpolating networks and
tracks the second descent. **Implicit bias** was characterized exactly for the
separable-logistic case by Soudry et al. (2018), whose result that gradient descent
converges in direction to the max-margin separator is the theorem this lesson
sketched, and connected to **flat minima** and generalization through the stability
lens (Keskar et al., 2017, on the sharp-minima cost of large-batch training). No
single paper yet closes the loop into a predictive, algorithm-dependent theory, but
together these mark the shift from "count the functions the class contains" to
"characterize the function the optimizer returns."

## What the theory has and has not settled

The classical bounds are valid, and tight for the families
they were derived for. What fails is their _relevance_: capacity is the wrong knob
for overparameterized networks because the optimizer, not the class, picks the
function. A predictive theory of deep generalization is still open, but its shape is
clear: it must be **algorithm-dependent**, folding the trajectory of SGD and the
geometry of the minimum it finds into the bound, not just counting the functions the
architecture _could_ in principle represent. The norm- and margin-based bounds are
the first honest step in that direction, because they measure the function the
optimizer actually returned rather than the class it was drawn from.

The threads this opens are picked up across the rest of the module: the brittleness
that survives small test error in [adversarial robustness](/deep-learning/theory/adversarial-robustness),
the use of the solution manifold's width to quantify uncertainty in
[Bayesian and ensemble methods](/deep-learning/theory/bayesian-and-ensemble-methods),
and the limit of infinite implicit depth in
[deep equilibrium models](/deep-learning/theory/deep-equilibrium-models). The
single idea underneath all of them is the one this lesson isolated: in the
overparameterized world, _how_ you search the hypothesis class matters more than
_how big_ it is.

[^gf-capacity]: **Goodfellow**, _Deep Learning_, §5.2 — Capacity, Overfitting and Underfitting: the representational capacity of a hypothesis class as the knob governing the train/test gap.
[^gf-biasvar]: **Goodfellow**, _Deep Learning_, §5.4 — Estimators, Bias and Variance: the U-shaped decomposition of error into bias and variance and the resulting capacity sweet spot.
[^gf-reg]: **Goodfellow**, _Deep Learning_, Ch. 7 — Regularization for Deep Learning: penalties and procedures that bias the learned function toward simpler solutions.
[^chollet-overfit]: **Chollet**, _Deep Learning with Python_, Ch. 5 — Fundamentals of ML: the practitioner's recipe of large models plus regularization rather than capacity-matching.
[^postdate]: The overparameterization phenomena here — fitting random labels, double descent, implicit bias toward max-margin and flat minima — postdate **Goodfellow** (2016), which still presents capacity control (§5.2) as the operative theory of generalization.