Growth Bounds for Finite Hypothesis Classes

Why Bound the Number of Label Patterns?

A hypothesis class may contain many functions, yet on a particular finite sample several functions can produce the same labels. The growth function counts the distinct patterns the class can produce, not the number of functions themselves. Bounding this count is useful because it distinguishes the sheer size of a class from the restrictions imposed by its combinatorial structure.

For a finite class, its cardinality gives an immediate bound. If the class also has finite VC dimension, the Sauer–Shelah lemma gives a second bound that depends on the sample size and VC dimension. The smaller of the two is the sharper upper bound. Neither bound is necessarily the exact growth function.

Definitions and the Two Bounds

Definition: Let \(\mathcal{H}\) be a class of binary functions \(h:\mathcal{X}\to\{0,1\}\). For points \(x_1,\ldots,x_n\), the set of label vectors induced by \(\mathcal{H}\) is \(\{(h(x_1),\ldots,h(x_n)):h\in\mathcal{H}\}\). The growth function \(\Pi_{\mathcal{H}}(n)\) is the maximum, over all choices of \(n\) points in \(\mathcal{X}\), of the number of distinct such vectors. A set of points is shattered if every binary labeling of those points is induced by some \(h\in\mathcal{H}\). The VC dimension \(d\) is the largest size of a shattered set, when such a largest finite size exists.

Repeated points are allowed in the definition of the growth function. They cannot increase the number of patterns beyond what can be realized on the distinct points among them. The VC dimension, by contrast, concerns sets of distinct points.

If \(\mathcal{H}\) contains \(M\) distinct functions, there are at most \(M\) patterns on any sample. There are also only \(2^n\) possible binary label vectors on \(n\) points. These observations give simple bounds before VC dimension is considered.

Theorem: If \(\mathcal{H}\) is a finite nonempty binary hypothesis class with \(|\mathcal{H}|=M\), then for every \(n\geq 0\), \(\Pi_{\mathcal{H}}(n)\leq \min\{M,2^n\}\).

Proof. Fix any \(n\) points. Each of the \(M\) hypotheses induces one label vector, so the number of distinct vectors is at most \(M\). There are exactly \(2^n\) binary vectors of length \(n\), so the number induced is also at most \(2^n\). Taking the maximum over samples preserves both inequalities, giving the stated bound. \(\square\)

The \(2^n\) term is a limit on the total number of possible patterns, whether or not the class is finite. The \(M\) term is specific to a finite class. Neither fact uses VC dimension.

Adding the Sauer–Shelah Bound

The Sauer–Shelah lemma gives a potentially different restriction: a class with VC dimension \(d\) cannot realize too many patterns on \(n\) points. In the statement below, \(\binom{n}{j}=0\) when \(j>n\), so the sum automatically equals \(2^n\) if \(d\geq n\).

Theorem: If a binary hypothesis class \(\mathcal{H}\) has VC dimension \(d<\infty\), then for every \(n\geq 0\), \(\Pi_{\mathcal{H}}(n)\leq \sum_{j=0}^{d}\binom{n}{j}\). This is the Sauer–Shelah bound.

For a finite class of size \(M\) and VC dimension \(d\), combine the cardinality bound with Sauer–Shelah:

\Pi_{\mathcal{H}}(n) \leq \min\left\{M,\;2^n,\;\sum_{j=0}^{d}\binom{n}{j}\right\}.

When \(d<n\), the Sauer–Shelah sum is smaller than \(2^n\), so the cardinality-versus-VC comparison is usually written as \(\Pi_{\mathcal{H}}(n)\leq\min\{M,\sum_{j=0}^{d}\binom{n}{j}\}\). When \(d\geq n\), the sum is \(2^n\), and the cardinality bound supplies any additional restriction. In particular, if \(d\) is fixed and \(n\) grows, the Sauer–Shelah sum grows at most polynomially in \(n\), whereas the unrestricted number of patterns \(2^n\) grows exponentially.

The combined inequality is an upper bound, not an assertion that the growth function equals the smaller term. It says that a pattern count cannot exceed either limit. Which term is more informative depends on the relationship between \(M\), \(n\), and \(d\).

Worked Comparisons

Worked Example: A Class Where Cardinality Is Tighter

Let \(\mathcal{X}=\{a,b,c\}\), and let \(\mathcal{H}\) contain the four indicator functions of the subsets \(\varnothing,\{a\},\{b\},\{a,b\}\). Thus each function is zero at \(c\), and \(|\mathcal{H}|=4\). Find the bounds for \(n=10\), and verify the VC dimension.

The points \(a\) and \(b\) are shattered: the four functions produce, respectively, the four labelings \((0,0),(1,0),(0,1),(1,1)\). No set containing \(c\) can be shattered because every hypothesis labels \(c\) as zero. Since the domain has only three points, a shattered set of size three would have to include \(c\), which is impossible. Hence \(d=2\).

The cardinality bound is \(4\). The Sauer–Shelah sum at \(n=10\) is \(\binom{10}{0}+\binom{10}{1}+\binom{10}{2}=1+10+45=56\). The total number of possible vectors is \(2^{10}=1024\). Therefore the combined bound is \(\min\{4,56,1024\}=4\).

