VC Dimension and PAC Learning

Intuition first

Everyone knows more data helps and simpler models generalise better. This lesson makes both statements quantitative: given a model family and a tolerance, how many examples do you actually need?

The key move is finding the right measure of model complexity. Parameter count will not do — a one-parameter model can be infinitely flexible, as we will see. What works is asking how many points the family can label in every possible way. A straight line in the plane can realise all $2^3 = 8$ labellings of three well-placed points, but not all 16 labellings of four. That number, three, is its VC dimension, and it turns out to be exactly what controls the sample size you need.

The resulting bounds are far too loose for practical use. Their value is structural: they tell you what the generalisation gap depends on, and what it does not.

Shattering and VC dimension

A hypothesis class $\mathcal{H}$ shatters a set of $m$ points if, for every one of the $2^m$ possible label assignments, some $h \in \mathcal{H}$ realises it.

$$\text{VC}(\mathcal{H}) = \text{the largest } m \text{ such that some set of } m \text{ points is shattered}$$

Note "some set", not "every set" — one shatterable configuration suffices.

Standard values:

The PAC framework

Probably Approximately Correct: we cannot demand a perfect model with certainty, so we demand a nearly-correct one with high probability.

A class is PAC-learnable if there is an algorithm that, for any $\epsilon, \delta > 0$ and enough samples, returns $h$ with

$$\Prob\Big(R(h) \leq R(h^*) + \epsilon\Big) \geq 1 - \delta$$

Two knobs: $\epsilon$ is how much error you tolerate, $\delta$ is how often you accept failure.

The generalisation bound

With probability at least $1 - \delta$, simultaneously for all $h \in \mathcal{H}$:

$$R(h) \;\leq\; \hat{R}(h) \;+\; \sqrt{\frac{\text{VC}(\mathcal{H})\big(\ln\frac{2n}{\text{VC}(\mathcal{H})} + 1\big) + \ln\frac{4}{\delta}}{n}}$$

Ignoring logarithms, the gap scales as

$$R(h) - \hat{R}(h) \;=\; O\!\left(\sqrt{\frac{\text{VC}(\mathcal{H})}{n}}\right)$$

Sample complexity

Inverting the bound gives the number of examples needed:

$$n \;=\; O\!\left(\frac{\text{VC}(\mathcal{H}) + \ln\frac{1}{\delta}}{\epsilon^2}\right)$$

Solved problem 1 · How much data does a linear classifier need?

You want a linear classifier in $\mathbb{R}^{20}$ with generalisation gap at most $\epsilon = 0.05$ and confidence $1 - \delta = 0.95$. Estimate the sample complexity, then compare with $\epsilon = 0.01$.

Step 1 — VC dimension

Linear separators in $\mathbb{R}^d$ have

$$\text{VC} = d + 1 = 20 + 1 = 21$$

Step 2 — apply the sample complexity form

Using the standard constant-free version $n \approx \dfrac{\text{VC} + \ln(1/\delta)}{\epsilon^2}$:

$$\ln\frac{1}{\delta} = \ln\frac{1}{0.05} = \ln 20 \approx 3.00$$$$n \approx \frac{21 + 3.00}{0.05^2} = \frac{24.0}{0.0025} = 9{,}600$$

Step 3 — tighten the tolerance to 0.01

$$n \approx \frac{21 + 3.00}{0.01^2} = \frac{24.0}{0.0001} = 240{,}000$$

Step 4 — note the two scalings separately

Reducing $\epsilon$ from $0.05$ to $0.01$ — a factor of 5 — multiplied the requirement by $5^2 = 25$. The $\epsilon^{-2}$ dependence is brutal, and it is why the last few points of accuracy are so much more expensive than the first.

Now vary the confidence instead. Tightening $\delta$ from $0.05$ to $0.001$:

$$\ln\frac{1}{0.001} = \ln 1000 \approx 6.91$$$$n \approx \frac{21 + 6.91}{0.0025} = \frac{27.9}{0.0025} \approx 11{,}160$$

A 50-fold reduction in failure probability costs only 16% more data, because $\delta$ enters logarithmically. High confidence is cheap; high accuracy is expensive.

Step 5 — reality check

In practice a 20-feature logistic regression performs well with a few thousand examples, not 9,600 — and far better than the bound's worst case. The bound is distribution-free: it must hold for the most adversarial data distribution imaginable, so it is loose by a wide margin on real data.

Answer

