Motivation
A hypothesis class can be infinite while behaving like a small finite class on any one finite sample. Real-line thresholds, for example, can place their cut at infinitely many positions, but on ordered inputs they produce only different label patterns. A generalization proof can count these patterns rather than count every hypothesis separately. The difficulty is that the sample on which the patterns are counted is itself random, and the learner chooses its hypothesis after seeing its labels.
The growth function measures the largest number of patterns possible on any sample of a given size. VC dimension records the largest set on which every pattern is possible. Sauer–Shelah turns a finite VC dimension into a polynomial growth bound. A separate probabilistic argument then converts that count into a simultaneous error guarantee. Neither counting nor empirical fit alone is a population guarantee: the data must be drawn under the stated probabilistic assumptions.
Definitions
Definition 2.1.1
(Trace, growth function and shattering)
Let be a nonempty measurable space and a nonempty class of measurable functions . For a finite set , its trace is
The set is shattered if . The VC dimension is the largest cardinality of a shattered finite set, or infinity if there is no finite maximum. Define the growth function by
Tuples may repeat points; repetitions cannot increase the number of patterns. A set of size is shattered precisely when it realizes all patterns. Finite VC dimension means some -point set is shattered, but no -point set is. Every subset of a shattered set is shattered: extend each labeling of the subset arbitrarily to the larger set. When , the empty set is shattered because is nonempty.
The trace depends on the inputs, not on their observed labels. Two hypotheses with different predictions elsewhere can give the same trace and therefore contribute only one pattern on these inputs. Conversely, an infinite class need not have infinite VC dimension. If is finite, the definition still allows repeated sample points, which is natural for sampling with replacement.
Definition 2.1.2
(Population and empirical errors)
Let be any distribution on labeled pairs , where . For set
where is drawn independently from . The distribution may have label noise and need not be realizable by . Uniform convergence bounds simultaneously for every on one high-probability event. It therefore also covers a hypothesis selected after the sample is observed.
For the probability proof below, assume is countable. This makes the relevant suprema and witness selections measurable without introducing additional empirical-process machinery. The combinatorial theorem itself does not need countability. Many uncountable classes admit extensions of the probability theorem under suitable measurability conditions; those conditions are not automatic and are not proved here.
Theorem/Proposition
Theorem 2.1.3
(Sauer–Shelah growth bound)
If has finite VC dimension , then for each integer ,
with for . In particular, for fixed the number of possible patterns is at most a polynomial in of degree , rather than .
Theorem 2.1.4
(Uniform error bound via a ghost sample)
Let be countable and measurable as above, and let contain i.i.d. labeled examples from an arbitrary . For with ,
The right side may exceed one, in which case the bound is valid but uninformative. Combining it with Sauer–Shelah gives a distribution-free bound for countable finite-VC classes; no assumption that the labels are noiseless is needed.
For a confidence parameter and VC dimension , define
The logarithm is natural. Because , the theorem applies: with probability at least , all satisfy . The expression is an explicit certificate, not a claim of the best possible constant or rate in every special model.
The growth bound also makes the rate visible without a sharper binomial estimate. Encode each subset of at most elements of an -point set by listing its elements in increasing order and padding the list to length with zeros. This is an injection into , so . Consequently
For fixed and this upper bound tends to zero. The logarithm in is a feature of this particular bound, not a proof that no stronger theorem can remove it. An estimate with a radius above one is still valid but cannot improve the trivial error bound.
Proof sketch or proof idea
Proof
(The combinatorial recurrence)
Fix distinct points and identify a trace with a subset of them. Delete the last point from every trace. Let be the family of resulting subsets, and let consist of the subsets that arise both with and without the last point. Every member of has one or two original extensions, so
The class has VC dimension at most , since any subset it shatters was already shattered by . If is nonempty, its VC dimension is at most : if shattered of the remaining points, then for each labeling on those points there would be a trace in with that labeling. Both choices of the deleted point occur for that trace, so would shatter those points together with the deleted one. This contradicts the definition of .
The induction claim is for every finite family of subsets of an -point set with VC dimension at most , not only for traces of the original class. The empty family has size zero and satisfies the bound trivially. Induct simultaneously on and . For , two different traces would differ at a point and shatter that singleton, so there is at most one trace. For the elementary bound is exactly the full binomial sum. In the remaining cases the induction hypothesis gives
The last step is Pascal's identity. Repeated sample points only reduce the number of distinct patterns, so the same bound applies to the tuples in .
Proof
(From a second sample to a uniform bound)
Let be an independent “ghost” sample of the same size. For a fixed , its ghost empirical error has mean and variance at most . Chebyshev's inequality gives
If has a bad hypothesis with , choose the first such hypothesis in a fixed enumeration of . Conditional on , the independent ghost sample has probability at least one half of placing that hypothesis within of its true error. The triangle inequality then gives . Consequently,
To bound the right side, pair the th examples of and and independently swap the two members of each pair with probability one half. Exchangeability leaves their joint distribution unchanged. Conditional on the labeled examples before these swaps, only prediction patterns can occur. The pooled labels are fixed too, so each prediction pattern determines its error-difference vector. For a fixed pattern, the difference of the two empirical errors is a mean of independent signed terms with mean zero, each lying in . Hoeffding's inequality gives probability at most that its absolute value exceeds . A union bound over the patterns and then averaging over the paired data prove the theorem, including the leading factor four.
The counting happens after conditioning on the pooled inputs, but before choosing a pattern that violates the bound. This is why a union bound over finitely many sample patterns can control a data-dependent choice from a countable, possibly infinite class. The ghost sample is a proof device; the learner is not required to acquire its labels.
Proof X-ray
Two reductions, not one
Sauer–Shelah is deterministic: it bounds how many label patterns a class can create on fixed inputs. Symmetrization is probabilistic: independent ghost data and random pair swaps relate true error to finitely many random empirical comparisons. The growth function enters only at the counting step. Separating these steps prevents the false inference that a low VC dimension makes a particular training sample representative with certainty.
A fast rate for consistent hypotheses
A two-sided deviation bound controls at the scale . For hypotheses with no sample errors, the bound below has an exponential factor , multiplied by a growth-function factor. Finite VC dimension bounds that factor polynomially, yielding an eventual faster rate. We prove this with a ghost sample and independent swaps.
In this section is the labeled distribution used in the definition of above. Write for empirical error; the analogous notation applies to , and .
Theorem 2.1.5
(Fast rate for consistent hypotheses)
Let be a nonempty countable class of measurable classifiers. Let be any distribution on labeled examples, and let with . If , then
The theorem does not assume realizability; it bounds an event under every . Realizability matters only afterwards: if some fixed has , it is sample-consistent almost surely, so a consistent hypothesis exists almost surely.
Proof
(Ghost sample, swaps and a Chernoff bound)
Known inequality (multiplicative Chernoff). Let be a sum of independent Bernoulli variables with , and let . Then .
Ghost sample. Let be independent of . Let be the event in the theorem, and let be the event that some has and .
Enumerate . On , let be the first with and . Because is countable, this first witness is a measurable function of .
Given , the count is a sum of independent Bernoulli variables. Here , so . Put . Then and . Chernoff gives
where the last step uses . So on . That event lies inside . Averaging over gives , so we lose a factor .
Swaps. Write and . Let be independent uniform bits, independent of . Form by exchanging and whenever . Since and are i.i.d., has the same law as . Hence equals the probability of the same event for .
Now condition on the pooled pre-swap data . Each gives an error vector , with iff errs on and iff errs on . This vector is determined by the labels assigns to the points. So at most distinct vectors occur; repeated points can only lower the count.
Fix one vector.
- If for some , one of those two errors lands in whatever is. Then is impossible.
- Otherwise, let be the number of pairs with exactly one error. The ghost side then has at most errors, so the event needs . It also needs each of those pairs to send its erroneous member to . This has probability .
A union bound over the vectors gives a conditional probability at most . Averaging over the pooled data gives the same bound for . Since , the ghost-sample step completes the proof.
Remarks
Why the ghost sample is needed. Hypotheses that agree on can have different risks, because depends on all of . Counting behaviors on alone does not give the uniform risk bound proved here, and a direct unweighted union bound over an infinite can be uninformative. The ghost sample replaces by . That quantity depends only on points, which is exactly what counts.
The bound may exceed 1. For small it is vacuous.
Sample size. Let and . Sauer–Shelah gives . Subject also to , it suffices that . This is an implicit sufficient sample-size inequality: the growth term is logarithmic in , while the exponential factor depends on . If and is nonempty, , so use the original bound with and . Under realizability, any consistent output then has with probability at least . These are sufficient bounds, not matching lower bounds or efficient algorithms.
Worked example 2.1.6
(Thresholds under the fast-rate bound)
Let on with ; this class is countable. On distinct points, a threshold labeling is fixed by how many sorted points lie at or above . The rationals are dense, so all choices occur, giving .
Take and . Then , and the bound is
The bound is sufficient, not optimal; far smaller also works.
Quick check
(For the same class with , show that makes the bound smaller than .)
Check the condition on , then evaluate .
Solution · Answer
The condition holds: . Next, and , so the bound is . Under realizability, a consistent output therefore has risk at most with probability at least .
Worked examples
Worked example 2.1.7
(Thresholds: infinitely many rules, linearly many patterns)
Let on . Every single point can receive either label, while for the labels are impossible. Thus . On distinct ordered inputs, a rational cut can be placed in each of the gaps, including beyond the endpoints, so . Sauer–Shelah is exact in this case. The countability restriction is satisfied, although the class is infinite. Real-parameter thresholds have the same finite traces, but the countable-class probability theorem does not automatically extend to them: additional measurability or a separate approximation argument is needed, especially when the input distribution has atoms.
Worked example 2.1.8
(A numerical certificate and its cost)
For these thresholds, . With and , the explicit uniform radius is
Thus the theorem certifies a simultaneous deviation below about with probability at least . This bound is deliberately general and can be conservative. It concerns every threshold at once; it is not an estimate of the actual error of one fitted model.
Worked example 2.1.9
(How empirical risk minimization uses the event)
Fix an enumeration of nonempty countable and let be the first empirical minimizer in that enumeration. A minimum exists because empirical errors belong to the finite set , and this tie-breaking rule gives a measurable selection. On the event that every deviation is at most ,
for every . Taking the infimum yields . The best true risk need not be attained. The guarantee includes approximation error ; it does not assume that a perfect classifier exists in the class.
Counterexample mode
Training accuracy alone does not imply generalization
Take with equal probabilities and deterministic labels at , at . The constant-one hypothesis has true error . If all sampled inputs happen to be , an event of probability , its empirical error is zero. A high-probability theorem can bound the frequency of unrepresentative samples; it does not say that no such sample exists.
Common mistakes
Common mistake
(Confusing VC dimension with the number of hypotheses)
A VC dimension of one does not mean that the class contains only one rule. It means that at least one point can be shattered but no pair can be shattered. Growth counts distinguishable labelings on a finite sample; different hypotheses that agree on that sample count only once.
Common mistake
(Using a fixed-hypothesis bound after fitting)
A concentration inequality for one preselected cannot simply be applied to a hypothesis chosen after seeing the same sample. The uniform theorem creates one event on which all hypotheses are controlled; the fitted hypothesis can then be inserted. Check both the i.i.d. assumption and the measurability condition before using the probability statement.
Summary
Shattering measures which label patterns are realizable; the Sauer–Shelah recurrence controls the maximum pattern count. A ghost sample, random swaps and concentration turn that count into a simultaneous deviation guarantee. Empirical risk minimization uses the uniform event to compare fitted risk with the best risk available in the class, even with noisy labels.
Exercises
Quick check
(On a domain of distinct points, let contain every binary function. Find and for .)
Count the patterns on distinct points.
Solution · Answer
The entire domain is shattered and no larger set exists, so . For , choose distinct points: all patterns occur, and there cannot be more. Thus .
Quick check
(For on , calculate and compare it with .)
Count the cut positions among six ordered inputs.
Solution · Answer
Six distinct ordered inputs attain one pattern per possible cut; repeated inputs cannot introduce extra cuts, so , much smaller than . The bound is attained.
Quick check
(Suppose a uniform convergence event has radius and an empirical risk minimizer has empirical error . Give an upper bound for its true error and a separate bound relative to .)
One bound uses the event directly, the other compares with every .
Solution · Answer
The uniform event gives . The empirical-minimization argument gives . These are different statements; neither identifies the unknown best risk.
Quick check
(Consider the class containing just the two constant classifiers on a nonempty domain. Find its VC dimension and growth function for , and verify the Sauer–Shelah inequality.)
Which pairs of distinct points can be shattered?
Solution · Answer
One point can receive either label, so the dimension is at least one. No two distinct points can receive different labels under a constant classifier, so the dimension is one when the domain has at least two points; on a singleton it is also one because no larger subset exists. For every , the two traces are all zeros and all ones, hence .