Entropy and VC Conditions for the Donsker Property: Maximal Inequalities

Intuition Beginner

The previous unit promised that for a well-behaved menu of questions the magnified estimation error settles into one universal Gaussian wiggle, and it gave the test for "well-behaved": the magnified error must not jump around wildly when you move between two nearly identical questions. That test is hard to check directly. This unit gives a recipe you can actually run: measure how big the menu is, and if it is small enough, the test passes automatically.

How do you measure the size of a menu of questions? Count how many small patches you need to tile it. Imagine every question is a point, and two questions sit close together when they give almost the same answers on the data. Cover all the questions with little patches of a chosen width. The number of patches needed is the menu's size at that width. Shrink the width and you need more patches; the rate at which the count grows is what matters.

The key quantity adds up these counts across all widths, with a square root softening the count at each width. If that running total is finite, the menu is small enough and the magnified error stays tame: nearby questions give nearby answers, the wiggle is continuous, and the universal Gaussian limit kicks in. This adding-up is called chaining, because it walks from coarse patches to fine ones in a chain of small steps, controlling the error one link at a time.

The one-sentence takeaway: count the patches needed to tile your menu of questions at every width, add up the softened counts, and if the total is finite the magnified error converges to the universal Gaussian limit.

Visual Beginner

Picture a class of curves you might fit to data. To measure how rich the class is, drop a grid of representative curves so that every curve in the class is within a small distance of some representative. The number of representatives needed, at a chosen tolerance, is the covering count. A second way to measure size is bracketing: trap every curve between a low curve and a high curve that are close together, and count how many such low-high cages you need.

Tolerance width	Covering count (patches to tile the menu)	Softened count (square root of its logarithm)
Wide	Few patches	Small
Medium	More patches	Moderate
Narrow	Many patches	Larger, but grows slowly for a tame menu
Shrinking to zero	Count grows without bound	Sum stays finite if the menu is tame

The number to watch is the running total of softened patch counts as the width shrinks to zero. For a tame menu the patch count grows, but slowly enough that the softened total levels off at a finite height. That finite height is the budget that controls the worst wiggle of the magnified error. A special kind of tame menu is a VC class, where a simple counting rule caps how complicated the menu can be, and the patch count is guaranteed to grow only like a power of one over the width.

Worked example Beginner

We compute the patch count and the softened running total for a simple menu, and check the total is finite. Take the menu of step functions on the line of the form "jump from low to high at a threshold," indexed by where the threshold sits. Suppose distances are measured so the whole menu fits inside a span of width $1$, and the patch count at width $w$ is about $1/w$ patches — halving the width doubles the patches.

Step 1. List patch counts at shrinking widths. At width $1/2$, about $2$ patches. At width $1/4$, about $4$ patches. At width $1/8$, about $8$ patches. At width $1/16$, about $16$ patches. Each halving of width doubles the count, so the count at width $w$ is about $1/w$.

Step 2. Soften each count. The softening is the square root of the natural logarithm of the count. At width $1/2$ the count is $2$, log is about $0.69$, square root about $0.83$. At width $1/4$ the count is $4$, log about $1.39$, square root about $1.18$. At width $1/8$ the count is $8$, log about $2.08$, square root about $1.44$.

Step 3. Form the running total weighted by width steps. Each width band from $w/2$ to $w$ has height equal to the softened count and base equal to the width step $w/2$. So the band near width $1/4$ contributes about $1.18\times 1/4=0.30$; near $1/8$ about $1.44\times 1/8=0.18$; the contributions shrink because the width step shrinks faster than the softened count grows.

Step 4. Add the bands. The contributions $0.30,0.18,\dots$ keep shrinking and add up to a finite number (a little under $1$). The total does not run off to infinity.

Step 5. What this tells us. The patch count blows up as the width shrinks, but the square-root softening plus the shrinking width steps tame it into a finite total. That finite total is the certificate that this menu is well-behaved, so its magnified error converges to the universal Gaussian limit. This is exactly the half-line threshold menu, and the finite total reproduces the Donsker property already known for it.

Check your understanding Beginner

Formal definition Intermediate+

Throughout, $X_1,X_2,\dots$ are i.i.d. random elements of $(\mathcal{X},\mathcal{A})$ with law $P$, $\mathcal{F}$ is a class of measurable functions $f:\mathcal{X}\to \mathbb{R}$, $P_n=n^{-1}{\sum }_k{\delta }_{X_k}$ is the empirical measure, and ${\mathbb{G}}_{n}f=\sqrt{n}(P_{n}f-Pf)$ is the empirical process, all as fixed in 45.05.02 and 45.05.03. The intrinsic semimetric is ${\rho }_P(f,g)=({\mathrm{Var}}_P(f-g){)}^{1/2}$, and $\Vert h{\Vert }_{Q,r}=(Q|h{|}^r{)}^{1/r}$ denotes the $L^r(Q)$ norm. A measurable $F$ with $|f|\le F$ for all $f\in \mathcal{F}$ is an envelope. The development follows van der Vaart ^{[van der Vaart 1998]} §19.2-19.4 and van der Vaart-Wellner ^{[van der Vaart Wellner 1996]} §2.2-2.6.

