Learning Theory & GeneralizationOpen in Colab
ML project loop
Data·Hypothesis space·Objective·Optimization·Evaluation·Deployment feedback

Learning Theory & Generalization

Training error is easy to drive to zero — just memorize. The real question, the one all of machine learning rests on, is why does fitting the training data ever help on data you haven't seen? Learning theory answers it: it formalizes what we minimize, what generalization costs, and why bigger models don't always overfit the way classical intuition says they should.

Real-world examples: every decision about model size, regularization strength, and dataset size is a bet about generalization; the bias-variance trade-off underlies model selection; double descent reshaped how we think about overparameterized deep nets.

Empirical risk minimization

What we want to minimize is the true risk — expected loss over the real data distribution D\mathcal{D}, which we can never see:

R(f)=E(x,y)∼D[L(f(x),y)]R(f) = \mathbb{E}_{(\mathbf{x},y)\sim\mathcal{D}}\big[L(f(\mathbf{x}), y)\big]

What we can minimize is the empirical risk — average loss over our finite training sample:

R^(f)=1n∑i=1nL(f(xi),yi)\hat{R}(f) = \frac{1}{n}\sum_{i=1}^{n} L(f(\mathbf{x}_i), y_i)

Training a model is empirical risk minimization (ERM): pick the ff that minimizes R^\hat{R} and hope it also minimizes RR. Generalization theory is the study of when that hope is justified — i.e. how close R^(f)\hat{R}(f) stays to R(f)R(f).

The generalization gap

The quantity that matters is the generalization gap:

gap=R(f)−R^(f)(≈test error−training error)\text{gap} = R(f) - \hat{R}(f) \quad (\approx \text{test error} - \text{training error})

A small training error is worthless if the gap is large. Theory shows the gap tends to grow with model capacity (a more flexible model can fit the particular sample more tightly, including its noise) and shrink with more data (a bigger sample is harder to fit by coincidence). This is the formal backing for "more data helps" and "simpler models generalize better."

The bias–variance decomposition

For squared loss, expected test error splits into three pieces:

E[(y−f^(x))2]=Bias2⏟too simple+Variance⏟too sensitive+σ2⏟irreducible noise\mathbb{E}\big[(y - \hat{f}(\mathbf{x}))^2\big] = \underbrace{\text{Bias}^2}_{\text{too simple}} + \underbrace{\text{Variance}}_{\text{too sensitive}} + \underbrace{\sigma^2}_{\text{irreducible noise}}
  • Bias: error from wrong assumptions; a model too simple to capture the truth (underfitting).
  • Variance: error from sensitivity to the particular training sample; an over-flexible model that fits noise (overfitting).
  • Irreducible noise: the floor no model can beat.

One model, many training sets

x (input)y
— individual fits (24 resamples)— average fit- - true function
bias²0.006
variance0.133
bias² + variance0.138

Each thin rose curve is a k-NN regressor fit to a fresh resample of the same noisy sine data. Their spread is variance; the gap between their average (teal) and the truth (dashed) is bias. Small k: the cloud is wild but centered on the truth. Large k: the cloud collapses, but onto the wrong, over-smoothed curve.

Classically, capacity trades one for the other: increasing model complexity lowers bias but raises variance, giving the familiar U-shaped test-error curve with a sweet spot in the middle.

Regularization shifts the trade-off

L2/L1 penalties, dropout, and early stopping all reduce variance at the cost of a little bias — deliberately moving left on the complexity axis to land nearer the sweet spot. That's why a regularized complex model often beats an unregularized simpler one.

Capacity: VC dimension

How do we quantify "model capacity"? The classic measure is VC (Vapnik–Chervonenkis) dimension: the size of the largest set of points the model class can shatter (classify in all possible label arrangements). A linear classifier in 2D has VC dimension 3. It can shatter 3 points but not 4.

VC theory bounds the generalization gap roughly as:

R(f)≤R^(f)+O ⁣(dVCn)R(f) \le \hat{R}(f) + O\!\left(\sqrt{\frac{d_{\text{VC}}}{n}}\right)

More capacity (dVCd_{\text{VC}}) or less data (nn) loosens the bound. It's the formal statement of "complex models need more data."

Deep dive
VC Dimension
Includes runnable notebook

Double descent: the modern surprise

Classical theory predicts test error should rise once a model is complex enough to interpolate (memorize) the training set. Deep learning violated this. As you keep growing an already-interpolating model past the point where it hits zero training error, test error often falls again: the double descent curve.

The visualization below is not a sketch of that claim, it is the experiment. Random-ReLU-feature ridge regression on n=40n = 40 noisy points, sweeping the model width pp from 1 to 160 and measuring train and test error at every width.

Double descent, computed live

ridge λ
1101001000p = n = 40interpolation thresholdunder-parameterizedover-parameterizedbest a classical model can do: 1.184test MSE10⁻⁸10⁻⁴1train MSE — reaches zero at the threshold and stays there14080120160p — number of random features (model width)110100‖w‖ — size of the fitted weights
classical best (p < n)1.184 at p = 14
peak test error13.9 at p = 39
test at p = 1600.867
overparameterized vs classical best27% better
‖w‖ peaks atp = 39

