VC Entropy Integrals and Rademacher Bounds

Why Covering Numbers Enter Rademacher Bounds

A class can contain many functions and still have modest statistical complexity if, at the observed sample, its functions are close to one another. Covering numbers quantify how many distinct approximations are needed at each resolution. A Dudley entropy integral adds the contributions across resolutions: coarse scales cost little, while fine scales matter only to the extent that many distinguishable functions remain.

Here the metric is computed on the observed sample. This makes the resulting bound conditional on the data and connects the entropy calculation directly to empirical Rademacher complexity. For a uniformly bounded VC-subgraph class, a uniform covering-number envelope makes the integral finite and gives the familiar square-root dependence on dimension and sample size.

The Dudley Entropy Integral

For each fixed \(f\), the signed sum in the definition has mean zero. Its increments across functions are controlled by the empirical distance: for every real \(\lambda\), $$ E_\sigma\exp\left\{\lambda\left[\frac{1}{n}\sum_{i=1}^n\sigma_i(f(X_i)-g(X_i))\right]\right\} \leq \exp\left(\frac{\lambda^2 d_S(f,g)^2}{2n}\right). $$ This follows by independence and \(\cosh(u)\leq \exp(u^2/2)\). Thus close functions have small random increments, and a sequence of increasingly fine covers can control the supremum.

Here is the chaining argument for this constant. If \(D=0\), all functions have the same sample vector, so the expected supremum is zero. Otherwise, let \(\epsilon_k=D2^{-k}\) for \(k=0,1,\ldots\). Choose a finite \(\epsilon_k\)-cover \(T_k\) of \(\mathcal F\), with centers in the class. At \(k=0\), one center suffices because the diameter is \(D\). For each \(f\), choose an approximant \(\pi_k(f)\in T_k\) within \(\epsilon_k\) of \(f\). Then $$ d_S(\pi_k(f),\pi_{k-1}(f))\leq \epsilon_k+\epsilon_{k-1}=3\epsilon_k. $$ The signed process converges along these approximants to its value at \(f\), since its sample-vector linear functional is continuous in \(d_S\).

Write \(Z_f=n^{-1}\sum_i\sigma_i f(X_i)\). The expected maximum of \(M\) mean-zero variables whose moment generating functions are bounded by \(\exp(\lambda^2s^2/2)\) is at most \(s\sqrt{2\log M}\). This follows by bounding the exponential of the maximum by the sum of the \(M\) exponentials, taking logarithms and expectations, and minimizing over \(\lambda>0\). For the increments \(Z_{\pi_k(f)}-Z_{\pi_{k-1}(f)}\), the increment scale is at most \(3\epsilon_k/\sqrt n\), and there are at most \(|T_k||T_{k-1}|\) possible pairs. With \(H(\epsilon)=\log N(\epsilon,\mathcal F,d_S)\), monotonicity of covering numbers gives $$ E_\sigma\sup_f\left(Z_{\pi_k(f)}-Z_{\pi_{k-1}(f)}\right) \leq \frac{6\epsilon_k}{\sqrt n}\sqrt{H(\epsilon_k)}. $$ The initial center has expected process value zero. Summing the increments, and using that \(H(u)\geq H(\epsilon_k)\) for \(\epsilon_k/2\leq u\leq\epsilon_k\), yields $$ \sum_{k\geq1}\epsilon_k\sqrt{H(\epsilon_k)} \leq 2\int_0^D\sqrt{H(u)}\,du. $$ Combining these inequalities proves the theorem. Boundedness and separability ensure the approximating process converges to the supremum; finiteness of the integral justifies the sum. \(\square\)

From VC-Subgraph Entropy to a Complexity Rate

For a real-valued function \(f\), its subgraph is the set of pairs \((x,t)\) satisfying \(t<f(x)\). The VC-subgraph dimension of \(\mathcal F\) is the VC dimension of the family of these sets. The standard uniform VC entropy bound says that a class of sets with VC dimension \(V\) has covering numbers bounded by a power of the reciprocal scale, uniformly over probability measures. For bounded functions, the subgraph representation transfers this control to function covers.

The entropy premise is a standard consequence of the VC-subgraph covering bound. To see why its scale has this form, for functions in \([0,1]\) associate to \(f\) the indicator of its subgraph restricted to \(0\leq t\leq1\). Under \(Q\) on \(x\) and an independent uniform \(t\) on \([0,1]\), the \(L_1\) distance between these indicators is \(E_Q|f-g|\). Since \(|f-g|^2\leq|f-g|\), an \(L_1\) cover at radius \(\epsilon^2\) gives an \(L_2\) cover at radius \(\epsilon\). The uniform VC set entropy bound therefore gives an \(L_2\) covering bound with exponent \(2V\), absorbing fixed constants into \(A\).

To derive the displayed rate, \(d_S\) has diameter at most \(1\), because all sample values lie in \([0,1]\). The uniform covering premise applies to the empirical measure on the observed sample, so $$ \log N(\epsilon,\mathcal F,d_S) \leq 2V\log(A/\epsilon). $$ Substitute this envelope in Dudley’s theorem and use \(\sqrt{a+b}\leq\sqrt a+\sqrt b\): $$ \int_0^1\sqrt{2V\log(A/\epsilon)}\,d\epsilon \leq \sqrt{2V}\left(\sqrt{\log A}+\int_0^1\sqrt{\log(1/\epsilon)}\,d\epsilon\right). $$ With \(u=\sqrt{\log(1/\epsilon)}\), the last integral is \(2\int_0^\infty u^2e^{-u^2}\,du=\sqrt{\pi}/2\). Thus the right side is \(\sqrt V(\sqrt{2\log A}+\sqrt{\pi/2})\); equivalently, retaining the sharper separation before multiplying constants gives the stated bound. More directly, \(\sqrt{2V\log(A/\epsilon)}\leq\sqrt{2V\log A}+\sqrt{2V\log(1/\epsilon)}\), which leads to \(12\sqrt V(\sqrt{2\log A}+\sqrt{\pi/2})/\sqrt n\). We use this latter, directly justified expression as the bound: $$ \widehat{\mathfrak R}_S(\mathcal F) \leq \frac{12\sqrt V}{\sqrt n} \left(\sqrt{2\log A}+\sqrt{\frac{\pi}{2}}\right). $$

The VC dimension enters as \(\sqrt V\), and the sample size as \(1/\sqrt n\). These are rate statements; the universal constants can make the numerical bound loose. If functions instead take values in \([-B,B]\), an affine rescaling to \([0,1]\) gives the corresponding bound multiplied by \(2B\). The additive constant introduced by the rescaling has zero expected Rademacher contribution.

Common Pitfall: Confusing Entropy and Its Square Root

The integrand in Dudley’s bound is \(\sqrt{\log N(\epsilon)}\), not \(\log N(\epsilon)\). Integrating the entropy itself and then treating that value as the Dudley integral changes the bound. Cauchy–Schwarz can convert an integrated entropy into an upper bound on the Dudley integral, as in the numerical example, but the square root and the interval length must be handled explicitly. Another frequent error is to use a covering number from a population metric without checking that it controls the empirical metric; the uniform-in-\(Q\) VC entropy premise permits the empirical measure, whereas a bound for only one fixed distribution may not.

The entropy integral is useful because it records how complexity varies with resolution rather than treating the class as simply finite or infinite. A class may have a large fine-scale cover but still have a manageable integral if those scales occupy a short interval. Conversely, a coarse covering estimate alone can miss the accumulation of complexity across finer scales. Uniform VC-subgraph entropy supplies a convenient envelope that makes this accumulation explicit and yields a distribution-free complexity rate.