PAC Learning & VC Dimension · Machine Learning

01 · Motivation

Why does this matter?

In Chapters 2–4 you trained models and used cross-validation to estimate their generalisation error. That works in practice, but it leaves a deep question untouched: can we prove, before we even look at a test set, that a learner will generalise? And if so, how much data is enough to make that proof trustworthy?

Three concrete pains that PAC theory addresses.

It overfits — but why?

You saw in Ch. 4 that a model with low training error can still fail on new data. PAC theory turns this from a mystery into an inequality: training error is a biased estimator of true error, and the bias is controlled by how rich your hypothesis space is relative to how many examples you saw.

How many samples do I need?

Before collecting (or labelling) data, a working engineer wants a budget: “to be $95\%$ sure my classifier has error under $5\%$ , how many labelled examples do I need?” PAC gives a closed-form answer — and it is surprisingly modest for finite hypothesis spaces.

Which model class is even learnable?

Not every concept can be learned from a polynomial number of examples. PAC-learnability is a precise yes/no notion that separates the tractable from the impossible — and it is the gateway to the deeper question of capacity measured by VC dimension.

why

The whole chapter in one sentence

If your hypothesis space is not too rich relative to the amount of data you have, then any hypothesis that fits the training set will, with high probability, generalise. Everything below — version spaces, Haussler’s bound, VC dimension, SRM — is the precise statement of “not too rich” and “high probability”.

PAC sits at a different level from Chapters 2–3, which were about algorithms. This chapter is about guarantees. The tools we build here (capacity, sample complexity, generalisation bounds) are what justify the regularisation in Ch. 2/4, the max-margin principle in Ch. 7, and the kernel trick in Ch. 6. You can do ML without it. You can’t understand why ML works without it.

02 · Intuition

The idea in plain language

Picture the space of all hypotheses your learner could possibly output as a city. Among them, somewhere, is the true concept $c$ — the function nature uses to label data. Around $c$ is a small neighbourhood of “good” hypotheses with error below your tolerance $\varepsilon$ . The rest of the city is “ $\varepsilon$ -bad”: hypotheses whose error is at least $\varepsilon$ .

When you train, you observe $N$ labelled examples drawn independently from some unknown distribution $P$ . The version space $VS_{H,D}$ is the set of hypotheses in $H$ that label every training example correctly. The learner picks one of them. But the version space is not the same as the set of good hypotheses: it may contain hypotheses that happen to fit the training data while being secretly bad off-training.

The whole game is: how likely is it that the version space is “poisoned” by an $\varepsilon$ -bad hypothesis? If we can make that probability tiny, then any hypothesis we pick from $VS_{H,D}$ is, with high confidence, good.

key

The two knobs of PAC

A PAC guarantee has two parameters and they mean different things:

$\varepsilon$ (accuracy) — the largest error we tolerate. “Approximately correct.”
$\delta$ (confidence) — the probability we’re allowed to fail outright. “Probably.”

We never get a deterministic promise. We get: with probability at least $1-\delta$ over the random training set, the learner outputs a hypothesis whose true error is at most $\varepsilon$ . Both knobs cost data — but only logarithmically in $1/\delta$ and linearly in $1/\varepsilon$ , which is why PAC works at all.

Why bad hypotheses can survive training

Here is the heart of the argument, stripped to one image. Suppose a specific hypothesis $h$ has true error $\varepsilon$ — it disagrees with the target on a fraction $\varepsilon$ of inputs. What is the probability that $N$ random inputs all happen to fall in the agreement region? It’s $(1-\varepsilon)^N$ . For $\varepsilon = 0.1$ and $N = 30$ , that’s about $4\%$ — small, but not negligible. With $|H| = 1{,}000$ such bad hypotheses, the expected number that “fool” the training set is $40$ , and the version space is full of impostors.

The fix is to make $N$ large enough that $|H|(1-\varepsilon)^N$ becomes tiny. Solving for $N$ gives the famous PAC sample-complexity formula. The next section makes this rigorous.

”Linear” but in capacity

The same bias–variance dial that haunted us in Ch. 4 reappears here, written in the language of $|H|$ .

Big H → low bias, high variance

A rich hypothesis space probably contains a hypothesis close to the target — bias is small. But many hypotheses can also accidentally fit the training data — the version space is large, full of $\varepsilon$ -bad impostors. High capacity demands more data.

Small H → high bias, low variance

A small hypothesis space might not even contain the target — bias may be irreducible. But there are few candidates that could accidentally fit the data, so the bound is tight. Less capacity, less data.

PAC turns “rich enough but not too rich” from a vibe into a number.

03 · Formalism

Definitions and equations

Time to nail down the symbols. Everything in this chapter rests on this small notation set — invest the minute to memorise it.

The PAC setup