Random-ReLU-feature ridge regression: n = 40 noisy training points, sweeping the model width p from 1 to 160. Below p = n the familiar U appears. At p ≈ n there is exactly one function that fits the training data, the model is forced to take it, and test error spikes. Past the threshold there are many interpolating functions and the minimum-norm solve can pick a smooth one, so test error falls again — here to 0.867, below the classical best of 1.184. The ‖w‖ panel is the mechanism: it peaks at exactly the p where test error does. Raise λ and the spike disappears, because it was a near-singular matrix all along.

Three things happen in order, and the third is the one classical theory does not have a slot for:

  1. The classical U, up to about p=14p = 14. Test error falls as the model gains enough capacity to represent the teacher, then starts to climb as it begins fitting the noise. This is the bias-variance trade-off exactly as the section above describes it.
  2. The spike at p≈np \approx n. Test error does not just climb, it explodes — around 12× the classical best. At p=np = n there is exactly one function in the class that fits all 40 training points, so the model has no choice but to take it, however violently it has to wiggle to pass through 40 noisy targets.
  3. The second descent. Past the threshold there are now infinitely many interpolating functions, and the fit is free to choose among them. Test error falls again, and keeps falling — ending up roughly a quarter below the classical sweet spot.

What actually drives it

The ‖w‖ panel is the mechanism rather than a decoration. The size of the fitted weights peaks at exactly the width where test error peaks, and decays as the model grows past it. That co-location is the whole explanation:

w^=arg⁡min⁡∥w∥subject toΦw=y\hat{\mathbf{w}} = \arg\min \|\mathbf{w}\| \quad \text{subject to} \quad \Phi\mathbf{w} = \mathbf{y}

Among the many interpolating solutions, least squares (and gradient descent from a zero initialization, which converges to the same place) picks the one of minimum norm. At p≈np \approx n that constraint set has a single element and the minimum is whatever it is. Widening the model enlarges the set of solutions to choose from, so the smallest-norm member gets smaller, and a low-norm function is a smooth one. Extra parameters do not buy more fitting, they buy more choice about how to fit.

Test the explanation instead of trusting it

If the spike really is a near-singular system rather than a deep truth about capacity, then a little explicit regularization should erase it. Click through the λ buttons: the peak drops from ~750 at λ ≈ 0 to 13.9 at 10−310^{-3} to 5.7 at 10−210^{-2}, and by λ = 0.1 there is no interior peak left at all — just the ordinary monotone curve. Double descent is a phenomenon of unregularized interpolation. A properly regularized model never rides the spike in the first place.

This is why massively overparameterized networks (which classical bias-variance would predict to overfit catastrophically) generalize fine. It doesn't repeal the bias-variance idea; it shows that raw parameter count is the wrong x-axis. What matters is the norm of the solution your optimizer actually lands on, and implicit regularization is what decides that.

Exercise

Training a model minimizes the empirical risk (average loss on the training set). What is the true quantity we actually care about, and why can't we minimize it directly?

Need a hint?

Expected loss over what?

Exercise

How does the generalization gap (test error − training error) typically change as you increase model capacity and as you add more training data?

Need a hint?

Capacity lets a model fit the sample tighter; data makes coincidental fits harder.

Exercise

Double descent describes what happens to test error as model capacity grows past the interpolation threshold (zero training error). What is observed?

Need a hint?

Classical theory says error rises after interpolation; reality is more surprising.

Exercise

Past the interpolation threshold, test error falls again as you keep adding parameters. What is the extra capacity actually buying, given that training error is already zero and cannot improve?

Need a hint?

Once many functions fit the data perfectly, something has to break the tie. What does least squares (and gradient descent from zero) pick?

Exercise

In the random-feature experiment, adding ridge regularization (λ = 0.1) makes the spike at the interpolation threshold disappear entirely, leaving an ordinary monotone curve. What does that tell you about double descent?

Need a hint?

What is numerically special about the design matrix exactly at p = n, and what does adding λ to the diagonal do to it?

Common mistakes

  1. Trusting training error. Low R^\hat{R} with a large generalization gap is overfitting; only held-out error estimates RR.
  2. Equating more parameters with more overfitting. Double descent shows overparameterized models can generalize — capacity isn't the whole story.
  3. Ignoring the data axis. The gap shrinks with nn; sometimes more data beats any modeling trick.
  4. Reading bias-variance off training loss. The decomposition is about expected test error over datasets, not a single training run.

Key takeaways

  • Training is empirical risk minimization — minimizing average training loss as a proxy for the unseen true risk; theory studies the generalization gap between them.
  • The gap grows with capacity and shrinks with data; the bias-variance decomposition splits test error into underfitting (bias), overfitting (variance), and irreducible noise.
  • VC dimension measures capacity and bounds the gap as ∼ ⁣dVC/n\sim\!\sqrt{d_{\text{VC}}/n} — formalizing "complex models need more data."
  • Double descent: past the interpolation threshold, test error can fall again, so overparameterized models generalize — implicit regularization, not raw capacity, decides.

Related concepts

Concept neighbourhood

How this concept connects — click any node to jump there, or explore the whole concept map.

Builds onRelatedGo deeper
Learning Theory & GeneralizationLinear & Logistic Regress…KNN & Decision TreesNeural NetworksThe Bias–Variance TradeoffValidation StrategiesRegularization: Ridge & L…Calibration & UncertaintyVC Dimension