In fact, the class induces exactly four patterns on any sample that includes both \(a\) and \(b\), and no sample can produce more than four. Here the cardinality bound is exact, while the Sauer–Shelah bound is valid but loose.

Worked Example: VC Dimension Gives a Much Smaller Bound

Let \(\mathcal{X}=\{1,\ldots,100\}\), and let \(\mathcal{H}\) consist of the 100 indicator functions of singleton subsets: \(h_j(x)=1\) if \(x=j\), and \(h_j(x)=0\) otherwise. Take \(n=4\). Compare the bounds and find the growth function at this sample size.

The class has \(M=100\) functions. Its VC dimension is one. Any single point \(x\) can receive either label: \(h_x\) labels it one, while \(h_j\) for \(j\ne x\) labels it zero. But no pair can be shattered, because no singleton indicator labels both points one. Thus \(d=1\).

The cardinality bound is \(100\), while Sauer–Shelah gives \(\binom{4}{0}+\binom{4}{1}=1+4=5\). The total-pattern bound is \(2^4=16\), so the combined bound is \(\min\{100,5,16\}=5\).

Choose four distinct sample points. The all-zero vector is produced by any singleton outside those four points. Each of the four vectors with exactly one coordinate equal to one is produced by the singleton at that coordinate. No other vector is possible, since a singleton cannot label two sample points one. Thus there are exactly five patterns and \(\Pi_{\mathcal{H}}(4)=5\). Here VC dimension, rather than class cardinality, gives the sharp restriction.

Worked Example: A Finite Threshold Class and Saturation

On \(\mathcal{X}=\{1,2,3,4\}\), define \(h_k(x)=1\{x\leq k\}\) for \(k=0,1,2,3,4\). Find the cardinality and VC bounds for \(n=8\), and determine the growth function.

There are five distinct thresholds, so \(M=5\). A single point can receive either label, and no two points can be shattered: on an ordered pair \(x<y\), a threshold cannot label \(x\) zero and \(y\) one. Thus \(d=1\).

For \(n=8\), the cardinality bound is \(5\), and the Sauer–Shelah sum is \(\binom{8}{0}+\binom{8}{1}=9\). The number of possible label vectors is \(2^8=256\), so the combined bound is \(5\).

The class induces five distinct patterns on a sample containing all four domain points: the all-zero vector and the four successive threshold patterns. Repeating points to form a sample of size eight does not create new patterns. Hence \(\Pi_{\mathcal{H}}(8)=5\). In this case the finite class has already reached its maximum possible number of distinct patterns, and the cardinality bound is the useful one.

How Class Size and VC Dimension Relate

For a finite class, VC dimension cannot be arbitrarily large relative to cardinality. If \(d\) points are shattered, the class must contain a hypothesis for each of the \(2^d\) labelings of those points. These hypotheses must be distinct, because two different labelings cannot be induced by the same function on the same points.

Result: If a finite class \(\mathcal{H}\) has VC dimension \(d\), then \(2^d\leq|\mathcal{H}|\), and consequently \(d\leq\log_2|\mathcal{H}|\).

Proof. By the definition of VC dimension, some set of \(d\) points is shattered. Each of the \(2^d\) binary labelings on this set is induced by at least one member of \(\mathcal{H}\). A single member induces only one labeling on the fixed set, so distinct labelings require distinct members of \(\mathcal{H}\). Therefore \(|\mathcal{H}|\geq2^d\). Taking base-two logarithms gives \(d\leq\log_2|\mathcal{H}|\). \(\square\)

This is a necessary relationship, not a formula for the growth function. A class may have many functions but low VC dimension, as the singleton example showed. Conversely, a class needs at least \(2^d\) functions to shatter \(d\) points, but having that many functions alone does not guarantee that any particular set is shattered.

Choosing the Informative Bound

For a finite class, first compare \(M\) with the Sauer–Shelah sum \(S(n,d)=\sum_{j=0}^{d}\binom{n}{j}\). If \(M<S(n,d)\), the cardinality term is smaller. If \(S(n,d)<M\), the VC-dimension term is smaller. If the two are equal, they provide the same numerical upper bound. Include \(2^n\) when using a formula that allows \(d\geq n\); it is the absolute limit on binary patterns.

A common mistake is to treat the Sauer–Shelah bound as automatically sharper because it uses VC dimension. That is not correct: for a small finite class, \(M\) may be far below the Sauer–Shelah sum. The reverse mistake is to assume that a large finite class can realize nearly \(M\) patterns on every sample. A low VC dimension can prevent this, even when \(M\) is large.

Key takeaway: A finite class has at most \(M\) patterns on any sample, while finite VC dimension limits the count to the Sauer–Shelah sum. Use the smaller bound, and remember that it is an upper bound on the growth function—not necessarily its exact value.

Check Your Understanding

For each question, identify which restriction is relevant and justify your answer.

A finite binary class has \(M=12\) hypotheses and VC dimension \(d=1\). What bound does the combined inequality give for \(n=5\)?
Why must a class that shatters four points contain at least 16 distinct hypotheses?
Can a class with 50 hypotheses have VC dimension 6? Use the cardinality–VC relationship to decide.
For a class with VC dimension \(d=3\), write the Sauer–Shelah bound at \(n=6\).
Explain why a bound of 20 on the number of patterns does not imply that the class actually produces 20 patterns on every sample.