VC Dimension and Uniform Entropy Bounds
Threshold indicators on the real line are separated in the uniform norm, yet their empirical averages converge uniformly. A sample sees only finitely many membership patterns. VC dimension controls how many patterns a class can produce, and this combinatorial bound gives covering numbers uniformly over the sampling distribution.
Let \(X_1,\ldots,X_n\) be iid with law \(P\), write \(P_nf=n^{-1}\sum_i f(X_i)\) and \(\mathbb G_nf=\sqrt n(P_n-P)f\), and let \(\varepsilon_i\) be independent Rademacher signs independent of the sample. Assume the function classes below are pointwise measurable, so the suprema used in expectations are measurable; alternatively use the outer-expectation conventions of the empirical-process setup.
1. VC Dimension
For a class of sets \(\mathscr C\), its trace on a finite set \(I\) is \(\mathscr C|_I=\{C\cap I:C\in\mathscr C\}\). The set \(I\) is shattered when this trace is all of \(2^I\). The VC dimension \(d\) is the largest size of a shattered finite set, or infinity if these sizes are unbounded. For a nonempty class with \(d=0\), every point has the same membership in every member, so the class contains just one distinct set.
For half-lines, a sample of size \(n\) has at most \(n+1\) distinct traces. A finite-class estimate therefore gives an expected uniform error of order \(\sqrt{\log(n+1)/n}\). This already implies the uniform law, but chaining will remove the logarithm. The obstruction in the uniform norm remains: distinct half-lines have distance one, so their covering number is infinite for radii below one.
Lemma 1 (Sauer–Shelah). If \(d=\operatorname{VC}(\mathscr C)<\infty\), then for \(|I|=n\),
When \(1\le d\le n\), the sum is at most \((en/d)^d\). For \(d=0\) it equals one, and for \(d>n\) the bound is \(2^n\).
The combinatorial part is the following stronger observation. It counts shattered sets, rather than merely bounding their sizes.
Theorem 2 (Pajor). For a family \(\mathscr A\subseteq2^I\) on a finite ground set, let \(\operatorname{Sh}(\mathscr A)\) denote its collection of shattered subsets. Then \(|\operatorname{Sh}(\mathscr A)|\ge|\mathscr A|\).
Proof. Induct on \(|I|\), with the empty ground set immediate. Fix \(x\in I\), and let \(\mathscr A_+\) and \(\mathscr A_-\) be the traces on \(I\setminus\{x\}\) of members containing and not containing \(x\), respectively. A set shattered by either family is shattered by \(\mathscr A\). A set \(J\) shattered by both gives the additional shattered set \(J\cup\{x\}\). These two collections are disjoint, so
This proves Theorem 2. Applying it to the trace of \(\mathscr C\), whose shattered subsets have size at most \(d\), proves the first part of Lemma 1. For its second part set \(t=d/n\in(0,1]\); then
Dividing by \(t^d\) gives the claim. ◻
Identify each set with its indicator. Its squared \(L^2(P)\) distance to another set is the probability of their symmetric difference. The next theorem turns the trace bound into a distribution-free metric bound.
Theorem 3. There are universal constants \(C,c\) such that, for \(d\ge1\), every probability measure \(P\), and \(0<\delta<1\),
If \(d=0\), the covering number is one.
Lemma 4 (Extraction). Suppose \(N\ge2\), \(|f_i|\le1\), and \(\|f_i-f_j\|_{P,2}>\delta\) for \(i\ne j\), where \(0<\delta<1\). There are \(r\le C\delta^{-4}\log N\) points whose empirical measure \(P_r\) satisfies \(\|f_i-f_j\|_{P_r,2}>\delta/2\) for every pair.
Proof. Draw \(r=\lceil32\delta^{-4}\log N\rceil\) iid points. Each squared difference \(W=(f_i-f_j)^2\) lies in \([0,4]\) and has mean greater than \(\delta^2\). Hoeffding's inequality gives
Here the required bounded-variable inequality follows directly from exponential moments. For \(0\le W\le4\), the second derivative of \(\log\mathbb{E}e^{tW}\) is the variance under exponential tilting, at most \(4\); integrating twice gives \(\log\mathbb{E}e^{t(W-\mathbb{E}W)}\le2t^2\). Apply this to the independent copies and optimize the lower-tail Chernoff bound at deviation \(3\delta^2/4\).
The union bound over fewer than \(N^2/2\) pairs is strictly below one. Some sample therefore has all the required separations. ◻
Remark 5. The conclusion concerns the empirical measure \(P_r=r^{-1}\sum_{k=1}^r\delta_{x_k}\), and the radius decreases from \(\delta\) to \(\delta/2\). It is enough that the functions remain distinct on these points; preserving the original radius is unnecessary.
Proof of Theorem 3. Start with any finite \(\delta\)-separated family of size \(N\ge2\). Extraction produces \(r\le C\delta^{-4}\log N\) points on which its indicator traces are distinct. If \(r<d\), then \(N\le2^r\le2^d\). Otherwise Sauer–Shelah yields \(N\le(er/d)^d\). Writing \(y=(\log N)/d\), we obtain \(e^y\le C\delta^{-4}y\). Since \(y\le2e^{y/2}\), this implies \(y\le2\log(2C\delta^{-4})\). Thus every finite packing has size at most \((C/\delta)^{cd}\). A greedy packing must consequently terminate, and the resulting maximal packing is a cover. This also proves existence of a finite cover, without first assuming a maximal finite packing exists. See the covering–packing comparison. ◻
Theorem 6. A measurable VC class of indicators satisfies
With probability at least \(1-\eta\), this supremum is at most \(C\sqrt{(1\vee d)/n}+\sqrt{\log(1/\eta)/(2n)}\).
Proof. Symmetrize, add the zero function to anchor the process, and condition on the observations. For \(a_i=f(X_i)-g(X_i)\), independence of the signs and \(\cosh u\le e^{u^2/2}\) give directly
Thus the conditional increments are subgaussian in \(L^2(P_n)\). The elementary inequality for \(\cosh\) follows by integrating \((\log\cosh u)''=\operatorname{sech}^2u\le1\). This supplies the exact exponential-moment bound needed here; see also the Rademacher example. Adding the empty set raises VC dimension by at most one. Theorem 3 and Dudley's inequality give
Undo conditioning and divide by \(\sqrt n\). Changing one observation changes the original supremum by at most \(1/n\), so bounded differences proves the probability bound. In particular, Borel–Cantelli gives the uniform law almost surely. The \(1\vee d\) is needed: a single nonconstant indicator has dimension zero and can still fluctuate. ◻
Theorem 7. Equivalently, \(\mathbb{E}\|\mathbb G_n\|_{\mathcal F}\le C\sqrt{1\vee d}\). For half-lines \(d=1\), giving the \(n^{-1/2}\) expected uniform error for empirical distribution functions.
The conditioning in this proof is on the observations, not on the signs. The empirical metric is then fixed while the signs supply the subgaussian increments. This is the same reduction used in the uniform-entropy bound.
For real functions we use their subgraphs:
Theorem 8. Let \(\mathcal F\) be a nonempty VC-subgraph class with measurable envelope \(F\). For \(1\le r<\infty\), \(0<\|F\|_{P,r}<\infty\), and \(0<\delta<1\),
The constants are universal. If \(F=0\) almost surely, the covering number is one. This bound is deliberately stated with universal constants; it does not claim a sharp exponent.
Proof. First take \(r=1\) and use the probability measure
It satisfies \(\widetilde P(C_f\triangle C_g)=P|f-g|/(2PF)\). Apply Theorem 3 at radius \(\sqrt{\delta/2}\) to the subgraphs. This bounds the desired \(L^1(P)\) covering number by a power of \(1/\delta\).
For \(r>1\), let \(dQ=F^{r-1}dP/PF^{r-1}\). Since \(|f-g|\le2F\),
An \(L^1(Q)\) cover at relative radius \(\delta^r/2^{r-1}\) is therefore an \(L^r(P)\) cover at radius \(\delta\|F\|_{P,r}\). Applying the first part proves the stated exponent. Centers can be chosen in the class, after at most a factor two in radius. ◻
Remark 9. Theorem 8 bounds the normalized uniform entropy integral by \(C\sqrt{1\vee V}\). The bound is polynomial in inverse radius, with exponent proportional to dimension; it is not polynomial in dimension for fixed radius.
Example 10 (Oscillations). The class \(\{x\mapsto\sin(tx):t\in\mathbb R\}\) on \([0,1]\) has infinite VC-subgraph dimension. For any \(k\), set \(x_j=2^{j-k}\), \(1\le j\le k\). Given desired signs, choose bits \(b_j=0\) for positive and \(b_j=1\) for negative, and put
The fractional part of \(2^{j-1}u\) is in \((0,1/2)\) when \(b_j=0\), and in \((1/2,1)\) when \(b_j=1\). Hence \(\sin(tx_j)\) has exactly the prescribed nonzero sign. The points \((x_j,0)\) are shattered. A one-dimensional parameter can therefore generate arbitrarily complicated traces.
Lemma 11 (Convex hulls). Let \(\operatorname{conv}(\mathcal F)\) consist of finite convex combinations of members of \(\mathcal F\). For every linear functional \(L\) defined on their span,
Indeed, \(|L\sum_i a_if_i|\le\sum_i a_i|Lf_i|\) for \(a_i\ge0\), \(\sum_i a_i=1\), and the reverse inequality follows from inclusion. Taking \(L=P_n-P\) transfers the uniform law, with the same error, to the convex hull.
Corollary 12. A pointwise measurable VC-subgraph class with integrable envelope is Glivenko–Cantelli.
Proof. For each integer \(M\), the class \(f\mathbf1\{F\le M\}\) remains VC-subgraph: outside the truncation set, all subgraphs have fixed membership. Its envelope is bounded, and Theorem 8, symmetrization, and chaining give expected uniform error tending to zero. Bounded differences and Borel–Cantelli give almost-sure convergence for each \(M\). The remaining error is at most \(P_n(F\mathbf1\{F>M\})+P(F\mathbf1\{F>M\})\). The strong law and then \(M\to\infty\) make this vanish. ◻
A variance bound can improve the global estimate for a bounded class. The next result makes the centering and the entropy hypothesis explicit.
Theorem 13. Suppose \(Pf=0\), \(|f|\le U\), and \(\sup_f Pf^2\le\sigma^2\le U^2\), where \(0<\sigma\le U\). Assume, uniformly over probability measures \(Q\),
Then, with a universal constant,
A bounded VC-subgraph class satisfies the entropy hypothesis with \(v=C(1\vee V)\) and universal \(A\). For an uncentered class apply the result to \(f-Pf\), whose envelope is at most twice the original envelope.
Proof. Scale to \(U=1\). Set \(R=\mathbb{E}\sup_f|n^{-1/2}\sum_i\varepsilon_i f(X_i)|\), \(D_n=\sup_f P_nf^2\), and \(D=\mathbb{E}D_n\). Conditional chaining, followed by concavity of \(x\mapsto\sqrt{x\log(A/\sqrt x)}\) on \([0,1]\), gives
At zero the expression is interpreted by continuity. Symmetrization and contraction for the map \(x\mapsto x^2\), which is 2-Lipschitz on \([-1,1]\), give \(D\le\sigma^2+CR/\sqrt n\). If \(D\le\sigma^2\), monotonicity gives \(R\le C\sigma\sqrt{vL}\), where \(L=\log(A/\sigma)\). If \(D>\sigma^2\), then \(\log(A/\sqrt D)\le L\), so
Solving this quadratic yields \(R\le C[\sigma\sqrt{vL}+vL/\sqrt n]\). Symmetrization and rescaling finish the proof. For centering, cover the original class in \(L^2((Q+P)/2)\); the triangle inequality and Cauchy–Schwarz show that the same centers, after centering, cover in \(L^2(Q)\) with radius enlarged by at most \(2\sqrt2\). Thus centering preserves the required polynomial entropy bound. ◻
Here are the analytic steps in the local bound. For \(0<c\le1\), substitute \(u=cv\) and use \(\sqrt{a+b}\le\sqrt a+\sqrt b\) to obtain
The last integral is \(\Gamma(3/2)\), by \(v=e^{-t}\). If \(q(x)=x\log(A/\sqrt x)\), then \(q'(x)=\log(A/\sqrt x)-1/2>0\) and \(q''(x)=-1/(2x)<0\) on \((0,1]\). Composing its nonnegative concave extension with the increasing concave square root proves the Jensen step. More explicitly, symmetrization and contraction give
Finally, an inequality \(R^2\le a+bR\), with \(a,b\ge0\), implies \(R\le(b+\sqrt{b^2+4a})/2\le b+\sqrt a\). This gives both terms of Theorem 13, including the regime in which the second term dominates. The contraction inequality and its coordinate-by-coordinate proof are given in the preceding maximal-inequalities note.
Example 14 (Polynomials). The real polynomials of degree at most \(m\) form a VC-subgraph class of dimension \(m+1\). Lagrange interpolation shatters \(m+1\) distinct points \((x_i,0)\). To prove the upper bound, take \(m+2\) arbitrary subgraph points \((x_i,y_i)\) and a nonzero vector \(a\) satisfying \(\sum_i a_i(1,x_i,\ldots,x_i^m)=0\). Then every polynomial satisfies
Because \(\sum_i a_i=0\), there are both positive and negative coefficients. Labeling \(p(x_i)>y_i\) exactly at the positive coefficients forces the left side to be positive; reversing these labels forces it to be negative. At least one of these two patterns contradicts the fixed value \(c\). Thus \(m+2\) points cannot be shattered. This argument also handles equalities at the subgraph boundary.
For the quadratic example, an envelope restriction is essential. Suppose \(P\) is supported on \([-1,1]\) and \(\mathcal Q\) consists of quadratics satisfying \(\sup_{[-1,1]}|p|\le1\). Theorem 8 and conditional chaining give, for every sample,
The squared class is contained in the degree-four polynomials and has envelope one. Applying the same argument and bounded differences to it shows that, with probability at least \(1-\eta\),
Here we used \(|\sqrt a-\sqrt b|^2\le|a-b|\). This provides the coarse \(n^{-1/4}\) norm-comparison scale directly. The localized fixed-point method can be used when finer dependence on a local radius is needed. Neither argument applies to all unbounded-coefficient quadratics with a fixed envelope.