VC Dimension

Let $\mathcal{H}$ be a hypothesis class of functions $h: \mathcal{X} \to \{0, 1\}$, mapping inputs to binary labels. Given a finite set of points $S = \{x_1, \dots, x_n\} \subset \mathcal{X}$, the restriction of $\mathcal{H}$ to $S$, written $\mathcal{H}|_S$, is the set of all labeling vectors $(h(x_1), \dots, h(x_n)) \in \{0,1\}^n$ achievable by some $h \in \mathcal{H}$. There are $2^n$ possible labelings of $n$ points in total. We say $\mathcal{H}$ shatters $S$ if $\mathcal{H}|_S$ equals the full set $\{0,1\}^n$ — every conceivable labeling of the $n$ points is realized by some hypothesis in the class. The VC dimension of $\mathcal{H}$, denoted $\mathrm{VCdim}(\mathcal{H})$, is the largest integer $d$ such that some set of $d$ points is shattered by $\mathcal{H}$. If arbitrarily large finite sets can be shattered, $\mathrm{VCdim}(\mathcal{H}) = \infty$. Two subtleties matter here. First, VC dimension asks only whether some set of size $d$ is shattered — it does not require every set of that size to be shattered. Second, it is a property of the hypothesis class, not of any particular dataset: it measures worst-case expressive power over all possible point configurations and all possible labelings. VC dimension formalizes "capacity" in a way that survives infinite hypothesis classes. Counting $|\mathcal{H}|$ fails when $\mathcal{H}$ is uncountable (e.g., all hyperplanes in $\mathbb{R}^d$), but VC dimension is typically small and finite even then. This is the bridge to PAC Learning: the finite-hypothesis-class sample complexity bound $O\!\left(\frac{\log |\mathcal{H}| + \log(1/\delta)}{\epsilon}\right)$ generalizes to infinite classes by replacing $\log|\mathcal{H}|$ with a term governed by VC dimension, via the Sauer–Shelah lemma, which bounds $|\mathcal{H}|_S|$ polynomially in $n$ whenever $\mathrm{VCdim}(\mathcal{H})$ is finite.

Computing or bounding the VC dimension of a hypothesis class follows a standard two-sided proof strategy, and this same strategy is what the "mechanism" of VC theory consists of — there is no numeric algorithm that computes VC dimension in general (it can be shown NP-hard to compute for many classes), but there is a completely systematic proof pattern. To show $\mathrm{VCdim}(\mathcal{H}) = d$, you must establish two separate facts: 1. Lower bound: Exhibit one specific set of $d$ points and show $\mathcal{H}$ shatters it — i.e., for each of the $2^d$ labelings, produce a hypothesis in $\mathcal{H}$ realizing it. 2. Upper bound: Show that no set of $d+1$ points can be shattered — i.e., for every possible configuration of $d+1$ points, exhibit at least one labeling that no $h \in \mathcal{H}$ can realize. The lower bound is a constructive existence proof (find one witness set). The upper bound is a universal claim over all configurations (rule out every possible witness), which is usually the harder direction and often requires a geometric or combinatorial argument rather than brute-force enumeration. ``` FUNCTION VerifyVCDimensionIsAtLeast(H, S): // S is a candidate set of points, |S| = n FOR each labeling y in {0,1}^n: found = FALSE FOR each hypothesis h in H: // conceptually; H may be infinite IF (h(x_1),...,h(x_n)) == y: found = TRUE BREAK IF NOT found: RETURN FALSE // S is not shattered RETURN TRUE // S is shattered FUNCTION UpperBoundVCDimension(H, d_plus_1): // Prove: for ALL sets S' of size d+1, S' is not shattered. // This is a universally-quantified geometric argument, not enumeration, // when the domain is infinite (e.g. R^d). Enumeration is only literal // when X itself is finite and small. FOR each set S' of size d_plus_1 drawn from X: IF VerifyVCDimensionIsAtLeast(H, S') == TRUE: RETURN "upper bound FAILS, try larger d" RETURN "no set of size d+1 is shattered — VCdim <= d" ``` Once the VC dimension $d$ is established, it plugs directly into the Sauer–Shelah lemma, the combinatorial engine behind the generalization bound:

This says that even though $\mathcal{H}$ may contain infinitely many hypotheses, the number of distinguishable behaviors on any fixed $n$ points grows only polynomially in $n$ (with degree equal to the VC dimension), not exponentially. This polynomial "effective size" is what substitutes for $|\mathcal{H}|$ in PAC-style generalization bounds.