X: the instance space — all possible inputs (e.g. all binary feature vectors of length $n$ ).
P: an unknown, fixed distribution over $X$ from which inputs are drawn. The learner never sees $P$ , only samples.
C: the concept class — the family of true Boolean functions $c : X \to \{0,1\}$ we might face.
c ∈ C: the actual target concept the data was labelled with.
H: the hypothesis space — the family of functions the learner is allowed to consider. Often $H \supseteq C$ , but not always.
D: the training set: $N$ i.i.d. pairs $\langle x_i, c(x_i) \rangle$ with $x_i \sim P$ .
L_true(h): the true error $\Pr_{x\sim P}[h(x)\neq c(x)]$ . What we actually care about.
L_train(h): the training error — the fraction of $D$ on which $h$ disagrees with $c$ .
ε: accuracy tolerance, $0 \leq \varepsilon \leq 1$ . We want $L_\text{true}(h) \leq \varepsilon$ .
δ: confidence parameter, $0 \leq \delta \leq 1$ . We allow ourselves to fail with probability $\leq \delta$ .

The version space

Version space

VS_{H,D} \;=\; \{\, h \in H : L_\text{train}(h) = 0 \,\}.

The set of hypotheses that classify every training example correctly. In the realisable setting (where some $h^\star \in H$ achieves zero true error), $VS_{H,D}$ is never empty — $c$ itself is always inside.

A version space is $\varepsilon$ -exhausted if every hypothesis still alive in it has true error below $\varepsilon$ . That’s the property we want: if $VS_{H,D}$ is $\varepsilon$ -exhausted, any consistent hypothesis is automatically good.

Haussler’s theorem (finite H, realisable case)

thm

Haussler 1988

Let $H$ be finite and $D$ a sequence of $N \geq 1$ i.i.d. examples of some target concept $c$ . For any $0 \leq \varepsilon \leq 1$ ,

\Pr\bigl(\,\exists h \in H : L_\text{train}(h)=0 \wedge L_\text{true}(h) \geq \varepsilon\,\bigr) \;\leq\; |H|\,e^{-\varepsilon N}.

In words: the probability that some $\varepsilon$ -bad hypothesis survives $N$ examples shrinks exponentially in $N$ and grows only linearly in $|H|$ .

Proof in three lines (an exam favourite)

Proof Deriving Haussler's bound

1 · One bad hypothesis

Fix a specific $\varepsilon$ -bad hypothesis $h$ (i.e. $L_\text{true}(h) \geq \varepsilon$ ). The probability it agrees with one random example is at most $1-\varepsilon$ . For $N$ i.i.d. examples it agrees on all of them with probability at most

\Pr(L_\text{train}(h)=0 \mid L_\text{true}(h)\geq \varepsilon) \;\leq\; (1-\varepsilon)^N.

Why $\leq$ and not $=$ ? Because $L_\text{true}(h)$ may exceed $\varepsilon$ , making agreement even less likely.

2 · Union bound over H

There are at most $|H|$ bad hypotheses to worry about. By the union bound,

\Pr\bigl(\exists h : L_\text{train}=0 \wedge L_\text{true}\geq \varepsilon\bigr) \;\leq\; |H|\,(1-\varepsilon)^N.

3 · The exponential inequality

Use the standard inequality $1-\varepsilon \leq e^{-\varepsilon}$ (valid for all $\varepsilon \in \mathbb{R}$ ):

|H|\,(1-\varepsilon)^N \;\leq\; |H|\,e^{-\varepsilon N}.

That’s the bound. Three lines, two ideas, one inequality. $\square$

From bound to sample size

Set the right-hand side to $\delta$ and solve for $N$ .

PAC sample complexity (realisable)

N \;\geq\; \frac{1}{\varepsilon}\Bigl(\,\ln |H| \;+\; \ln \tfrac{1}{\delta}\,\Bigr).

Read this carefully. The cost of better accuracy is $1/\varepsilon$ (linear). The cost of more confidence is $\ln(1/\delta)$ (logarithmic — confidence is cheap!). The cost of a richer hypothesis space is $\ln|H|$ — also logarithmic, so doubling $|H|$ costs just one more example per accuracy unit.

The same inequality solved for $\varepsilon$ given $N$ and $\delta$ gives the generalisation bound form:

\varepsilon \;\geq\; \frac{1}{N}\Bigl(\,\ln|H| + \ln\tfrac{1}{\delta}\,\Bigr).

A concrete count: conjunctions of literals

Consider $M$ Boolean attributes and let $H$ be the set of conjunctions where each literal is either present positively, present negatively, or absent. That’s $3$ choices per attribute, so

|H| \;=\; 3^M \quad\Longrightarrow\quad N \;\geq\; \frac{1}{\varepsilon}\bigl(M\ln 3 + \ln\tfrac{1}{\delta}\bigr).

Linear in the number of attributes. Even with $M = 100$ features, $\varepsilon = 0.05$ , $\delta = 0.05$ , we need only $\lceil(100\ln 3 + \ln 20)/0.05\rceil \approx 2{,}260$ labelled examples. That is why ML works.

!

Why we cannot let H be 'all Boolean functions'

A function from $\{0,1\}^M$ to $\{0,1\}$ is specified by its truth table on $2^M$ inputs. There are $2^{2^M}$ such functions, so

\ln |H_\text{all Boolean}| \;=\; 2^M \ln 2 \quad\Longrightarrow\quad N \;\geq\; \frac{2^M \ln 2 + \ln(1/\delta)}{\varepsilon}.

