Pseudo-Dimension of Real-Valued Examples

From Subgraph Labels to Geometric Constraints

For a real-valued function class, complexity is not determined just by how many different function values it can take. The key question is how many binary label patterns its functions can produce when each input is compared with its own real-valued threshold. This comparison turns a class of functions into a class of binary labelings, making geometric tools for VC dimension available.

The central calculation in this tutorial is to express those labels as inequalities. For threshold indicators, the inequalities are ordered by a single threshold parameter. For linear functions, they become hyperplanes in the parameter space. The resulting geometry gives exact dimensions and clarifies when restrictions on the inputs matter.

Definition: Let $\mathcal F$ be a class of real-valued functions on a domain $\mathcal X$. A finite collection $(x_1,r_1),\ldots,(x_m,r_m)$ in $\mathcal X\times\mathbb R$ is pseudo-shattered by $\mathcal F$ if, for every subset $I\subseteq\{1,\ldots,m\}$, there is an $f\in\mathcal F$ such that $$ f(x_i)>r_i \quad\text{if }i\in I,\qquad f(x_i)\le r_i \quad\text{if }i\notin I. $$ The pseudo-dimension of $\mathcal F$, denoted $\operatorname{Pdim}(\mathcal F)$, is the largest $m$ for which some $m$ pairs are pseudo-shattered. Equivalently, it is the VC dimension of the subgraph sets $\{(x,r):r<f(x)\}$, for $f\in\mathcal F$.

The thresholds $r_i$ can differ across inputs; they are part of the choice of points being tested. A labeling marks coordinate $i$ positive precisely when the function lies strictly above its threshold there. The use of strict $>$ on the positive side and $\le$ on the negative side fixes the boundary convention. In finite shattering arguments, equality on a negative coordinate can be removed by a small upward shift of all thresholds, as shown below.

Worked Examples: Threshold Functions

Worked Example: The Pseudo-Dimension of One-Dimensional Threshold Indicators

Consider $\mathcal F=\{f_a:a\in\mathbb R\}$, where $f_a(x)=\mathbf 1\{x\ge a\}$ for $x\in\mathbb R$. These functions take real values, namely zero and one. First, a single pair is pseudo-shattered: take $x_1=0$ and $r_1=1/2$. If $a\le0$, then $f_a(0)=1>1/2$; if $a>0$, then $f_a(0)=0\le1/2$. Both labels are possible.

Now take any $m$ pairs $(x_i,r_i)$. If $r_i\ge1$, coordinate $i$ is never positive, since $f_a(x_i)\le1$. If $r_i<0$, it is always positive, since $f_a(x_i)\ge0$. Every remaining coordinate has $0\le r_i<1$, and is positive exactly when $x_i\ge a$. As $a$ increases, each such coordinate can change from positive to negative at most once, and it cannot change back. Thus the label vectors occur in an ordered sequence with at most $m+1$ distinct patterns. For $m=2$, this is at most three patterns, fewer than the four needed to shatter two pairs. The same argument rules out shattering any $m\ge2$, since $m+1<2^m$. Therefore $\operatorname{Pdim}(\mathcal F)=1$.

Worked Example: Checking the Label Patterns on Three Inputs

Take the threshold indicator class above and the three pairs $(1,1/2),(2,1/2),(3,1/2)$, listed in increasing order of input. For $a\le1$, the label vector is $(1,1,1)$. For $1<a\le2$, it is $(0,1,1)$; for $2<a\le3$, it is $(0,0,1)$; and for $a>3$, it is $(0,0,0)$. There are only four possible vectors, and in particular not all eight binary patterns. This illustrates why a threshold parameter that moves monotonically through the inputs cannot independently set each label.

The upper-bound argument does not depend on the inputs being distinct or on the thresholds being equal. Some coordinates may be fixed by their $r_i$, and the others switch at different input locations, but a single moving threshold still produces at most $m+1$ patterns.

Linear Functions: Hyperplanes in Parameter Space