The reasoning made visible: three points in "general position" (not collinear) can always be shattered by lines in the plane, giving all 8 labelings — this witnesses $\mathrm{VCdim} \ge 3$. But every configuration of four points admits a labeling (the diagonal / XOR pattern shown) that no line can realize, whether the four points are in convex position or one lies inside the triangle of the others — this establishes $\mathrm{VCdim} \le 3$, so $\mathrm{VCdim}(\text{linear classifiers in } \mathbb{R}^2) = 3 = 2+1$.

Why the upper-bound direction is genuinely a proof, not a search. Because $\mathcal{X}$ is often infinite (e.g. $\mathbb{R}^d$), "check every set of $d+1$ points" cannot literally be enumerated; it must be established by a geometric argument valid for all configurations simultaneously. For linear classifiers in $\mathbb{R}^d$, this argument is Radon's theorem: any set of $d+2$ points in $\mathbb{R}^d$ can be partitioned into two disjoint subsets whose convex hulls intersect. If a hyperplane could separate one subset from the other, its convex hulls could not intersect — contradiction. Hence no $d+2$ points can be shattered by hyperplanes, giving $\mathrm{VCdim} \le d+1$. Combined with the constructive lower bound (place $d+1$ points such that one is the origin and the rest form a linearly independent basis; any labeling is realizable by choosing hyperplane coefficients via the linear independence), this yields the exact value $\mathrm{VCdim}(\text{halfspaces in } \mathbb{R}^d) = d + 1$.

The Sauer–Shelah lemma, proof sketch. Let $d = \mathrm{VCdim}(\mathcal{H})$. Define $\tau_{\mathcal{H}}(n) = \max_{|S|=n} |\mathcal{H}|_S|$, the maximum number of distinct labelings induced on any $n$ points. The claim is

The proof proceeds by induction on $n + d$, using a shifting/compression argument: for a fixed point $x$, split the labelings realized on $S$ into those extendable both ways on $x$ and those extendable only one way, relating $\mathcal{H}|_S$ to restrictions on $S \setminus \{x\}$ under two smaller hypothesis classes, one of VC dimension at most $d$ and one of VC dimension at most $d - 1$. Summing recursively yields the binomial-sum bound. The key consequence: for $n \gg d$, $\tau_{\mathcal{H}}(n) = O(n^d)$ — polynomial, not exponential ($2^n$).

From polynomial growth to a generalization bound. The PAC framework bounds the probability that empirical risk $\hat{R}(h)$ and true risk $R(h)$ diverge, uniformly over $h \in \mathcal{H}$, using a union bound over the effective number of hypotheses realizable on the sample — that is $\tau_{\mathcal{H}}(2n) = O(n^d)$ rather than $|\mathcal{H}|$. Combining a symmetrization argument (comparing training risk to risk on a fresh "ghost" sample) with a Chernoff-type concentration bound over the $O(n^d)$ effective labelings gives, with probability at least $1 - \delta$ over a sample of size $n$, for all $h \in \mathcal{H}$:

Equivalently, to guarantee $|R(h) - \hat{R}(h)| \le \epsilon$ for all $h$ with probability $1-\delta$, a sample size of

suffices (this is the agnostic PAC form; for the realizable case where some $h^\star \in \mathcal{H}$ achieves zero true risk, the dependence improves to $O\!\left(\frac{d\log(1/\epsilon) + \log(1/\delta)}{\epsilon}\right)$). This is the precise link foreshadowed at the start: finite VC dimension is both necessary and sufficient for (agnostic) PAC-learnability, and the sample complexity scales linearly in VC dimension, not in the number of parameters or the cardinality of $\mathcal{H}$.

Tradeoffs, stated honestly.

• The bound is distribution-free — it holds for every data distribution, which is its strength and its weakness: it is often loose in practice because real data is far from worst-case.
• VC dimension can be larger than the number of free parameters (though for many parametric families, such as linear classifiers, it coincides with parameter count plus one) and in some pathological infinite-parameter families (e.g. certain neural network activation constructions) the VC dimension is finite while a naive parameter count would suggest otherwise, or vice versa.
• VC dimension says nothing about which algorithm is used to select $h$ from $\mathcal{H}$; it bounds the worst case over the whole class, so it upper-bounds the generalization gap for whatever hypothesis empirical risk minimization outputs, but it does not certify that ERM is computationally tractable.
• A class with infinite VC dimension is not PAC-learnable in the distribution-free sense at all — no sample size, however large, gives a uniform guarantee. This is not merely "needs more data"; it is a hard impossibility, previewing the flavor of the No-Free-Lunch Theorem.