Sample complexity becomes exponential in the number of features. For $M = 30$ features that’s a billion examples to learn a generic Boolean function with PAC guarantees. This is the precise reason ML must commit to an inductive bias — a restricted hypothesis class — before seeing the data. Without it, learning is doomed.

PAC-learnability, formally

def

PAC-learnable concept class

A concept class $C$ is PAC-learnable by learner $L$ using hypothesis space $H$ if there exists an algorithm such that for every $c \in C$ , every distribution $P$ over $X$ , every $0 < \varepsilon < 1/2$ , and every $0 < \delta < 1/2$ , $L$ with probability at least $1-\delta$ outputs a hypothesis $h \in H$ with $L_\text{true}(h) \leq \varepsilon$ , using a number of samples polynomial in $1/\varepsilon$ and $1/\delta$ .

It is efficiently PAC-learnable if, additionally, the learner’s running time is polynomial in $1/\varepsilon$ , $1/\delta$ , the input size $M$ , and $\mathrm{size}(c)$ .

When the version space is empty: agnostic PAC

In real life, no hypothesis in $H$ is perfect — there is always irreducible label noise, model misspecification, or both. The version space collapses to $\varnothing$ . We no longer ask for $L_\text{train}=0$ ; we ask: given that we picked the hypothesis with smallest $L_\text{train}$ , how far can $L_\text{true}$ be from $L_\text{train}$ ?

The tool is Hoeffding’s inequality, a concentration result that says: the empirical mean of bounded i.i.d. random variables is, with high probability, close to the true mean. For us, “empirical mean” is training error and “true mean” is true error — exactly what we need.

thm

Hoeffding's inequality (one- and two-sided)

Let $X_1, \dots, X_N$ be i.i.d. random variables with $X_i \in [0,1]$ , and let $\bar X = \tfrac{1}{N}\sum_i X_i$ . Then for any $\varepsilon > 0$ ,

\Pr\bigl(\,\mathbb{E}[X] - \bar X > \varepsilon\,\bigr) \;\leq\; e^{-2N\varepsilon^2}, \qquad \Pr\bigl(\,|\mathbb{E}[X] - \bar X| > \varepsilon\,\bigr) \;\leq\; 2e^{-2N\varepsilon^2}.

The two-sided form (right) is what we use when we don’t know which way the gap will fall. Either way, the bound is exponential in $N\varepsilon^2$ — the price of getting “twice as close” is “four times the data”.

How does this apply to a classifier $h$ ? Set $X_i = \mathbf{1}[h(x_i) \neq c(x_i)] \in \{0, 1\}$ — the indicator that $h$ makes a mistake on the $i$ -th training example. Then $\bar X = L_\text{train}(h)$ and $\mathbb{E}[X] = L_\text{true}(h)$ . Hoeffding tells us that for any single $h$ , the training error is a tight estimate of the true error. Apply it to each $h \in H$ and union-bound over $H$ :

Agnostic PAC bound

\Pr\bigl(\exists h \in H : L_\text{true}(h) - L_\text{train}(h) > \varepsilon\bigr) \;\leq\; |H|\,e^{-2N\varepsilon^2}.

Note the square on $\varepsilon$ — agnostic learning needs more data than the realisable case for the same accuracy, because we now have to estimate every $L_\text{true}(h)$ from $L_\text{train}(h)$ instead of just ruling out impostors.

Setting the right side to $\delta$ and solving gives the generalisation form that the exam expects you to know by heart.

Agnostic generalisation bound

L_\text{true}(h) \;\leq\; \underbrace{L_\text{train}(h)}_{\text{bias}} \;+\; \underbrace{\sqrt{\,\frac{\ln|H| + \ln(1/\delta)}{2N}\,}}_{\text{variance}}.

The bias–variance trade-off Ch. 4 promised, now written as a bound. Big $H$ — small training error (good bias term) but large square-root term (large variance). Small $H$ — flipped. The trade-off lives inside the inequality.

What if H is infinite?

Everything above used $|H|$ as the capacity measure. For continuous hypothesis spaces — lines in $\mathbb{R}^2$ , all polynomials of bounded degree, neural networks — $|H|=\infty$ , and $\ln|H|$ is undefined. The bound becomes vacuous.

But this cannot be the right answer. We routinely learn with linear classifiers from finite data and they generalise. The issue is that $|H|$ is the wrong measure: most of the “different” hypotheses in a continuous family agree on almost every point. What matters is not how many hypotheses there are but how many distinct labellings of finite samples the family can produce. That number is what the VC dimension captures — §05 of this chapter. Hold that thought.

04 · Worked example

How many labelled examples does my spam filter need?

Let’s make every symbol concrete with a problem you might actually face. You’re building a spam classifier whose hypothesis space is conjunctions of literals over $M = 20$ boolean features (e.g. “the word discount appears AND the sender is unknown AND the subject is in ALL CAPS”). You want to be $99\%$ sure the true error is below $5\%$ . How many labelled emails do you need to collect?

