The VC Generalization Bound

A model that fits its training data perfectly could be genuinely brilliant, or could be a flexible enough class to memorize any labeling of that many points, noise included, telling you nothing about its performance on new data. Distinguishing these two situations from the training accuracy number alone is impossible — you need to know how flexible the model class could have been, independent of the specific labels it happened to see. The VC dimension (Shattering and the Growth Function) is that flexibility measured as one number, and the VC generalization bound is the inequality that turns it directly into a worst-case guarantee on the gap between training and true error.

The analogy: a tailor with how many free measurements

A tailor who is only allowed to take 2 measurements (say, chest and waist) can fit a suit reasonably well to a body, but not perfectly — there just isn't enough freedom to match every idiosyncrasy. A tailor allowed 50 measurements can fit almost any body shape essentially perfectly, including quirks that are really just that one day's posture, not the body's real shape. The 50-measurement tailor's "perfect fit" tells you far less about their skill, because the flexibility itself could produce a perfect fit regardless of skill. VC dimension is the model-class equivalent of "how many free measurements does this tailor get" — and the bound quantifies exactly how much less trustworthy a perfect fit becomes as that number grows.

The formal bound

For a hypothesis class with VC dimension $d$, with high probability $1-\delta$ over a training set of size $n$, every hypothesis $h$ in the class simultaneously satisfies:

$$R(h) \le \hat{R}(h) + \sqrt{\frac{d\left(\ln\frac{2n}{d} + 1\right) + \ln\frac{4}{\delta}}{n}}$$

In words: the true error $R(h)$ (on all future data) is at most the training error $\hat{R}(h)$ plus a penalty term that grows with the class's flexibility $d$ and shrinks as the sample size $n$ grows — the penalty is the price of a flexible class's training accuracy being an optimistic estimate of its true accuracy, and that price only goes to zero as data accumulates far faster than complexity does.

Worked example 1: the gap shrinks as data grows

For $d = 10$, $\delta = 0.05$ (95% confidence), and $n = 1{,}000$: the penalty term is roughly $\sqrt{\frac{10(\ln 200 + 1) + \ln 80}{1000}} = \sqrt{\frac{10(6.29) + 4.38}{1000}} = \sqrt{\frac{67.3}{1000}} \approx 0.26$ — a training error of, say, 5% could correspond to a true error as high as roughly 31%. Bump $n$ to $100{,}000$ with the same $d=10$: the penalty term shrinks to $\sqrt{\frac{10(\ln 20{,}000+1)+4.38}{100{,}000}} = \sqrt{\frac{10(10.9)+4.38}{100{,}000}} \approx \sqrt{0.00114} \approx 0.034$ — the same 5% training error now bounds true error at roughly 8.4%. A hundred-fold increase in data shrank the worst-case gap by roughly a factor of 8.

Worked example 2: two model classes, same training error, different bound

Model A (linear, $d=5$) and Model B (a deep decision tree, $d=500$) both achieve 3% training error on $n=5{,}000$ examples, $\delta=0.05$. Model A's penalty: $\sqrt{\frac{5(\ln 2000+1)+3.69}{5000}} \approx \sqrt{\frac{5(8.6)+3.69}{5000}} \approx \sqrt{0.00961} \approx 0.098$, so true error $\le$ roughly 12.8%. Model B's penalty: $\sqrt{\frac{500(\ln 20+1)+3.69}{5000}} \approx \sqrt{\frac{500(3.996)+3.69}{5000}} \approx \sqrt{0.400} \approx 0.632$, a bound so loose (true error $\le$ 66%) it's nearly worthless. Identical training error, wildly different trustworthiness — exactly the gap the tailor analogy predicts.

Drag model complexity above and watch the train/test gap widen — that widening gap is the VC bound's penalty term made visible, growing with $d$ exactly as the formula predicts.

What this means in practice

The bound is rarely computed exactly in day-to-day model building — VC dimensions for deep networks are hard to pin down and the bounds are famously loose — but the qualitative lesson transfers directly: a very flexible model (deep tree, wide neural net, high-degree polynomial features) achieving near-zero training error on a modest dataset is a red flag demanding out-of-sample validation, not a training-error number to celebrate on its own.