Subgraph Classes and Pseudo-Dimension

From Real-Valued Functions to Set Classes

VC dimension is defined for classes of sets, while many statistical learning problems involve real-valued functions: prediction scores, regression functions, or losses. A subgraph turns each such function into a set in a larger space. This translation lets us use VC dimension to count how many different threshold comparisons the function class can make on finitely many inputs.

Let \(\mathcal X\) be a set and let \(\mathcal F\) be a class of real-valued functions \(f:\mathcal X\to\mathbb R\). We use the strict subgraph convention: a point \((x,t)\) belongs to the subgraph of \(f\) precisely when the function value at \(x\) exceeds the level \(t\).

Definition: The subgraph of \(f\) is the set \(\operatorname{subgraph}(f)=\{(x,t)\in\mathcal X\times\mathbb R:t<f(x)\}\). The subgraph class of \(\mathcal F\) is \(\operatorname{subgraph}(\mathcal F)=\{\operatorname{subgraph}(f):f\in\mathcal F\}\). The pseudo-dimension of \(\mathcal F\), denoted \(\operatorname{Pdim}(\mathcal F)\), is the VC dimension of \(\operatorname{subgraph}(\mathcal F)\).

Recall that a set of \(m\) points is shattered by a set class if every one of its \(2^m\) subsets is the intersection of that point set with some member of the class. Here the points being tested are pairs \((x_i,t_i)\), not inputs \(x_i\) alone. Thus pseudo-dimension allows a different real threshold \(t_i\) at each input \(x_i\). Under the strict convention, equality \(f(x_i)=t_i\) gives a negative comparison.

Threshold Comparisons Are Subgraph Membership

For any chosen pairs \((x_i,t_i)\), membership of each pair in a subgraph records exactly one binary comparison. This gives the direct link between pseudo-dimension and the number of thresholded patterns.

Proposition: For a fixed list \((x_1,t_1),\ldots,(x_m,t_m)\), the comparison vector produced by \(f\in\mathcal F\) is \((\mathbf 1\{f(x_i)>t_i\})_{i=1}^m\). The set of all such vectors, as \(f\) ranges over \(\mathcal F\), is exactly the set of membership vectors of \(\operatorname{subgraph}(\mathcal F)\) on those \(m\) points. Consequently, \(\operatorname{Pdim}(\mathcal F)\ge m\) if and only if there are \(m\) input-threshold pairs for which every binary comparison vector is attained.

To verify the proposition, fix \(f\). Its \(i\)th membership indicator is \(\mathbf 1\{(x_i,t_i)\in\operatorname{subgraph}(f)\}\), which equals \(\mathbf 1\{t_i<f(x_i)\}\). This is exactly \(\mathbf 1\{f(x_i)>t_i\}\) for every \(i\). Therefore the two collections of vectors coincide for every \(f\), and so do their collections over \(\mathcal F\). The final statement is the definition of shattering applied to the points \((x_i,t_i)\). \(\square\)

The thresholds need not be equal. Requiring one common threshold is a more restricted way to test a class and does not, in general, determine its pseudo-dimension. The point-specific thresholds are what make the definition equivalent to VC dimension on the product domain \(\mathcal X\times\mathbb R\).

Worked Example: Constant Functions

Let \(\mathcal F\) contain every constant function on a nonempty domain: \(f_c(x)=c\) for \(c\in\mathbb R\). We show that \(\operatorname{Pdim}(\mathcal F)=1\).

A single pair, for example \((x,0)\), is shattered. Choosing \(c=1\) gives \(f_c(x)>0\), while choosing \(c=-1\) gives \(f_c(x)\not>0\). Thus the pseudo-dimension is at least one.

Now take any two pairs with thresholds \(t_1\le t_2\). If a constant \(c\) satisfies \(c>t_2\), then it also satisfies \(c>t_1\). Therefore the pattern \((0,1)\) is impossible on these two pairs. If instead \(t_2<t_1\), the same reasoning shows that the pattern \((1,0)\) is impossible. No pair of points can be shattered, so the pseudo-dimension is at most one. Together, the bounds give \(\operatorname{Pdim}(\mathcal F)=1\).

A Growth Bound for Thresholded Patterns

Define the growth function \(\Pi_{\mathcal F}(m)\) to be the maximum, over all lists of \(m\) pairs \((x_i,t_i)\), of the number of distinct vectors \((\mathbf 1\{f(x_i)>t_i\})_{i=1}^m\) produced by functions \(f\in\mathcal F\). This is the growth function of the subgraph class on the product domain. If the pseudo-dimension is finite, the Sauer–Shelah lemma gives a bound that applies uniformly to every choice of inputs and thresholds.

Theorem: Suppose \(\operatorname{Pdim}(\mathcal F)=d<\infty\). For every integer \(m\ge 0\), \(\Pi_{\mathcal F}(m)\le\sum_{j=0}^{\min(d,m)}\binom{m}{j}\). In particular, when \(m\ge d\), the number of threshold-comparison patterns is at most \(\sum_{j=0}^{d}\binom{m}{j}\).

Proof. Fix any \(m\) pairs \((x_i,t_i)\). By the proposition, the comparison vectors are precisely the membership patterns of the subgraph class on these \(m\) product-space points. That set class has VC dimension \(d\), by the definition of pseudo-dimension. The Sauer–Shelah lemma states that a set class of VC dimension \(d\) produces at most \(\sum_{j=0}^{\min(d,m)}\binom{m}{j}\) distinct intersections on any \(m\)-point set. Applying it to the fixed pairs gives this bound for their comparison vectors. Since the bound does not depend on which pairs were fixed, taking the maximum over all such lists proves the stated growth-function bound. \(\square\)