Let $\mathcal X\subseteq\mathbb R^d$ and consider the linear predictors $f_w(x)=w^\mathsf{T}x$, with parameter $w\in\mathbb R^d$. At a proposed pseudo-shattering pair $(x_i,r_i)$, the positive-label condition is $w^\mathsf{T}x_i>r_i$. In parameter space, the boundary between the two labels is the hyperplane $\{w:w^\mathsf{T}x_i=r_i\}$. Thus, as $w$ varies, the label vectors are controlled by the regions cut out by these hyperplanes.

Theorem: Suppose $\mathcal X\subseteq\mathbb R^d$, and let $r$ be the dimension of the linear span of $\mathcal X$. For the class $\mathcal F=\{x\mapsto w^\mathsf{T}x:w\in\mathbb R^d\}$, $$ \operatorname{Pdim}(\mathcal F)=r, $$ with the convention that the dimension is zero if $r=0$. The same result holds if the parameter set is a Euclidean ball $\{w:\|w\|_2\le B\}$ for any $B>0$. In particular, if the inputs span $\mathbb R^d$, the pseudo-dimension is $d$, even when the input domain is bounded.

We prove the upper bound by counting regions of hyperplane arrangements. The relevant geometric fact is that $m$ hyperplanes in a real affine space of dimension $r$ cut the space into at most $\sum_{j=0}^{r}\binom{m}{j}$ regions. To see this, let $R(m,r)$ be the maximum possible number of regions. With no hyperplanes, or in dimension zero, there is one region. When the $m$-th hyperplane is added, each new region must come from a region that the hyperplane intersects. The intersections are regions of the arrangement induced on that hyperplane by the first $m-1$ hyperplanes, an arrangement of dimension at most $r-1$. Consequently, $R(m,r)\le R(m-1,r)+R(m-1,r-1)$. Induction using Pascal’s identity gives the stated sum.

Proof of the theorem: First consider an arbitrary collection of $m$ pairs $(x_i,r_i)$ that is pseudo-shattered. For each of the finitely many binary labelings, choose one witnessing parameter $w$. If a coordinate is positive under a witness, its margin $w^\mathsf{T}x_i-r_i$ is strictly positive. There are finitely many such positive margins, so their minimum is positive. Choose $\delta>0$ smaller than that minimum and replace each threshold $r_i$ by $r_i+\delta$. Every positive label remains positive, while every negative label becomes strict because $w^\mathsf{T}x_i\le r_i<r_i+\delta$. Thus every labeling corresponds to a distinct region cut out by the hyperplanes $w^\mathsf{T}x_i=r_i+\delta$.

All these hyperplanes are constant along parameter directions orthogonal to the span of $\mathcal X$, so the arrangement has effective dimension $r$. If $m>r$, the region bound gives at most $\sum_{j=0}^{r}\binom{m}{j}<2^m$, so the $m$ pairs cannot be pseudo-shattered. Hence $\operatorname{Pdim}(\mathcal F)\le r$.

For the lower bound when $r>0$, choose linearly independent inputs $x_1,\ldots,x_r\in\mathcal X$. Their Gram matrix $G$, with entries $G_{ij}=x_i^\mathsf{T}x_j$, is invertible. For any sign vector $s\in\{-1,1\}^r$, solve $G c=\varepsilon s$ and set $w=\sum_{j=1}^r c_jx_j$. Then $w^\mathsf{T}x_i=\varepsilon s_i$ for every $i$. With thresholds $r_i=0$, this realizes each labeling. If $\|w\|_2\le B$ is required, there are only $2^r$ sign vectors; the corresponding solutions have norms proportional to $\varepsilon$. Choosing $\varepsilon>0$ small enough ensures every solution satisfies the bound. This proves the lower bound for both parameter sets. When $r=0$, every input is zero, so all functions have value zero and no pair can be pseudo-shattered. $\square$

Worked Example: Two-Dimensional Bounded Linear Predictors