Definition (covering and packing numbers). Let $(T,d)$ be a semimetric space. The covering number $N(\epsilon ,T,d)$ is the minimum number of closed balls of radius $\epsilon$ needed to cover $T$. The packing number $D(\epsilon ,T,d)$ is the maximum number of points in $T$ that are pairwise more than $\epsilon$ apart. The two satisfy $N(\epsilon ,T,d)\le D(\epsilon ,T,d)\le N(\epsilon /2,T,d)$. The metric entropy is $\log N(\epsilon ,T,d)$.

Definition (bracketing number and bracketing entropy). For $\ell \le u$, the bracket $[\ell ,u]=\{g:\ell \le g\le u\text{ pointwise}\}$ is an $\epsilon$-bracket in $L^r(P)$ if $\Vert u-\ell {\Vert }_{P,r}\le \epsilon$. The bracketing number $N_{[]}(\epsilon ,\mathcal{F},L^r(P))$ is the minimum number of $\epsilon$-brackets needed to cover $\mathcal{F}$. The bracketing entropy is $\log N_{[]}(\epsilon ,\mathcal{F},L^r(P))$. Because a bracket of width $\epsilon$ has all its members within $\epsilon$ of its midpoint, $N(\epsilon ,\mathcal{F},L^r(P))\le N_{[]}(2\epsilon ,\mathcal{F},L^r(P))$: bracketing entropy dominates ordinary entropy.

Definition (uniform covering number). With envelope $F$, the uniform covering number is

$$\underset{Q}{\sup }N(\epsilon \Vert F{\Vert }_{Q,2},\mathcal{F},L^2(Q)),$$

the supremum over all finitely supported probability measures $Q$ with $\Vert F{\Vert }_{Q,2}>0$. The envelope-relative radius $\epsilon \Vert F{\Vert }_{Q,2}$ makes the quantity scale-free; the supremum over $Q$ makes the resulting bound distribution-free.

Definition (the two entropy integrals). The bracketing integral and the uniform-entropy integral are

$$J_{[]}(\delta ,\mathcal{F},L^2(P))={\int }_0^{\delta }\sqrt{\log N_{[]}(\epsilon ,\mathcal{F},L^2(P))}d\epsilon ,J(\delta ,\mathcal{F})={\int }_0^{\delta }\underset{Q}{\sup }\sqrt{\log N(\epsilon \Vert F{\Vert }_{Q,2},\mathcal{F},L^2(Q))}d\epsilon .$$

The integrand is the square root of the entropy; this is the quantitative signature separating the central limit theorem from the law of large numbers, where bare finiteness of the entropy at each scale already sufficed 45.05.02.

Definition (Orlicz norm). For $p\ge 1$ let ${\psi }_p(x)=e^{x^p}-1$. The Orlicz ${\psi }_p$-norm of a random variable $Z$ is $\Vert Z{\Vert }_{{\psi }_p}=\inf \{C>0:\mathbb{E}{\psi }_p(|Z|/C)\le 1\}$. A finite $\Vert Z{\Vert }_{{\psi }_2}$ encodes a sub-Gaussian tail and a finite $\Vert Z{\Vert }_{{\psi }_1}$ a sub-exponential tail; these are the tail classes of 45.05.01, repackaged as a norm so that maxima can be controlled by a single inequality.

Definition (VC class of functions). A collection $\mathcal{C}$ of subsets of $\mathcal{X}$ is a VC class of VC index $V(\mathcal{C})$ if it shatters no set of $V(\mathcal{C})+1$ points, in the sense fixed in 45.05.02. A class $\mathcal{F}$ of functions is a VC(-subgraph) class if the collection of subgraphs $\{(x,t):t<f(x)\}$, $f\in \mathcal{F}$, is a VC class of subsets of $\mathcal{X}\times \mathbb{R}$; its VC index is that of the subgraph collection. The combinatorial dimension here is identical to the one driving uniform generalisation in statistical learning theory 45.07.03.

Key theorem with proof Intermediate+