Step 1 · Translate the requirements into PAC parameters

Requirement	Symbol	Value
True error tolerance	$\varepsilon$	0.05
Failure probability	$\delta$	0.01
Number of features	$M$	20
Hypothesis count	$\lvert H\rvert = 3^M$	$3^{20} \approx 3.49\times 10^{9}$

Three choices per feature: positive, negative, or absent (= the literal “doesn’t matter”). With twenty features, three and a half billion possible conjunctions.

Step 2 · Plug into the realisable sample-complexity formula

Worked example Computing the realisable bound

2a · The formula and its assumption

Recall:

N \;\geq\; \frac{1}{\varepsilon}\Bigl(\ln |H| + \ln \tfrac{1}{\delta}\Bigr).

We use this only if we believe there exists $h^\star \in H$ with $L_\text{train}(h^\star)=0$ . For a spam filter with twenty hand-engineered binary features, this is plausible on a clean training set.

2b · Compute the log term

\ln |H| \;=\; \ln 3^{20} \;=\; 20\ln 3 \;\approx\; 20 \cdot 1.0986 \;\approx\; 21.97.

And $\ln(1/\delta) = \ln 100 \approx 4.61$ .

2c · Add and divide by ε

N \;\geq\; \frac{1}{0.05}\,(21.97 + 4.61) \;=\; \frac{26.58}{0.05} \;\approx\; 532.

$N \geq 532$ labelled emails. Surprisingly few.

Step 3 · Feel the scaling

Pause to appreciate how cheap the parameters are.

Change	New $N$	Cost factor
Baseline ( $\varepsilon=.05,\,\delta=.01,\,M=20$ )	532	1×
Want $\varepsilon=.01$ (5× more accurate)	2 658	5× (linear in $1/\varepsilon$ )
Want $\delta=10^{-6}$ (10 000× more confident)	716	1.35× (log!)
Double the features ( $M=40$ )	971	1.83× (linear in $M$ )
Switch to arbitrary Boolean functions ( $\lvert H\rvert = 2^{2^M}$ )	$\approx 2.1\times 10^7$	40 000× (exponential)

The last row is the punchline. Allowing any Boolean function as a hypothesis pushes the sample budget into the tens of millions — humans cannot label that many emails. The inductive bias of “conjunction of literals” is what makes the problem learnable. This is PAC’s quantitative answer to “why do we need priors / regularisation / a restricted hypothesis class?”.

Step 4 · What if the data is noisy?

Suppose your training set is not perfectly clean — maybe $8\%$ of labels are wrong, so no conjunction will have zero training error. Switch to the agnostic bound. We want $L_\text{true}(\hat h) \leq L_\text{train}(\hat h) + \varepsilon$ with $\varepsilon = 0.05$ and $\delta = 0.01$ :

N \;\geq\; \frac{1}{2\varepsilon^2}\Bigl(\ln |H| + \ln \tfrac{1}{\delta}\Bigr) \;=\; \frac{21.97 + 4.61}{2 \cdot 0.0025} \;\approx\; 5{,}316.

Ten times the realisable case — because $\varepsilon$ appears squared. The price of noise-robustness is paid in data.

map

What just happened, in three bullets

The hypothesis space is huge ( $3.5\times 10^9$ conjunctions) yet only $\ln|H| \approx 22$ matters — that’s the magic of logarithm.
Confidence is cheap, accuracy is expensive. 10 000× lower $\delta$ needs 35% more data; 5× lower $\varepsilon$ needs 5× more data.
Bias matters. Restricting to conjunctions cuts sample complexity by four orders of magnitude vs unrestricted Boolean functions. Without an inductive bias, learning is impossible from realistic samples.

05 · Visual explanation

Seeing it geometrically

Three pictures that capture the geometry of PAC and VC. Make space for them in your head — they generalise immediately to every later chapter that talks about capacity.

A · Learning axis-aligned rectangles

The cleanest concrete PAC example. The target concept is an axis-aligned rectangle in the plane; points inside it are positive, outside are negative. Our learner outputs the tightest rectangle around the positive training examples — a sensible, consistent strategy.

The error region (orange stripes) is the part of the true rectangle $R$ that the learner’s tighter $R'$ misses: positive points there would be wrongly classified as negative. Decompose this ring into four strips — top, bottom, left, right. If we guarantee each strip has probability mass at most $\varepsilon/4$ , the total error is at most $\varepsilon$ .

For any strip individually: the probability that no training point lands in it is $(1-\varepsilon/4)^N$ . Apply the union bound over four strips and the standard $1-x \leq e^{-x}$ inequality.

Derivation The rectangle bound, even with infinite H

1 · Over-allocate the budget

The error region $R \setminus R'$ is the union of (at most) four rectangular strips — top, bottom, left, right. We over-allocate budget: ask each strip to carry probability mass at most $\varepsilon/4$ . If all four succeed, the total error is at most $\varepsilon$ .

2 · The bad event for one strip

