Statistical Learning Theory — Why Does Learning Generalize?

You only ever see finitely many examples, yet the model answers questions about data it has never seen. This piece builds the guarantee from scratch — Hoeffding, uniform convergence, VC dimension, PAC — then shows where it broke against deep learning, and what survives in day-to-day evaluation design.

Understanding Deep Learning Requires Rethinking Generalization

Acing the past papers doesn't mean passing the exam

Suppose you drill ten years of past exam papers until you get every question right. Will you pass the real thing? It depends on how you got there. Learn the methods and you'll pass. Memorize which letter was circled and you have nothing left when a fresh question appears.

Machine learning has the same split. Keep a lookup table of every training example and answer "whatever I saw last time," and your training error is exactly zero — yet nobody would call that learning. What you actually want to know is what happens on data you haven't seen.

The puzzling part is that learning often does work. You see finitely many examples and somehow answer correctly across an infinite input space. Why is that leap allowed? The answer built up from the 1970s onward is a toolkit — uniform convergence, VC dimension, PAC learning — and around 2017 that toolkit broke, audibly, against deep networks. This article is the whole arc.

"Generalizing" means two numbers are close

Call the rule your learner picked a hypothesis $h$, and judge it with two numbers.

$D$ is the true distribution the world's data comes from, $\ell$ scores mistakes (for 0-1 loss: 1 if wrong, 0 if right), and $n$ is how many examples you hold. The left side of Eq. (1) is your exam score (true risk, a.k.a. generalization error); the right side is your past-paper score (empirical risk, a.k.a. training error). One averages over all the data in the world, the other over the $n$ examples on your disk. That's all the notation says. Read in words: "generalizing" means nothing more than these two averages landing in nearly the same place.

You want to push $R(h)$ down, but $D$ is unknown, so $R(h)$ is not computable. Only $\hat{R}(h)$ is. Which narrows the theory's job to exactly one thing:

$$R(h) \;\le\; \hat{R}(h) + (\text{something you can compute})$$

Producing that inequality. The "something" is called a complexity penalty. Statistical learning theory issues an insurance policy: your measured score plus a penalty upper-bounds your real score. Put in words: exam score ≤ past-paper score + a markup, and if that markup can be worked out from what's already on your disk, you get a ceiling on performance you were never able to measure. Before deriving the penalty, look at what it is trying to capture.

With a single hypothesis, this is just coin flipping

Start with the easy case: you fix one hypothesis before looking at the data. Then each per-example loss is an i.i.d. random variable, $\hat{R}(h)$ is their sample mean, and $R(h)$ is their expectation. Textbook law of large numbers. Hoeffding's inequality puts a rate on the convergence — when the loss lives in $[0,1]$:

In words: the chance your past-paper score and your exam score differ by more than $\epsilon$ collapses exponentially as examples $n$ pile up. Stated in words: gather enough examples and the score you measured can be trusted as the score you'd really get, with confidence that sharpens fast as the pile grows. The $\epsilon^2$ inside the exponent is the sting — halving the tolerance costs four times the data. Solve for $\epsilon$ and you get, with probability at least $1-\delta$, $R(h) \le \hat{R}(h) + \sqrt{\log(2/\delta)/(2n)}$, where $\delta$ is the chance the policy simply doesn't pay out. At $n=10{,}000$ and $\delta=0.05$ the penalty is about 1.4 points. That looks like a fine deal.

Choosing is what costs you

Except the story smuggled in a lie: "you fixed $h$ before looking at the data." Real learning does the opposite — it looks at the data, then picks whichever candidate minimizes $\hat{R}$. The selected $\hat{h}$ is a function of the data, so it is no longer a fixed hypothesis at all.

Coins make the problem obvious. Have 100 people each flip a coin ten times, then single out whoever got the most heads. That person got 9 heads — is their coin biased? No. The act of selecting the best performer is itself what harvests the lucky outliers. Same in learning: try enough hypotheses, keep the one with lowest training error, and its score flatters it by exactly as much luck as you shopped for.

The fix is to demand a guarantee that doesn't care how the winner was chosen — an inequality that holds simultaneously for every $h$ in the hypothesis class $\mathcal{H}$. That's uniform convergence. With finitely many candidates a union bound (the chance any one of them fails is at most the sum of the individual chances) settles it, and with probability at least $1-\delta$, for all $h \in \mathcal{H}$:

$|\mathcal{H}|$ is the number of candidates. Eq. (3) says: more candidates cost you more, but only logarithmically. Said in words, discount your winner's score by how many things you tried — and the discount is one you can buy back with more data. Multiply the candidate pool by a thousand and the numerator grows by $\log 1000 \approx 6.9$ — and the whole thing is divided by $\sqrt{n}$ anyway. The expressiveness-versus-data trade-off, in the barest possible algebra.