Consider $\mathcal{H}$ = axis-aligned rectangles in $\mathbb{R}^2$: each $h_{[a,b]\times[c,d]}(x,y) = 1$ iff $a \le x \le b$ and $c \le y \le d$. We compute $\mathrm{VCdim}(\mathcal{H})$ exactly.

Step 1 — lower bound: exhibit 4 points that are shattered. Place points in a diamond configuration:

For any subset $T \subseteq \{N,S,E,W\}$ we must find a rectangle containing exactly the points in $T$ and excluding the rest. Since each point is the unique extremizer of $x$ or $y$ among the four, a rectangle can always be shrunk just enough to include any chosen subset while excluding the others — e.g. to realize $T = \{N, E\}$, take the rectangle $[0.5, 1.5] \times [0.5, 1.5]$: it contains $E=(1,0)$? Check carefully — we need a general constructive rule, so instead take the tight bounding box of exactly the points in $T$, expanded by $\epsilon < 0.5$ in every direction. Because each of $N,S,E,W$ sits at a distinct extreme coordinate, this expanded box never accidentally captures an excluded point. All $2^4 = 16$ labelings are realizable this way. So $\mathrm{VCdim}(\mathcal{H}) \ge 4$.

Step 2 — upper bound: no 5 points can be shattered. Take any 5 points $P_1, \dots, P_5$ in the plane. Let $x_{\min}, x_{\max}$ be the extreme $x$-coordinates among the five and $y_{\min}, y_{\max}$ the extreme $y$-coordinates; let $P^\star$ be a point achieving none of these four extremes if it exists, or more carefully: among any 5 points at most 4 distinct extremal roles ($x_{\min}$-achiever, $x_{\max}$-achiever, $y_{\min}$-achiever, $y_{\max}$-achiever) can be assigned, so by pigeonhole at least one point $P^\star$ is not the unique extremizer in any direction — its coordinates lie within the ranges set by the other four. Consider the labeling: all points except $P^\star$ are labeled positive, and $P^\star$ is labeled negative. Any rectangle containing the four extremal points must contain their full bounding box $[x_{\min}, x_{\max}] \times [y_{\min}, y_{\max}]$, and since $P^\star$'s coordinates lie inside this range, $P^\star$ is forced inside too. This labeling cannot be realized. So no 5-point set is shattered, giving $\mathrm{VCdim}(\mathcal{H}) \le 4$.

Conclusion: $\mathrm{VCdim}(\text{axis-aligned rectangles}) = 4$.

Second trace — plugging into the sample complexity formula. Suppose we want, with confidence $\delta = 0.05$, an accuracy gap $\epsilon = 0.1$ using this rectangle hypothesis class ($d=4$) in the realizable setting:

So on the order of a couple hundred labeled points already gives a meaningful guarantee — far fewer than would be needed for a hypothesis class with unbounded (infinite) VC dimension, for which no finite $n$ would suffice at all under a distribution-free guarantee.

Support vector machines, historically Vapnik's signature contribution, rely on VC-theoretic reasoning to justify margin-based generalization bounds: maximizing the margin effectively controls an effective VC dimension even in high-dimensional feature spaces, explaining why SVMs generalize well despite operating in spaces where naive dimension counting would predict overfitting. Model selection procedures such as Structural Risk Minimization directly use VC dimension to penalize hypothesis classes of higher capacity, choosing among nested classes of increasing complexity by trading off empirical fit against a VC-based complexity term. Decision tree depth limits, the choice of polynomial degree in regression, and early stopping heuristics in neural network training are all informally justified by the same capacity-versus-data intuition that VC dimension makes precise. In theoretical computer science, VC dimension appears well beyond learning theory: it underlies bounds in computational geometry (epsilon-nets, range searching), discrepancy theory, and even database query optimization, wherever one needs to bound how many distinct "behaviors" a structured family of sets can exhibit on a finite point set. Modern deep learning complicates this picture — networks with vastly more parameters than training examples still generalize, motivating alternative capacity measures (Rademacher complexity, margin-based bounds, norm-based bounds) that refine or replace raw VC dimension while keeping its core philosophy: generalization is governed by effective expressive power, not raw parameter count.

Ask the tutor: How does VC dimension change when combining hypothesis classes, e.g. taking unions or intersections of two classes with known VC dimensions?