Theorem (chaining maximal inequality — Dudley's entropy bound). Let $\{X_t:t\in T\}$ be a stochastic process whose increments are sub-Gaussian for a semimetric $d$, meaning

$$\Vert X_s-X_t{\Vert }_{{\psi }_2}\le Cd(s,t)\text{for all }s,t\in T,$$

and let $T$ be totally bounded for $d$ with diameter $\mathrm{diam}(T)$. Then for some universal constant $K$,

$$\Vert \underset{s,t\in T}{\sup }|X_s-X_t|{\Vert }_{{\psi }_2}\le KC{\int }_0^{\mathrm{diam}(T)}\sqrt{\log N(\epsilon ,T,d)}d\epsilon .$$

Proof. The argument is the chaining method of Dudley ^{[Dudley 1967]}, following van der Vaart-Wellner ^{[van der Vaart Wellner 1996]} §2.2. We use the maximal inequality for finitely many sub-Gaussian variables: if $Z_1,\dots ,Z_m$ have $\Vert Z_i{\Vert }_{{\psi }_2}\le A$, then $\Vert {\max }_i|Z_i|{\Vert }_{{\psi }_2}\le K_{0}A\sqrt{\log (1+m)}$, because ${\psi }_2^{-1}(m)\asymp \sqrt{\log (1+m)}$ and $\mathbb{E}{\psi }_2({\max }_i|Z_i|/(K_{0}A\sqrt{\log (1+m)}))\le {\sum }_i\mathbb{E}{\psi }_2(\cdots )\le 1$.

Set ${\epsilon }_j=2^{-j}\mathrm{diam}(T)$ for $j\ge 0$. For each $j$ choose a minimal ${\epsilon }_j$-net $T_j\subseteq T$ with $|T_j|=N({\epsilon }_j,T,d)$, and a "link" map ${\pi }_j:T\to T_j$ sending each $t$ to a net point within ${\epsilon }_j$. Fix any $s_0\in T$. For $t\in T$ the successive approximations ${\pi }_j(t)$ converge to $t$ (total boundedness), and we telescope:

$$X_t-X_{s_0}=(X_{{\pi }_0(t)}-X_{s_0})+\sum _{j\ge 1}(X_{{\pi }_j(t)}-X_{{\pi }_{j-1}(t)}),$$

the sum converging in ${\psi }_2$ because the links shrink. Each link $X_{{\pi }_j(t)}-X_{{\pi }_{j-1}(t)}$ joins two points at distance $d({\pi }_j(t),{\pi }_{j-1}(t))\le d({\pi }_j(t),t)+d(t,{\pi }_{j-1}(t))\le {\epsilon }_j+{\epsilon }_{j-1}=3{\epsilon }_j$, so its ${\psi }_2$-norm is at most $3C{\epsilon }_j$. At level $j$ the number of distinct links is at most $|T_j|\cdot |T_{j-1}|\le N({\epsilon }_j,T,d{)}^2$. By the finite maximal inequality,

$$\Vert \underset{t}{\max }|X_{{\pi }_j(t)}-X_{{\pi }_{j-1}(t)}|{\Vert }_{{\psi }_2}\le K_0\cdot 3C{\epsilon }_j\cdot \sqrt{\log (1+N({\epsilon }_j,T,d{)}^2)}\le 6K_{0}C{\epsilon }_j\sqrt{\log (1+N({\epsilon }_j,T,d))}.$$

Summing the links by the triangle inequality for the ${\psi }_2$-norm,

$$\Vert \underset{t}{\sup }|X_t-X_{s_0}|{\Vert }_{{\psi }_2}\le 6K_{0}C\sum _{j\ge 0}{\epsilon }_j\sqrt{\log (1+N({\epsilon }_j,T,d))}.$$

Because $\epsilon \mapsto \sqrt{\log N(\epsilon ,T,d)}$ is non-increasing, each term is comparable to the integral over $[{\epsilon }_{j+1},{\epsilon }_j]$: ${\epsilon }_j\sqrt{\log (1+N({\epsilon }_j))}\le 4{\int }_{{\epsilon }_{j+1}}^{{\epsilon }_j}\sqrt{\log (1+N(\epsilon ))}d\epsilon$ up to the $j=0$ boundary term, so the sum is bounded by a constant times ${\int }_0^{\mathrm{diam}(T)}\sqrt{\log N(\epsilon ,T,d)}d\epsilon$. Finally ${\sup }_{s,t}|X_s-X_t|\le 2{\sup }_t|X_t-X_{s_0}|$, absorbing the factor into $K$. $\square$

Bridge. This chaining bound builds toward the entropy Donsker theorems: the empirical process ${\mathbb{G}}_n$, after symmetrisation, has increments that are conditionally sub-Gaussian in the $L^2(P_n)$ metric, so the bound converts a covering-number estimate into a uniform control of ${\mathbb{E}}^{\ast }{\sup }_{{\rho }_P(f,g)<\delta }|{\mathbb{G}}_{n}f-{\mathbb{G}}_{n}g|$, which is exactly the asymptotic equicontinuity that 45.05.03 requires, and it appears again in Gaussian-process theory, where the same integral bounds the modulus of continuity of the limiting $P$-Brownian bridge. The foundational reason a square-root-entropy integral is the right object is that chaining pays, at each scale, a per-link tail cost of order $\sqrt{\log (\text{number of links})}$ — the sub-Gaussian maximal inequality of 45.05.01 — times the link length, and summing length-times-square-root-of-log across geometric scales is precisely the entropy integral. This is exactly the mechanism that generalises the one-grid sandwich of the classical Glivenko-Cantelli proof 45.05.02: there a single coarse grid sufficed for a law-of-large-numbers statement, whereas a central-limit statement needs the full geometric cascade of grids that chaining organises. Putting these together, the metric entropy of $\mathcal{F}$ is the single input that decides both the Glivenko-Cantelli and the Donsker properties, and the bridge is the chaining sum that turns a static count of $\epsilon$-balls into a dynamic bound on the fluctuation of a random process; the central insight is that the difficulty of the empirical CLT lives entirely in this equicontinuity estimate, the finite-dimensional part being free.

Exercises Intermediate+

Advanced results Master

Theorem 1 (the bracketing Donsker theorem with maximal inequality). Suppose $\mathcal{F}$ has envelope $F$ with $P{F}^2<\infty$ and $J_{[]}(\infty ,\mathcal{F},L^2(P))<\infty$. Then $\mathcal{F}$ is $P$-Donsker ^{[van der Vaart Wellner 1996]}. Quantitatively, the bracketing maximal inequality of van der Vaart-Wellner §2.5 gives, for the $\delta$-fluctuation,

$${\mathbb{E}}^{\ast }\underset{{\rho }_P(f,g)<\delta }{\sup }|{\mathbb{G}}_{n}f-{\mathbb{G}}_{n}g|\lesssim J_{[]}(\delta ,\mathcal{F},L^2(P))+\sqrt{n}P[F1\{F>\sqrt{n}a(\delta )\}],$$

with $a(\delta )=\delta /\sqrt{1+\log N_{[]}(\delta ,\mathcal{F},L^2(P))}$. As $\delta \downarrow 0$ the first term vanishes because the integral converges, and the truncation term vanishes for fixed $\delta$ as $n\to \infty$ under $P{F}^2<\infty$ (dominated convergence with the threshold growing in $n$), so the double limit defining asymptotic equicontinuity is zero and 45.05.03 delivers ${\mathbb{G}}_n⇝\mathbb{G}$. The proof chains bracketing partitions at geometric scales, using a Bernstein-type per-link inequality from 45.05.01 rather than the pure sub-Gaussian one, because brackets control $L^2(P)$-width but the increments carry a sub-exponential tail from large bracket endpoints; the truncation term is the price of that tail.

Theorem 2 (the uniform-entropy Donsker theorem). Suppose $\mathcal{F}$ has envelope $F$ with $P{F}^2<\infty$, satisfies the pointwise-measurability/image-admissibility condition, and has $J(\infty ,\mathcal{F})<\infty$. Then $\mathcal{F}$ is $P$-Donsker for every such $P$ ^{[Dudley 1978]}. The proof is symmetrisation followed by conditional chaining in the random $L^2(P_n)$ metric, with the supremum over $Q$ in the definition of $J$ absorbing the empirical metric, exactly as in Exercise 8. The bound is distribution-free in the integral, $P$ entering only through the envelope moment. This is the empirical-process analogue of Dudley's metric-entropy CLT for Gaussian and sub-Gaussian processes.

Theorem 3 (VC implies finite uniform entropy, hence Donsker). If $\mathcal{F}$ is a VC-subgraph class of index $V$ with envelope $F$, then there is a universal constant $K$ with

$$\underset{Q}{\sup }N(\epsilon \Vert F{\Vert }_{Q,2},\mathcal{F},L^2(Q))\le KV(16e{)}^V(\frac{1}{\epsilon }{)}^{2(V-1)},0<\epsilon <1,$$

so ${\sup }_Q\sqrt{\log N}\lesssim \sqrt{V\log (1/\epsilon )}$, which integrates near $0$ ^{[van der Vaart Wellner 1996]}. Hence $J(\infty ,\mathcal{F})<\infty$ and, with $P{F}^2<\infty$, $\mathcal{F}$ is $P$-Donsker for every $P$ — finite VC dimension plus a square-integrable envelope is a distribution-free sufficient condition for the empirical CLT. The bound rests on Sauer's lemma 45.05.02 through the probabilistic-extraction argument of Exercise 7: the polynomial trace count caps the number of $L^2(Q)$-separated functions, with the exponent linear in the VC index. The indicator-of-halfspace class $\{1\{x:⟨a,x⟩\le b\}:a\in {\mathbb{R}}^d,b\in \mathbb{R}\}$ has VC index $d+1$, so it is universally Donsker, the empirical-process backbone of multivariate goodness-of-fit and of margin-based classification.

Theorem 4 (the Rademacher comparison and contraction principle). After symmetrisation, ${\mathbb{E}}^{\ast }\Vert {\mathbb{G}}_n{\Vert }_{\mathcal{F}}$ is comparable, up to constants, to the conditional Rademacher complexity ${\mathbb{E}}^{\ast }{\mathbb{E}}_{\sigma }\Vert n^{-1/2}{\sum }_k{\sigma }_{k}f(X_k){\Vert }_{\mathcal{F}}$ ^{[Giné Zinn 1984]}. The Ledoux-Talagrand contraction principle states that for $1$-Lipschitz ${\varphi }_k$ with ${\varphi }_k(0)=0$,

$${\mathbb{E}}_{\sigma }\underset{f\in \mathcal{F}}{\sup }|\sum _k{\sigma }_k{\varphi }_k(f(X_k))|\le 2{\mathbb{E}}_{\sigma }\underset{f\in \mathcal{F}}{\sup }|\sum _k{\sigma }_{k}f(X_k)|,$$

so composing the class with a fixed contraction can only decrease the Rademacher complexity. This is the same Rademacher quantity that governs uniform generalisation in statistical learning theory 45.07.05, and the contraction principle is the engine behind the preservation calculus: sums, Lipschitz images, and minima/maxima of Donsker classes are Donsker because each operation is a contraction in the symmetrised process.

Theorem 5 (the entropy bound for the limit bridge). If $(\mathcal{F},{\rho }_P)$ is totally bounded with ${\int }_0^{\infty }\sqrt{\log N(\epsilon ,\mathcal{F},{\rho }_P)}d\epsilon <\infty$, then the $P$-Brownian bridge $\mathbb{G}$ with covariance $Pfg-PfPg$ has a version with uniformly ${\rho }_P$-continuous sample paths, a tight Borel element of ${\ell }^{\infty }(\mathcal{F})$ ^{[Dudley 1967]}. This is the Key theorem applied to the Gaussian process $\mathbb{G}$, whose increments satisfy $\Vert \mathbb{G}f-\mathbb{G}g{\Vert }_{{\psi }_2}\asymp {\rho }_P(f,g)$ exactly, so the same chaining integral that controls the discrete fluctuation of ${\mathbb{G}}_n$ controls the continuity modulus of its limit. The existence of the limit object in 45.05.03 and the asymptotic equicontinuity of the approaching sequence are thus two readings of one entropy bound.

Synthesis. The metric entropy of $\mathcal{F}$ is the single input that decides whether the empirical process converges, and chaining is the mechanism that converts a static count of $\epsilon$-balls into a dynamic bound on a random fluctuation. The foundational reason the square-root-entropy integral is the right object is that the central limit scale carries a per-increment sub-Gaussian tail of order $\sqrt{\log (\#\text{links})}$ from 45.05.01, and summing link-length times square-root-of-log across geometric scales is precisely the entropy integral; the law-of-large-numbers scale of 45.05.02 needed only bare finiteness at each scale, which is exactly why Glivenko-Cantelli and Donsker stand to one another as a single grid stands to a cascade of grids. This is exactly the dichotomy that organises the chapter: bracketing entropy in a fixed $L^2(P)$ handles classes like monotone functions through one reference measure, while uniform entropy handles VC classes combinatorially and distribution-free, and the two integrability conditions $\int \sqrt{\log N_{[]}}$ and $\int {\sup }_Q\sqrt{\log N}$ are the Donsker-tier strengthenings of the finiteness that sufficed before.

Putting these together, finite VC index plus a square-integrable envelope is the cleanest sufficient condition, generated by Sauer's lemma through a probabilistic extraction that the same combinatorics powers in statistical learning; it is dual to the bracketing condition in the precise sense that one measures size against a single $P$ and the other against all $Q$ at once, neither containing the other. The central insight is that the asymptotic equicontinuity that 45.05.03 postulated as the entire difficulty of the empirical CLT is, by chaining, nothing more than the finiteness of an entropy integral, so the abstract weak-convergence theorem becomes a checkable calculus on the size of $\mathcal{F}$.

Full proof set Master

The chaining maximal inequality (Dudley's entropy bound), the half-line and VC-indicator covering bounds, the monotone and Lipschitz-parametric bracketing bounds, the finite sub-Gaussian maximal inequality, and the symmetrisation reduction are proved in the Key theorem and Exercises. The remaining Master claims are recorded here.

Proposition 1 (covering-packing comparison). For any semimetric space $(T,d)$ and $\epsilon >0$, $N(\epsilon ,T,d)\le D(\epsilon ,T,d)\le N(\epsilon /2,T,d)$.

Proof. Let $\{t_1,\dots ,t_D\}$ be a maximal $\epsilon$-separated set, $D=D(\epsilon ,T,d)$. Maximality means every $t\in T$ is within $\epsilon$ of some $t_i$ (else $\{t_1,\dots ,t_D,t\}$ would be $\epsilon$-separated, contradicting maximality), so the balls $B(t_i,\epsilon )$ cover $T$ and $N(\epsilon ,T,d)\le D$. For the upper bound, take a minimal $(\epsilon /2)$-net of size $N(\epsilon /2,T,d)$; two points more than $\epsilon$ apart cannot share an $(\epsilon /2)$-ball (the ball has diameter $\le \epsilon$), so each net ball contains at most one point of any $\epsilon$-separated set, giving $D\le N(\epsilon /2,T,d)$. $\square$

Proposition 2 (bracketing entropy dominates ordinary entropy). $N(\epsilon ,\mathcal{F},L^r(P))\le N_{[]}(2\epsilon ,\mathcal{F},L^r(P))$ for every $\epsilon >0$ and $r\ge 1$.

Proof. Take a minimal cover of $\mathcal{F}$ by $2\epsilon$-brackets $[{\ell }_i,u_i]$, $i=1,\dots ,N_{[]}(2\epsilon )$, with $\Vert u_i-{\ell }_i{\Vert }_{P,r}\le 2\epsilon$. Let $m_i=({\ell }_i+u_i)/2$ be the midpoint. Any $f\in [{\ell }_i,u_i]$ satisfies $|f-m_i|\le (u_i-{\ell }_i)/2$ pointwise, so $\Vert f-m_i{\Vert }_{P,r}\le \frac{1}{2}\Vert u_i-{\ell }_i{\Vert }_{P,r}\le \epsilon$. Thus the midpoints $\{m_1,\dots ,m_{N_{[]}(2\epsilon )}\}$ form an $\epsilon$-cover of $\mathcal{F}$ in $L^r(P)$, giving $N(\epsilon ,\mathcal{F},L^r(P))\le N_{[]}(2\epsilon ,\mathcal{F},L^r(P))$. The reverse inequality is false in general: ordinary covering ignores the pointwise sandwich that brackets enforce, which is why the bracketing condition is genuinely stronger and is the natural one when no combinatorial structure is available. $\square$

Proposition 3 (Dudley's tail and high-probability form). Under the hypotheses of the Key theorem, for every $u>0$,

$$\mathbb{P}(\underset{s,t}{\sup }|X_s-X_t|>KC[{\int }_0^{\mathrm{diam}(T)}\sqrt{\log N(\epsilon ,T,d)}d\epsilon +u\mathrm{diam}(T)\left]\right)\le 2e^{-u^2}.$$

Proof. The ${\psi }_2$-norm bound $\Vert {\sup }_{s,t}|X_s-X_t|{\Vert }_{{\psi }_2}\le KCJ$ with $J={\int }_0^{\mathrm{diam}}\sqrt{\log N}d\epsilon$ is, by Markov's inequality applied to ${\psi }_2$, equivalent up to constants to a sub-Gaussian tail: $\mathbb{P}({\sup }_{s,t}|X_s-X_t|>x)\le 2\exp (-x^2/(KCJ{)}^2)$. Setting the tail level via $x=KC(J+u\mathrm{diam}(T))$ and using $J\ge c\mathrm{diam}(T)\sqrt{\log 2}$ (the coarsest single-scale link) to bound the cross term gives the stated form. The deviation term scales with the diameter because the largest single link in the chain has length of order $\mathrm{diam}(T)$ and contributes the leading Gaussian deviation; the entropy integral supplies the mean. This concentration form is what upgrades the equicontinuity-in-mean of Theorems 1-2 to the in-probability statement that the asymptotic-equicontinuity definition of 45.05.03 requires. $\square$

Proposition 4 (VC polynomial covering bound, function case). If $\mathcal{F}$ is a VC-subgraph class of index $V$ with measurable envelope $F$, then for every finitely supported probability measure $Q$ and $0<\epsilon <1$,

$$N(\epsilon \Vert F{\Vert }_{Q,2},\mathcal{F},L^2(Q))\le KV(16e{)}^V{\epsilon }^{-2(V-1)}.$$

Proof sketch. Reduce the function case to the set case via subgraphs, following van der Vaart-Wellner §2.6 ^{[van der Vaart Wellner 1996]}. The subgraphs $\{(x,t):t<f(x)\}$ form a VC class of sets of index $V$ in $\mathcal{X}\times \mathbb{R}$. For functions $f,g$,

$$\Vert f-g{\Vert }_{Q,1}={\int }_{\mathcal{X}}|f-g|dQ=(Q\times \lambda )(\{(x,t):t\text{ between }g(x)\text{ and }f(x)\})=(Q\times \lambda )(S_f△S_g),$$

the measure of the symmetric difference of subgraphs against $Q\times \lambda$ on the relevant strip, normalised by the envelope. So an $L^1$ packing of $\mathcal{F}$ is a packing of the subgraph sets, and Exercise 7's extraction argument applied to the subgraph VC class of index $V$ gives the polynomial bound for $L^1$. The passage from $L^1$ to $L^2$ uses $\Vert f-g{\Vert }_{Q,2}^2\le \Vert f-g{\Vert }_{Q,1}\cdot \Vert f-g{\Vert }_{Q,\infty }$ together with the envelope normalisation, which preserves the polynomial form at the cost of the constants and the factor of $2$ in the exponent. The exponent $2(V-1)$ is linear in the VC index, so the square-rooted log is $\sqrt{V\log (1/\epsilon )}$, integrable near $0$, proving Theorem 3. $\square$

Proposition 5 (the bracketing maximal inequality). Let $\mathcal{F}$ have envelope $F$ and finite bracketing integral. Then with $a(\delta )=\delta /\sqrt{1+\log N_{[]}(\delta ,\mathcal{F},L^2(P))}$,

$${\mathbb{E}}^{\ast }\underset{{\rho }_P(f,g)<\delta }{\sup }|{\mathbb{G}}_{n}f-{\mathbb{G}}_{n}g|\lesssim J_{[]}(\delta ,\mathcal{F},L^2(P))+\sqrt{n}P[F1\{F>\sqrt{n}a(\delta )\}].$$

Proof sketch. This is the maximal inequality of van der Vaart-Wellner §2.5 ^{[van der Vaart Wellner 1996]}. Bracket $\mathcal{F}$ at scales ${\epsilon }_j=2^{-j}\delta$ with $N_{[]}({\epsilon }_j)$ brackets; let ${\pi }_{j}f$ be a bracket midpoint at level $j$ and chain $f-g$ through the telescoping differences of successive midpoints, as in 45.05.03 Proposition 2. Each link is an increment of ${\mathbb{G}}_n$ over a pair at $L^2(P)$-distance $\le {\epsilon }_{j-1}$; here, unlike the pure sub-Gaussian Key theorem, the increment has a Bernstein tail because the bracket width functions can be large, so the per-link bound from 45.05.01 is ${\epsilon }_{j-1}\sqrt{\log N_{[]}({\epsilon }_j)}+{\sqrt{n}}^{-1}\log N_{[]}({\epsilon }_j)\cdot \Vert \text{width}{\Vert }_{\infty }$. The links whose width exceeds the threshold $\sqrt{n}a(\delta )$ are truncated and collected into the second term, which is controlled by $P{F}^2<\infty$. Summing the surviving links over $j$ reconstitutes the bracketing integral $J_{[]}(\delta ,\cdot )$. Both terms vanish in the double limit ($\delta \downarrow 0$ then large $n$), giving asymptotic equicontinuity and Theorem 1. $\square$

Connections Master

The Donsker classes unit 45.05.03 is the direct consumer of everything proved here: it postulated asymptotic ${\rho }_P$-equicontinuity as the entire content of the empirical CLT and deferred the verification, and the chaining maximal inequality is exactly that verification, converting a finite entropy integral into the vanishing equicontinuity modulus. Theorems 1 and 2 of this unit supply the two sufficient conditions — bracketing and uniform entropy — that the abstract theorem of 45.05.03 leaves abstract, and Theorem 5 supplies the existence of the limit bridge it requires.

The empirical-distribution and Glivenko-Cantelli unit 45.05.02 furnishes the combinatorial substrate: covering and bracketing numbers, the VC dimension, Sauer's lemma, and the symmetrisation inequality all originate there as law-of-large-numbers tools, and this unit lifts each from a bare-finiteness (Glivenko-Cantelli) role to a square-root-integrated (Donsker) role, so the relation between the two units is precisely the relation between the law of large numbers and the central limit theorem at the level of entropy conditions.

Bernstein's inequality and the sub-exponential regime 45.05.01 is the per-increment engine of every maximal inequality here: the finite sub-Gaussian maximal inequality, the Bernstein per-link bound in the bracketing chaining of Proposition 5, and the concentration tail of Proposition 3 are all instances of the sub-Gaussian and sub-exponential tail control developed there, packaged through the Orlicz ${\psi }_p$-norm so that maxima over geometrically growing link counts cost only $\sqrt{\log }$.

The VC-dimension and Sauer-Shelah machinery of statistical learning theory 45.07.03 shares the identical combinatorial core: the polynomial covering bound proved here from Sauer's lemma is the same object that bounds the growth function in PAC learning, so finite VC dimension is simultaneously the empirical-process Donsker condition and the learnability condition, two readings of one uniform-convergence phenomenon.

The Rademacher complexity of statistical learning theory 45.07.05 is the symmetrised quantity that Theorem 4 places at the centre: the symmetrisation reduction and the Ledoux-Talagrand contraction principle developed here as tools for the empirical CLT are exactly the tools that yield data-dependent generalisation bounds in learning theory, so the contraction principle that powers the Donsker preservation calculus is the same one that powers Rademacher generalisation bounds.

Historical & philosophical context Master

The metric-entropy method originates with Andrey Kolmogorov and Vladimir Tikhomirov, whose 1959 work on the $\epsilon$-entropy of function classes introduced covering numbers as the basic measure of the size of an infinite-dimensional set. The chaining technique that converts entropy into a bound on the supremum of a random process is due to Richard Dudley, in his 1967 study of the continuity of Gaussian processes ^{[Dudley 1967]}, where the integral ${\int }_0^{\infty }\sqrt{\log N(\epsilon )}d\epsilon$ — now called Dudley's entropy integral — first appeared as a sufficient condition for sample-path continuity. Dudley transferred the method to empirical processes in 1978 ^{[Dudley 1978]}, proving the uniform-entropy central limit theorem and identifying the Vapnik-Chervonenkis classes as the combinatorial source of finite uniform entropy.

The bracketing route, controlling a class through brackets in a fixed reference measure, and the systematic theory of maximal inequalities were developed by David Pollard ^{[Pollard 1984]} and by Evarist Giné and Joel Zinn ^{[Giné Zinn 1984]}, the latter establishing necessary and sufficient conditions for the empirical CLT through symmetrisation and multiplier inequalities. Michel Talagrand's later work on generic chaining showed that the entropy integral, while sufficient, is not always sharp for Gaussian processes, and that the exact modulus is governed by majorising measures; for the empirical process the entropy conditions remain the standard working sufficient conditions. The unification of the bracketing and uniform-entropy routes, with the full catalogue of maximal inequalities, was codified by Aad van der Vaart and Jon Wellner ^{[van der Vaart Wellner 1996]}, the reference text for the modern theory.

Bibliography Master

@article{Dudley1967sizes,
  author  = {Dudley, Richard M.},
  title   = {The sizes of compact subsets of {Hilbert} space and continuity of {Gaussian} processes},
  journal = {Journal of Functional Analysis},
  volume  = {1},
  number  = {3},
  year    = {1967},
  pages   = {290--330}
}

@article{Dudley1978clt,
  author  = {Dudley, Richard M.},
  title   = {Central limit theorems for empirical measures},
  journal = {Annals of Probability},
  volume  = {6},
  number  = {6},
  year    = {1978},
  pages   = {899--929}
}

@article{GineZinn1984,
  author  = {Gin\'e, Evarist and Zinn, Joel},
  title   = {Some limit theorems for empirical processes},
  journal = {Annals of Probability},
  volume  = {12},
  number  = {4},
  year    = {1984},
  pages   = {929--989}
}

@book{Pollard1984,
  author    = {Pollard, David},
  title     = {Convergence of Stochastic Processes},
  publisher = {Springer-Verlag},
  series    = {Springer Series in Statistics},
  address   = {New York},
  year      = {1984}
}

@article{KolmogorovTikhomirov1959,
  author  = {Kolmogorov, Andrey N. and Tikhomirov, Vladimir M.},
  title   = {{$\varepsilon$}-entropy and {$\varepsilon$}-capacity of sets in function spaces},
  journal = {Uspekhi Matematicheskikh Nauk},
  volume  = {14},
  number  = {2},
  year    = {1959},
  pages   = {3--86}
}

@book{LedouxTalagrand1991,
  author    = {Ledoux, Michel and Talagrand, Michel},
  title     = {Probability in Banach Spaces: Isoperimetry and Processes},
  publisher = {Springer-Verlag},
  series    = {Ergebnisse der Mathematik und ihrer Grenzgebiete},
  year      = {1991}
}

@book{vanderVaart1998entropy,
  author    = {van der Vaart, Aad W.},
  title     = {Asymptotic Statistics},
  publisher = {Cambridge University Press},
  series    = {Cambridge Series in Statistical and Probabilistic Mathematics},
  year      = {1998}
}

@book{vanderVaartWellner1996entropy,
  author    = {van der Vaart, Aad W. and Wellner, Jon A.},
  title     = {Weak Convergence and Empirical Processes: With Applications to Statistics},
  publisher = {Springer-Verlag},
  series    = {Springer Series in Statistics},
  address   = {New York},
  year      = {1996}
}

@book{Dudley1999entropy,
  author    = {Dudley, Richard M.},
  title     = {Uniform Central Limit Theorems},
  publisher = {Cambridge University Press},
  series    = {Cambridge Studies in Advanced Mathematics 63},
  year      = {1999}
}