Vapnik–Chervonenkis theory turns a combinatorial restriction on possible labelings into a distribution-free entropy bound. It is especially powerful because it is invariant under the unknown sampling law and survives many Boolean and monotone operations.
Traces and shattering
Definition. Let \(\mathcal C\) be a class of subsets of \(\mathcal X\). Its trace on \(S=\{x_1,\ldots,x_n\}\) is \[ \mathcal C|_S=\{C\cap S:C\in\mathcal C\}. \] The growth function is \[ \Pi_{\mathcal C}(n) =\sup_{|S|=n}|\mathcal C|_S|. \] The class shatters \(S\) if \(\mathcal C|_S=2^S\). Its VC dimension \(V(\mathcal C)\) is the largest cardinality of a shattered finite set, with value \(\infty\) if no finite bound exists.
Example. The lower half-lines \((-\infty,t]\) shatter one point but cannot shatter two ordered points, so their VC dimension is \(1\). All intervals \([a,b]\) shatter any two points but not three: the labeling that keeps the two outer points and excludes the middle one is impossible. Thus their VC dimension is \(2\).
The Sauer–Shelah lemma
Theorem (Sauer–Shelah). If \(V(\mathcal C)=V<\infty\), then for every \(n\), \[ \Pi_{\mathcal C}(n) \leq \sum_{j=0}^{V}\binom nj. \] In particular, for \(n\geq V\), \[ \Pi_{\mathcal C}(n)\leq \left(\frac{en}{V}\right)^V. \]
Proof. Write \(m(n,V)\) for the largest trace cardinality among classes of VC dimension at most \(V\). Fix a point \(x_n\). Separate traces on \(n\) points according to their restrictions on the first \(n-1\) points. Restrictions that occur with both choices for membership of \(x_n\) form a class of VC dimension at most \(V-1\); otherwise that class together with \(x_n\) would shatter \(V+1\) points. All restrictions form a class of dimension at most \(V\). Hence \[ m(n,V)\leq m(n-1,V)+m(n-1,V-1). \] With \(m(n,0)=1\) and \(m(0,V)=1\), Pascal's identity and induction give \(m(n,V)\leq\sum_{j=0}^V\binom nj\). Finally, \[ \sum_{j=0}^V\binom nj \leq \inf_{t>0}t^{-V}(1+t)^n \leq(en/V)^V \] by choosing \(t=V/(n-V)\), with the endpoint cases handled directly. \(\square\)
The change from \(2^n\) to \(n^V\) is decisive. After taking a logarithm, the apparent exponential size of a set class becomes only \(V\log n\).
From growth to metric entropy
Theorem (VC entropy bound). If \(\mathcal C\) has VC dimension \(V<\infty\), then universal constants \(A,c>0\) exist such that, for every probability measure \(Q\) and \(0<\varepsilon<1\), \[ N\!\left(\varepsilon,\{1_C:C\in\mathcal C\},L_2(Q)\right) \leq A\left(\frac{A}{\varepsilon}\right)^{cV}. \] Equivalently, \[ \sup_Q\log N(\varepsilon,\mathcal C,L_2(Q)) \lesssim V\log(A/\varepsilon). \]
The proof samples a finite approximation from \(Q\), uses the Sauer–Shelah bound on its possible traces, and shows that sets separated in \(L_1(Q)\) remain distinguishable on that sample. The resulting polynomial exponent can be sharpened, but its precise universal constant is rarely important in empirical-process applications.
Corollary. A measurable VC class of sets is \(P\)-Glivenko–Cantelli and \(P\)-Donsker for every \(P\). Indeed, \[ \int_0^1\sqrt{V\log(A/\varepsilon)}\,\mathrm{d}\varepsilon<\infty. \]
VC-subgraph classes
Definition. The subgraph of a real-valued function \(f\) is \[ \operatorname{subgraph}(f) =\{(x,t)\in\mathcal X\times\mathbb R:t<f(x)\}. \] A function class \(\mathcal F\) is VC-subgraph if \(\{\operatorname{subgraph}(f):f\in\mathcal F\}\) is a VC class of sets.
Theorem. Let \(\mathcal F\) be VC-subgraph with dimension \(V\) and envelope \(F\). For every probability measure \(Q\) with \(\|F\|_{Q,2}>0\), \[ N\!\left( \varepsilon\|F\|_{Q,2}, \mathcal F,L_2(Q) \right) \leq A\left(\frac{A}{\varepsilon}\right)^{cV}, \qquad 0<\varepsilon<1, \] for universal constants \(A,c\). If \(PF^2<\infty\) and measurability is controlled, \(\mathcal F\) is \(P\)-Donsker.
Geometric examples
Proposition. The following dimensions are exact:
- affine halfspaces in \(\mathbb R^d\): \(d+1\);
- Euclidean balls in \(\mathbb R^d\): \(d+1\);
- axis-parallel rectangles in \(\mathbb R^d\): \(2d\);
- linear threshold functions \(1\{w^\top x>0\}\) on \(\mathbb R^d\): \(d\).
Example (finite-dimensional linear spaces). If \(g_1,\ldots,g_d\) are fixed functions, then \[ \mathcal F=\left\{\sum_{j=1}^d\theta_jg_j:\theta\in\mathbb R^d\right\} \] is VC-subgraph with dimension at most \(d+2\). Indeed, deciding whether \(t<f_\theta(x)\) is a linear threshold decision in the vector \((g_1(x),\ldots,g_d(x),t)\). Generalized linear models with a monotone link inherit the same finite-dimensional combinatorial structure.
Permanence under operations
Proposition. Finite VC dimension is preserved under complements, inverse images, finite unions and intersections, and monotone transformations. More precisely, if \(\mathcal C_1,\ldots,\mathcal C_k\) have finite VC dimensions, then \[ \left\{\bigcup_{j=1}^k C_j:C_j\in\mathcal C_j\right\}, \qquad \left\{\bigcap_{j=1}^k C_j:C_j\in\mathcal C_j\right\} \] have finite VC dimension, with bounds depending only on \(k\) and the original dimensions.
VC theory should be checked whenever a class is generated by finitely many inequalities, thresholds, order restrictions, or Boolean operations. It often supplies both the uniform law and the central limit theorem without any distribution-specific calculation.