About 9,600 examples for $\epsilon = 0.05$ and about 240,000 for $\epsilon = 0.01$. The $\epsilon^{-2}$ scaling dominates everything; the $\ln(1/\delta)$ term is nearly free. Treat these as upper bounds on the worst case, not as forecasts.

Why the bounds are loose, and what replaced them

VC bounds are distribution-free — they hold for any data distribution, including maliciously constructed ones. That generality is exactly what makes them loose on benign real data.

They also fail spectaculary on modern networks. A network with $10^{11}$ parameters has an astronomically large VC dimension, so the bound is vacuous — it permits a generalisation gap above 1. Yet such models generalise. Worse, deep networks can perfectly fit randomly labelled data, which means their capacity genuinely is enormous, and yet they still generalise on real labels.

Refinements that do better:

• Margin bounds — depend on $1/\text{margin}^2$ rather than dimension, which is why SVMs work in very high dimensions.
• Rademacher complexity — data-dependent, measuring how well the class fits random noise on your sample rather than in the worst case.
• PAC-Bayes — bounds in terms of the distance between a learned posterior over hypotheses and a prior; currently the most successful route for deep networks.
• Algorithmic stability — bounds based on how much the output changes when one training point is swapped. Applies to SGD directly.

What to actually take away

The bounds are not calculators. They are a correct account of what the generalisation gap depends on:

1. Quadruple the data to halve the gap. This sets realistic expectations for data-collection projects.
2. Confidence is cheap, accuracy is not. $\ln(1/\delta)$ versus $1/\epsilon^2$.
3. What matters is complexity relative to sample size, not complexity alone.
4. Regularisation works by reducing effective complexity — a claim the theory makes precise.

Exercise 1

Show that the VC dimension of axis-aligned rectangles in $\mathbb{R}^2$ is exactly 4.

Show solutionHide solution

Two parts: exhibit 4 shattered points, and show 5 can never be.

At least 4. Place four points in a diamond: top $(0,1)$, bottom $(0,-1)$, left $(-1,0)$, right $(1,0)$. For any subset $S$ of these four, take the smallest axis-aligned rectangle containing exactly the points of $S$. Because each point is the unique extreme point in one of the four directions, the bounding box of $S$ contains no point outside $S$ — removing the topmost point, for instance, lowers the top edge below it. All $2^4 = 16$ subsets are realisable, so these four are shattered.

Not 5. Take any five points. Identify the point with the largest $y$, smallest $y$, largest $x$, and smallest $x$ — at most four points are selected this way, so at least one point $p$ is not extreme in any direction. Then $p$ lies inside the bounding box of the other four.

Consider the labelling that marks the other four positive and $p$ negative. Any rectangle containing all four positives must contain their bounding box, which contains $p$ — so $p$ is included and labelled positive. That labelling is unachievable, so no set of 5 points is shattered.

Hence $\text{VC} = 4$.

Sanity check against the general pattern: an axis-aligned rectangle in $\mathbb{R}^d$ is specified by $2d$ numbers and has VC dimension $2d$, giving 4 for $d = 2$. ✓

Exercise 2

A model class has VC dimension 500. You have 1,000 training examples and zero training error. Should you trust the model?

Show solutionHide solution

No. The ratio $\text{VC}/n = 500/1000 = 0.5$ is far too high.

Plugging into the asymptotic form, the generalisation gap is on the order of

$$\sqrt{\frac{500}{1000}} = \sqrt{0.5} \approx 0.71$$

A bound permitting a gap of 0.71 is vacuous for a classifier whose error is between 0 and 1 — it tells you the true error could be anywhere.

The intuition behind the formalism: a class with VC dimension 500 can shatter 500 points, meaning it can produce any labelling of 500 points. With only 1,000 examples, achieving zero training error is weak evidence of learning, because the class is flexible enough to fit a large fraction of arbitrary label patterns. Zero training error is close to guaranteed whether or not signal exists.

What to do:

1. Hold out a test set and measure. The theory is loose; the empirical gap is what matters.
2. Reduce effective complexity — regularise, constrain, or use a simpler class. Aim for $\text{VC} \ll n$.
3. Run the randomisation check. Shuffle the labels and refit. If training error is still near zero, the model is memorising, and the zero error on real labels means nothing.
4. Get more data. For a meaningful bound you would want $n$ in the tens of thousands at $\text{VC} = 500$.

---

That completes Machine Learning Foundations. Next module: Supervised Learning, where these principles are applied to specific algorithms, starting with Simple Linear Regression.