Generalization Theory

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}$,

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.

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

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.

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.

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.

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 $\mathrm{Pr}[R(h)-\hat{R}(h)>\epsilon ]\le e^{-2n{\epsilon }^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 $\mathrm{Pr}[\exists h:R(h)-\hat{R}(h)>\epsilon ]\le M{e}^{-2n{\epsilon }^2}$; setting the right side to $\delta$ and solving for $\epsilon$ 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⇝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:

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

The bias–variance decomposition

The U-shape has an exact algebraic source. Fix a query point $x$, let $y=g(x)+ϵ$ with noise $\mathbb{E}[ϵ]=0$, $\mathrm{Var}(ϵ)={\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:

The cross terms vanish: $ϵ$ 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.²

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.

Consider two extreme cases. A single constant function has ${\hat{\mathfrak{R}}}_S=0$: the sum $\frac{1}{n}\sum {\varsigma }_{i}h(x_i)=h\cdot \frac{1}{n}\sum {\varsigma }_i$ has expectation zero because the signs average out. A class that can hit any target on the sample has ${\hat{\mathfrak{R}}}_S=1$: it sets $h(x_i)={\varsigma }_i$ for every draw, so the correlation is $\frac{1}{n}\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.

For linear predictors with $\Vert w\Vert \le B$ over inputs with $\Vert x\Vert \le X$, one can show ${\hat{\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.³

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.

If the class can shatter the training set, then ${\hat{\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]$.

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}$.

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.

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.

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,

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.

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 }\Vert W_{\ell }\Vert /\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.

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

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

To see the tail argument in coordinates, write the gradient of the logistic loss, $\nabla \hat{R}(w)=-\frac{1}{n}{\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: 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.

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.

This is why the dominant practical recipe is to make models as large as compute allows and lean on regularization, explicit (weight decay, dropout) and implicit (SGD, early stopping), to steer the interpolating solution toward the well-behaved corner, rather than to shrink the model to fit a capacity budget.⁵ 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.

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

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 }\Vert W_{\ell }\Vert /\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

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, the use of the solution manifold's width to quantify uncertainty in Bayesian and ensemble methods, and the limit of infinite implicit depth in 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.