Let $\mathcal X=\{x\in\mathbb R^2:\|x\|_2\le1\}$ and restrict parameters to $\|w\|_2\le1$. The inputs $x_1=(1,0)$ and $x_2=(0,1)$ are linearly independent. Use threshold zero at both inputs. For any desired signs $s_1,s_2\in\{-1,1\}$, choose $w=(s_1/2,s_2/2)$. Then $w^\mathsf{T}x_i=s_i/2$, and $\|w\|_2=\sqrt{1/4+1/4}=1/\sqrt2\le1$. The signs, and hence the two labels, are exactly as requested. So the class pseudo-shatters two pairs. Its inputs span $\mathbb R^2$, and the theorem’s upper bound is two; therefore its pseudo-dimension is exactly two.

Worked Example: Inputs on a Line Inside a Bounded Domain

Consider inputs $\mathcal X=\{(t,2t): -1\le t\le1\}$ and predictors $f_w(x)=w^\mathsf{T}x$, with $\|w\|_2\le1$. Every input lies in a one-dimensional linear subspace, so the input span has rank one. In fact, $f_w(t,2t)=(w_1+2w_2)t$, meaning that only one scalar combination of the two parameters affects the predictions. The theorem gives pseudo-dimension one.

To verify the lower bound directly, use $x_1=(1,2)$, threshold zero, and $w=(\varepsilon/5,2\varepsilon/5)$. Then $w^\mathsf{T}x_1=\varepsilon$; replacing $w$ by $-w$ gives $-\varepsilon$. For any $0<\varepsilon\le1$, both parameters have norm $\varepsilon/\sqrt5\le1$, so both labels are achieved. The rank-one upper bound rules out shattering two pairs.

What Boundedness Does—and Does Not—Change

For linear predictors, restricting the inputs to a bounded set does not by itself lower the pseudo-dimension. If the set still contains $d$ linearly independent vectors, their scale and location can support the lower-bound construction. Likewise, imposing any positive radius $B$ on a ball of coefficients does not change the dimension: the witnessing predictions can be made arbitrarily small while preserving their signs. If $B=0$, however, only the zero function remains, and its pseudo-dimension is zero.

The relevant restriction is the linear span of the available inputs. If the inputs lie in a proper subspace, parameter components orthogonal to that subspace have no effect. The rank calculation captures this loss exactly. This distinction is useful when assessing a model on a particular input domain: the number of named coefficients alone does not determine how many independent label patterns its predictions can produce there.

Common Mistake

A tempting but incorrect argument is: “There are $d$ linear coefficients, so the pseudo-dimension must be $d$, regardless of the input domain or coefficient constraint.” The coefficient count is only an upper-bound clue. If the inputs lie in a one-dimensional subspace of $\mathbb R^d$, predictions depend on only one effective direction, so the pseudo-dimension is one, not $d$. And if the coefficient set collapses to the single point $w=0$, the class has pseudo-dimension zero. Check the input span and the parameter set before claiming an exact dimension.

Key takeaway: To compute pseudo-dimension, write each subgraph label as an inequality. Threshold indicators produce nested label patterns; linear predictors produce hyperplane regions in parameter space. For linear predictors, the exact dimension is the rank of the input span, provided the allowed parameter set contains a neighborhood of zero.

Check Your Understanding

Use the label inequalities and geometric arguments from this tutorial.

For $f_a(x)=\mathbf 1\{x\le a\}$ on the real line, explain why varying $a$ cannot produce every binary labeling of two inputs.
Why can an equality on a negative-labeled pair be made strict by shifting all thresholds upward by a sufficiently small amount?
A linear predictor uses three coefficients, but every input lies in a two-dimensional linear subspace. What is its pseudo-dimension, assuming the coefficient set contains a neighborhood of zero?
Explain why a positive norm bound on $w$ does not prevent a linear class from shattering independent inputs at threshold zero.
What is the pseudo-dimension of the class containing only the zero function?