A bad event for one strip: its probability mass is $\geq \varepsilon/4$ yet no training point landed in it (otherwise $R'$ would have stretched to include that point). The probability of “no points in a region of mass $\varepsilon/4$ ” is $(1 - \varepsilon/4)^N$ .

3 · Union-bound the four strips

Union-bound over the four strips: $\Pr(\text{any strip bad}) \leq 4(1 - \varepsilon/4)^N$ . Force this to be $\leq \delta$ and use $1-x \leq e^{-x}$ :

4\,e^{-\varepsilon N / 4} \;\leq\; \delta \;\Longleftrightarrow\; N \;\geq\; \frac{4}{\varepsilon}\ln\frac{4}{\delta}.

Notice: the bound depends on $\varepsilon$ and $\delta$ but not on $|H|$ — which is infinite here. Geometry replaced finite enumeration. That’s the seed of the VC argument.

B · Shattering — what capacity really means

Forget “how many hypotheses are there?” and ask instead: “on a given set of points, how many different label patterns can my hypothesis class realise?” A class shatters a set of $d$ points if it can realise all $2^d$ possible $\pm$ -labellings of those points.

For 3 collinear points with a 1-D threshold classifier, only 4 of the 8 labellings are realisable (the four monotone ones). 1-D thresholds cannot shatter 3 points. But linear classifiers in 2-D can shatter 3 (non-collinear) points — all eight labellings, shown below; the XOR pattern on 4 points is the configuration no line can split:

− − −

− − +

− + −

− + +

+ − −

+ − +

+ + −

+ + +

XOR — no line works

The “XOR” pattern on the corners of a square is not linearly separable. Hence 2-D linear classifiers cannot shatter this set of 4 points — and indeed they cannot shatter any set of 4 points. The VC dimension of 2-D linear classifiers is therefore 3.

def

VC dimension in plain English

The VC dimension $VC(H)$ is the size of the largest set of points that $H$ can shatter. Showing $VC(H) \geq d$ means exhibiting some arrangement of $d$ points that $H$ shatters. Showing $VC(H) < d+1$ means proving that every arrangement of $d+1$ points has at least one labelling $H$ cannot produce. Asymmetric, on purpose.

C · The VC generalisation bound

With VC dimension as the right capacity measure, the agnostic bound generalises to infinite hypothesis classes.

VC bound

L_\text{true}(h) \;\leq\; \underbrace{L_\text{train}(h)}_{\text{empirical risk}} \;+\; \underbrace{\sqrt{\,\frac{VC(H)\bigl(\ln\frac{2N}{VC(H)} + 1\bigr) + \ln\frac{4}{\delta}}{N}\,}}_{\text{capacity penalty}}.

Replace $\ln|H|$ with a term that grows linearly in $VC(H)$ (with a log factor). The shape of the bound — empirical risk plus a capacity-dependent penalty — is exactly the bias–variance picture, and it is the principle behind structural risk minimisation: choose $H$ (out of a ladder of nested spaces) so the right-hand side is smallest.

As VC dimension grows, training error decreases (the model can fit more) but the penalty grows. The sweet spot — minimum of the sum — is the classifier you should pick. That is SRM, and you can feel it move in Hands-on 3’s companion intuition below.

D · From VC bound to sample complexity

Solving the VC bound for $N$ (the analogue of what we did with Haussler in §03) gives the VC sample-complexity formula — the number of examples sufficient to guarantee error at most $\varepsilon$ with probability at least $1-\delta$ , for an infinite hypothesis class of VC dimension $VC(H)$ :

VC sample complexity

N \;\geq\; \frac{1}{\varepsilon}\Bigl(\,4\log_2\tfrac{2}{\delta} \;+\; 8\,VC(H)\,\log_2\tfrac{13}{\varepsilon}\,\Bigr).

Same shape as the finite- $H$ formula: linear in $1/\varepsilon$ (up to a log), logarithmic in $1/\delta$ , and now linear in $VC(H)$ instead of $\ln|H|$ . VC dimension is the right capacity measure: it plays the role that $\ln|H|$ played for finite spaces.

E · Two structural theorems about VC dimension

thm

VC vs. log of hypothesis-space size

For any finite hypothesis space, $VC(H) \leq \log_2 |H|$ .

Proof (one line): if $VC(H) = d$ , there exists a set of $d$ points that $H$ shatters — i.e. $H$ realises all $2^d$ labellings on those points. Each labelling requires a distinct $h \in H$ , so $|H| \geq 2^d$ , i.e. $d \leq \log_2 |H|$ . $\square$

thm

Infinite VC ⟹ not PAC-learnable

A concept class $C$ with $VC(C) = \infty$ is not PAC-learnable. Intuition: if every finite sample size $N$ admits some configuration of $N+1$ points that $C$ can shatter, then no algorithm using $N$ examples can rule out all $\varepsilon$ -bad concepts — an adversary can always hide a bad target in the unshattered direction. Finite VC is the price of admission to PAC-learnability.

06 · Hands-on

Try it yourself

Three labs, each tuned to drill in one PAC/VC concept that has to be felt moving before it sticks. Push the sliders, drag the points, watch the numbers, then read the takeaway.

Hands-on 1

Sample-complexity calculator

Pick accuracy ε, confidence 1−δ, and the hypothesis-space size |H| = 3^M (conjunctions of literals over M features). The calculator reports the minimum N for the realisable PAC bound and the agnostic (Hoeffding) bound.

ε (accuracy)0.050

δ (failure)1e-2

M (features)20

|H| = 3^M

3,486,784,401

N realisable

532

N agnostic

5,316

agnostic / realisable

10.0×

Try thisStart at the spam-filter defaults (ε=.05, δ=.01, M=20) — about N ≈ 532. Halve ε: N doubles. Slide δ down by orders of magnitude: N barely moves. Crank M: N grows linearly.

TakeawayThe three knobs cost data asymmetrically — accuracy is expensive (1/ε, or 1/ε² agnostic), capacity is moderate (ln|H|), confidence is cheap (ln 1/δ). Confidence is the one PAC parameter you can almost always afford.

Hands-on 2

Watch the version space shrink

The target is the green interval. Each sample lands inside (positive, +) or outside (negative). The version space — every interval consistent with all samples — is bracketed by the tightest consistent interval (gold) and the loosest (dashed). Watch it collapse toward the truth.

version space huge

N samples

0

VS width (left)

—

VS width (right)

—

L_true(worst h)

0.350

Try thisFrom Reset, the version space is every interval. Each negative sample near an edge, and each positive sample, tightens the band. After ~10 samples it's narrow; after ~50 a sliver. The worst surviving hypothesis defines L_true(worst) — exactly what Haussler bounds.

TakeawayEach i.i.d. sample is a filter that removes consistent-but-bad hypotheses. The exponential |H|·e^(−εN) is just the formal accounting of this shrinkage.

Hands-on 3

Shattering check — drag the points

Three points in 2-D. Cycle through all 2³ = 8 possible ±-labellings; for each, a perceptron searches for a separating line. Drag a point to move it. As long as the three are in general position (not collinear), every labelling is realisable — that is what shattering looks like, and it proves VC ≥ 3 for lines in the plane.

+ + +linearly separable

pattern

+ + +

realisable?

yes

shattered (all 8)?

yes → VC ≥ 3

Try thisCycle through all eight patterns with the three points spread into a triangle — every one is separable, so the set is shattered. Now drag the points onto a straight line: patterns like + − + become impossible (the middle point can't sit on the opposite side of one line from both neighbours) and the “shattered” cell turns red. Collinear points are not in general position.

Takeaway VC(H) ≥ d only needs some configuration of d points to be shattered — not all of them. Any three non-collinear points work for 2-D lines, and no set of four ever does (the XOR labelling defeats every line), so VC = 3. That “some configuration” asymmetry catches a lot of students on the exam.

07 · Exam intel

What the exam actually tests

PAC and VC questions are short and structured — they’re the theoretical block of a Polimi ML exam. Five archetypes appear essentially every year.

Q1

Derive Haussler's bound from scratch

Start by fixing a single $\varepsilon$ -bad hypothesis. Show $\Pr(L_\text{train}=0 \mid L_\text{true}\geq \varepsilon) \leq (1-\varepsilon)^N$ . Union-bound over at most $|H|$ such hypotheses to get $|H|(1-\varepsilon)^N$ . Finish with the inequality $1-\varepsilon \leq e^{-\varepsilon}$ to obtain $|H|\,e^{-\varepsilon N}$ . Three steps, name each one, full marks.

Q2

Compute a sample-complexity bound

“Given $|H| = \ldots$ , $\varepsilon = \ldots$ , $\delta = \ldots$ , how many samples does PAC guarantee?” Apply $N \geq \tfrac{1}{\varepsilon}(\ln|H| + \ln\tfrac{1}{\delta})$ (realisable) or $N \geq \tfrac{1}{2\varepsilon^2}(\ln|H| + \ln\tfrac{1}{\delta})$ (agnostic). Watch which one is asked — the squared $\varepsilon$ is the agnostic signature.

Q3

Compute the VC dimension of a given class

Standard arguments expected at exam:

Hypothesis class	VC	Reasoning
1-D thresholds $h(x) = \mathbf{1}[x>\theta]$	1	Can shatter 1 point, not 2 (can’t realise $+\,-$ ).
1-D intervals $h(x) = \mathbf{1}[a\leq x\leq b]$	2	Two points: all four labellings; three points: can’t realise $+\,-\,+$ .
Linear classifier in $\mathbb{R}^M$	$M+1$	Hyperplane has $M+1$ parameters; general-position points are shatterable.
Axis-aligned rectangles in $\mathbb{R}^2$	4	Four points on a diamond shatterable; any five — one labelling fails.
Neural network with $P$ parameters	$O(P)$	Roughly linear in parameter count for most activations.
1-Nearest Neighbour	$\infty$	Can memorise any finite labelled set.
Gaussian-kernel SVM	$\infty$	Infinite-dim feature space — but effective capacity is controlled by margin.

Full-mark answers prove both $VC \geq d$ (exhibit a shatterable set) and $VC < d+1$ (show some labelling of every $(d+1)$ -set is unrealisable).

Q4

State the VC generalisation bound and SRM

Memorise both forms:

L_\text{true}(h) \;\leq\; L_\text{train}(h) \;+\; \sqrt{\,\frac{VC(H)(\ln\frac{2N}{VC(H)}+1) + \ln\frac{4}{\delta}}{N}\,},

N \;\geq\; \frac{1}{\varepsilon}\Bigl(4\log_2\tfrac{2}{\delta} + 8\,VC(H)\log_2\tfrac{13}{\varepsilon}\Bigr).

Then articulate SRM in one sentence: “Among a nested ladder of hypothesis spaces $H_1 \subset H_2 \subset \cdots$ , pick the one that minimises the right-hand side, not just the training error.” This is the principled cousin of cross-validation. Be ready to add the two structural facts: $VC \leq \log_2|H|$ for finite $H$ , and $VC = \infty$ rules out PAC-learnability.

Q5

Connect PAC bounds to the bias–variance picture

Be ready to point at the agnostic bound and identify: $L_\text{train} \approx$ bias term (small for large $H$ , large for small $H$ ); the $\sqrt{\ln|H|/N}$ or VC penalty $\approx$ variance term (the opposite). The trade-off sits inside the inequality. The “right” $H$ minimises the sum, which is exactly what Ch. 4’s cross-validation does empirically and SRM does analytically.

tip

Formulas to memorise verbatim

Version space: $VS_{H,D} = \{ h \in H : L_\text{train}(h) = 0 \}$ .
Haussler: $\Pr(\exists\,\varepsilon\text{-bad }h \in VS_{H,D}) \leq |H|e^{-\varepsilon N}$ .
Realisable PAC: $N \geq \tfrac{1}{\varepsilon}(\ln|H| + \ln\tfrac{1}{\delta})$ .
Hoeffding (two-sided): $\Pr(|\bar X - \mathbb{E}[X]| > \varepsilon) \leq 2e^{-2N\varepsilon^2}$ .
Agnostic PAC: $L_\text{true} \leq L_\text{train} + \sqrt{(\ln|H| + \ln\tfrac{1}{\delta})/(2N)}$ .
VC sample complexity: $N \geq \tfrac{1}{\varepsilon}(4\log_2\tfrac{2}{\delta} + 8\,VC(H)\log_2\tfrac{13}{\varepsilon})$ .
$VC(H) \leq \log_2 |H|$ when $H$ is finite; $VC = \infty \Rightarrow$ not PAC-learnable.

08 · Common mistakes

Where students get this wrong

×

'PAC says my classifier has error ≤ ε'

It says no such thing. PAC is a statement about probability: with probability $1-\delta$ over the choice of training set, the learner’s output has error $\leq \varepsilon$ . The remaining $\delta$ probability mass is unlucky training draws on which the learner can fail arbitrarily. There is no deterministic guarantee — there can’t be, since with tiny probability you could draw the same example $N$ times.

×

Confusing 'VC ≥ d' with 'VC = d'

To show $VC(H) \geq d$ you need to find one set of $d$ points that $H$ shatters. To show $VC(H) \leq d$ you need to prove that every set of $d+1$ points has at least one labelling $H$ cannot realise. The two halves are very different in spirit; a complete VC argument does both.

×

'VC dimension = number of parameters'

A useful heuristic — true for linear classifiers ( $VC = M+1$ parameters), neural nets ( $VC \approx P$ ). But not a law. Two concrete counter-examples from the slides:

One parameter, infinite VC. The class $h_w(x) = \mathrm{sign}(\sin(wx))$ on $\mathbb{R}$ has a single parameter $w$ , but by choosing $w$ extremely large you can realise any binary labelling of any finite set of points along the real line. $VC = \infty$ with just one knob.
Infinitely many parameters, finite effective capacity. An SVM with a Gaussian kernel implicitly works in an infinite-dimensional feature space — its formal VC dimension is $\infty$ — yet with margin regularisation it generalises beautifully. The margin controls effective capacity, not parameter count.

Moral: parameter count is a rough proxy. The right capacity measure depends on the geometry of the hypothesis class and the loss — VC for 0/1 loss, Rademacher complexity in general, margin-based bounds for kernel methods.

×

Using the realisable bound when L_train > 0

The bound $N \geq \tfrac{1}{\varepsilon}(\ln|H| + \ln\tfrac{1}{\delta})$ requires the existence of a hypothesis with zero training error (and assumes the learner picks one). If your best hypothesis has 8% training error, you are in the agnostic regime and must use the Hoeffding-based bound — which pays an extra $1/\varepsilon$ in sample complexity. Quoting the realisable formula in a noisy setting is a hallmark exam-time mistake.

×

'The bound is loose, so PAC is useless'

PAC bounds are notoriously loose numerically — they often predict needing 10× more data than works in practice. That’s because they are worst-case over all distributions $P$ and all targets $c$ , with no distributional assumptions. The shape of the bound (logarithm in $|H|$ and $1/\delta$ , linear in $1/\varepsilon$ , $M$ , or VC) is what we actually use — it tells us what to regularise, why bigger models need more data, and where SRM comes from.

×

Forgetting the i.i.d. assumption

Every bound in this chapter assumes training samples are drawn independently from the same distribution that will generate test data. If your data is time-series, or stratified, or comes from a different distribution at test time, none of these guarantees apply. Bounds for non-i.i.d. settings (online learning, domain adaptation) exist but are outside this chapter — and they are typically much weaker.

×

'Infinite VC means cannot learn'

Infinite VC means the worst-case PAC bound is vacuous, but it does not mean the algorithm can’t generalise on real problems. SVMs with Gaussian kernels have infinite VC and are world-class classifiers — because their effective capacity is controlled by the margin, regularisation, and data geometry. VC is one capacity notion; Rademacher complexity and margin-based bounds are others. Don’t conflate “infinite VC” with “doesn’t work”.

09 · Self-check

Can you answer these?

Five questions in the style the chapter typically gets tested. Click an option for instant feedback.

In the realisable PAC setting with finite |H|, how many examples are sufficient to guarantee with probability at least 1−δ that any consistent hypothesis has true error at most ε?

The version space VS_{H,D} is...

What is the VC dimension of the class of linear classifiers in ℝ^M (with bias term)?

You enlarge your hypothesis space from H₁ (|H₁| = 100) to H₂ (|H₂| = 10⁶). Holding N, δ, and the best in-class training error fixed, what happens to the agnostic bound L_true ≤ L_train + √((ln|H| + ln(1/δ))/2N)?

A hypothesis class H shatters a set S = {x₁, x₂, x₃, x₄} of four points. Which consequence is most accurate?

10 · Recap

One-screen summary

Chapter 05 — load-bearing ideas

PAC framework. i.i.d. samples $D \sim P^N$ , unknown target $c \in C$ , hypothesis space $H$ , and two knobs: accuracy $\varepsilon$ and confidence $\delta$ . We want $L_\text{true}(\hat h) \leq \varepsilon$ with probability $\geq 1-\delta$ .
Version space $VS_{H,D}$ . Hypotheses consistent with $D$ . Bad hypotheses can survive — Haussler bounds how often.
Haussler’s bound. $\Pr(\exists\,\varepsilon\text{-bad }h\in VS_{H,D}) \leq |H|e^{-\varepsilon N}$ . Three-line proof: $(1-\varepsilon)^N$ per bad $h$ , union-bound, $1-\varepsilon \leq e^{-\varepsilon}$ .
Realisable sample complexity. $N \geq \tfrac{1}{\varepsilon}(\ln|H| + \ln\tfrac{1}{\delta})$ . Linear in $1/\varepsilon$ , log in capacity and $1/\delta$ . Confidence is cheap.
Hoeffding inequality. For i.i.d. $X_i \in [0,1]$ : $\Pr(|\bar X - \mathbb{E}[X]| > \varepsilon) \leq 2e^{-2N\varepsilon^2}$ . Setting $X_i = \mathbf{1}[h(x_i)\neq c(x_i)]$ links it to $L_\text{train}$ and $L_\text{true}$ .
Agnostic bound. $L_\text{true} \leq L_\text{train} + \sqrt{(\ln|H| + \ln\tfrac{1}{\delta})/(2N)}$ . Squared $\varepsilon$ — noise costs data: agnostic sample complexity is $1/(2\varepsilon^2)$ instead of $1/\varepsilon$ .
Bias–variance, baked in. Big $H$ : $L_\text{train}$ small (low bias) but penalty large (high variance). Small $H$ : reversed. The right $H$ minimises the sum.
Inductive bias is mandatory. Unrestricted Boolean functions give $|H| = 2^{2^M}$ , so $N$ scales like $2^M$ — exponential. Restricted classes (conjunctions, half-spaces, …) make learning possible.
Shattering & VC dimension. $H$ shatters $S$ iff all $2^{|S|}$ labellings of $S$ are realisable. $VC(H)$ = size of largest shatterable set. For finite $H$ , $VC \leq \log_2|H|$ .
VC of canonical classes. 1-D thresholds: 1. 1-D intervals: 2. Linear classifiers in $\mathbb{R}^M$ : $M+1$ . Axis-aligned rectangles in $\mathbb{R}^2$ : 4. 1-NN and Gaussian-kernel SVM: $\infty$ .
VC generalisation bound. $L_\text{true}(h) \leq L_\text{train}(h) + \sqrt{(VC(H)(\ln\frac{2N}{VC(H)}+1) + \ln\frac{4}{\delta})/N}$ . VC sample complexity: $N \geq \tfrac{1}{\varepsilon}(4\log_2\tfrac{2}{\delta} + 8\,VC(H)\log_2\tfrac{13}{\varepsilon})$ . Infinite VC ⟹ not PAC-learnable.
Structural Risk Minimisation. Among nested $H_1 \subset H_2 \subset \cdots$ , pick the one minimising the VC bound. Principled regularisation; the theoretical sibling of cross-validation.

→

Looking ahead → Chapter 06

We now know how much capacity costs. Next we exploit it: kernel methods lift data into rich feature spaces where linear separation is easy, while the margin — not the parameter count — keeps effective capacity under control.