When \(m\le d\), the sum is \(2^m\), so the bound allows every pattern. When \(m>d\), it is strictly smaller than \(2^m\): a class with finite pseudo-dimension cannot realize all possible threshold-comparison patterns at arbitrarily large sample sizes. The bound controls the number of patterns, not the numerical range of the functions or the size of their prediction errors.

Worked Example: Affine Functions on the Real Line

Let \(\mathcal F=\{f_{a,b}:f_{a,b}(x)=ax+b,\ a,b\in\mathbb R\}\). We show that \(\operatorname{Pdim}(\mathcal F)=2\).

For a lower bound, choose the pairs \((0,0)\) and \((1,0)\). The function values there are \(b\) and \(a+b\), respectively. For any desired two-bit pattern, set these two values to \(1\) for a positive bit and \(-1\) for a negative bit. If the chosen values are \(u\) at \(0\) and \(v\) at \(1\), take \(b=u\) and \(a=v-u\). This produces exactly the desired strict comparisons against zero. Thus the two pairs are shattered, and the pseudo-dimension is at least two.

For the upper bound, consider any three pairs. If two have the same input \(x\), order their thresholds as \(t_1\le t_2\). The comparison at \(t_2\) being positive forces the comparison at \(t_1\) to be positive, so the two pairs cannot be shattered.

It remains to consider three distinct inputs, ordered \(x_1<x_2<x_3\). Write \(\lambda=(x_3-x_2)/(x_3-x_1)\), so \(0<\lambda<1\) and \(x_2=\lambda x_1+(1-\lambda)x_3\). Every affine function satisfies \(f(x_2)=\lambda f(x_1)+(1-\lambda)f(x_3)\). If the endpoint comparisons are both positive, then \(f(x_1)>t_1\) and \(f(x_3)>t_3\), so \(f(x_2)>\lambda t_1+(1-\lambda)t_3\). For the middle comparison to be negative, \(f(x_2)\le t_2\), which requires \(t_2>\lambda t_1+(1-\lambda)t_3\).

But if the endpoint comparisons are both negative, then \(f(x_1)\le t_1\) and \(f(x_3)\le t_3\), giving \(f(x_2)\le\lambda t_1+(1-\lambda)t_3\). A positive middle comparison would require \(f(x_2)>t_2\), and hence \(t_2<\lambda t_1+(1-\lambda)t_3\). The two required inequalities on \(t_2\) cannot both hold. Therefore at least one of these two label patterns is impossible, and no three pairs are shattered. The pseudo-dimension is at most two, proving \(\operatorname{Pdim}(\mathcal F)=2\).

Worked Example: A Two-Function Class

Let \(\mathcal F=\{f_0,f_1\}\), where \(f_0(x)=0\) and \(f_1(x)=1\) for every \(x\). At any fixed input \(x\), the pair \((x,1/2)\) is shattered: \(f_0(x)\not>1/2\), while \(f_1(x)>1/2\). Hence \(\operatorname{Pdim}(\mathcal F)\ge1\).

For any list of two pairs, there are only two functions in the class and therefore at most two comparison vectors. Shattering two pairs would require all four distinct vectors, so it is impossible. Thus \(\operatorname{Pdim}(\mathcal F)=1\). For three pairs, the growth bound gives at most \(\binom{3}{0}+\binom{3}{1}=1+3=4\) patterns; the class in fact produces at most two. The general bound need not be tight for a particular class.

Why the Translation Matters

Pseudo-dimension makes a set-based complexity tool available for real-valued classes. Once the subgraph class has finite VC dimension, the growth bound limits the number of ways its functions can lie above chosen levels at finitely many inputs. This is useful when an argument depends on exceedance events or thresholded predictions, even though the original model outputs real numbers.

The bound is uniform in the finite list: inputs and thresholds may be chosen arbitrarily before counting the patterns. It does not by itself establish a bound on prediction errors, nor does it automatically give a uniform deviation result for a real-valued loss. Those conclusions require additional arguments and assumptions.

Common mistake: using only one threshold for all inputs. That tests comparisons \(f(x_i)>t\) at a common \(t\), while pseudo-dimension allows a separate \(t_i\) for each \(x_i\). The correction is to formulate the shattering points in \(\mathcal X\times\mathbb R\).
Common mistake: treating a real-valued class as though it were already a set class. The functions themselves are not sets. The subgraph construction creates a set class, and its VC dimension is what defines pseudo-dimension.
Common mistake: interpreting the growth bound as a bound on function values. Sauer–Shelah limits the number of binary patterns, not the magnitude or range of \(f(x)\).

Key takeaway: \(\operatorname{Pdim}(\mathcal F)\) is the VC dimension of the subgraph class. It measures how many input-threshold pairs can be shattered and, through Sauer–Shelah, controls the number of threshold-comparison patterns on any finite list.

Check Your Understanding

Try these questions using the strict comparison convention \(f(x)>t\).

State the subgraph of a function \(f:\mathcal X\to\mathbb R\) and the domain on which its subgraph class is defined.
What does it mean for \(m\) input-threshold pairs to be shattered by \(\mathcal F\)?
If \(\operatorname{Pdim}(\mathcal F)=3\), what Sauer–Shelah bound applies to the number of comparison patterns on five pairs?
Why does a common-threshold test fail to express the full definition of pseudo-dimension?
For the class of all constant real-valued functions, explain why one pair can be shattered but no two pairs can be shattered.

Subgraph Classes and Pseudo-Dimension

What You'll Learn