Empirical Processes & Uniform Convergence

Take $X \sim \mathrm{Uniform}(0, 1)$ and squared loss $\ell(x; \theta) = (x - \theta)^2$, so $R(\theta) = \mathrm{Var}(X) + (\mathbb{E} X - \theta)^2$ is minimised at $\theta^\star = 1/2$. The LLN gives $\hat R_n(\theta) \to R(\theta)$ a.s. for every fixed $\theta$. But the minimiser $\hat\theta_n$ of $\hat R_n$ is just the sample mean $\bar X_n$, which by the CLT sits within $O(n^{-1/2})$ of $\theta^\star$ — the same $\sqrt n$-rate that controls $\sup_\theta |\hat R_n(\theta) - R(\theta)|$. This isn’t a coincidence: the rate at which $\hat\theta_n \to \theta^\star$ is controlled by the uniform gap, not the pointwise one. Pointwise LLN on its own gives consistency-in-parameter; it does not give a rate on that consistency. §32.4 supplies the precise condition — finite VC dimension of the loss class — that makes the uniform-convergence rate quantitative.

Topic 29’s Kolmogorov–Smirnov statistic $D_n = \sup_t |F_n(t) - F(t)|$ is the empirical-process object in disguise. Under the null $X_i \sim F$, Glivenko–Cantelli (Topic 10 §10.7) gives $D_n \to 0$ a.s. — the uniform LLN for the distribution-function class $\mathcal{F}_{\mathrm{cdf}} = \{\mathbf{1}_{(-\infty, t]} : t \in \mathbb{R}\}$. Donsker’s theorem (§32.5) supplies the corresponding uniform CLT: $\sqrt n\,D_n$ converges in distribution to the sup of a Brownian bridge, the Kolmogorov distribution Topic 29 §29.8 used to build KS’s distribution-free critical values. The step from “fix a $t$, apply the LLN or CLT” to “take a sup over all $t$, get a uniform analogue” is the leap Topic 32 formalises in generality, for any function class $\mathcal{F}$ not just $\mathcal{F}_{\mathrm{cdf}}$.

Generalisation in machine learning is the same question ERM asks, wearing a different hat: does the training loss on an IID training set track the test loss uniformly over the hypothesis class we’re searching? When the class has finite VC dimension $V$, §32.4 Thm 2 delivers a positive answer with an explicit $O(\sqrt{V \log n / n})$ rate; when it doesn’t — think of neural networks with more parameters than data points — Rademacher-complexity refinements and PAC-Bayes bounds take over, and both reuse §32.4’s symmetrisation technique nearly verbatim. Those refinements live at formalML’s generalization-bounds and pac-bayes-bounds; §32.4 is the version of the result this site proves in full.

Track 8 has been building toward this topic. Topic 29 introduced the ECDF $F_n$ and studied its single-point and 1D-sup-norm behaviour. Topic 30 smoothed $F_n$ into a density estimate $\hat f_h$ and worked out its bias–variance trade-off. Topic 31 resampled from $F_n$ to bootstrap the sampling distribution of any statistic we care about. Each of the three treated $F_n$ as a fixed-point or scalar-statistic object. Topic 32 now treats $F_n$ as a path in the function space $\ell^\infty(\mathbb{R})$, the empirical process $\sqrt n(F_n - F)$ as a random function, and everything the earlier topics did as special cases of this functional viewpoint. The most load-bearing payoff: §32.5 Donsker supplies the limit distribution §29.8 Proof 3 credited without deriving — the single biggest forward-promise of the curriculum, discharged here.

Given iid $X_1, \dots, X_n \sim P$ on a measurable space $(\mathcal{X}, \mathcal{A})$, the empirical measure is $P_n := n^{-1}\sum_{i=1}^n \delta_{X_i}$, the random probability measure that places mass $1/n$ at each sample point. For any measurable $f : \mathcal{X} \to \mathbb{R}$, define

Topic 29’s ECDF $F_n(t) = P_n(\mathbf{1}_{(-\infty, t]})$ is $P_n$ applied to a single half-line indicator; the sample mean $\bar X_n = P_n(\mathrm{id})$ is $P_n$ applied to the identity; Topic 31’s bootstrap draws sample points from $P_n$ rather than from $P$. The empirical measure is the glue holding Track 8 together.

Given a class $\mathcal{F}$ of measurable functions $\mathcal{X} \to \mathbb{R}$, the empirical process indexed by $\mathcal{F}$ is the random function

Two specialisations recover familiar objects. If $\mathcal{F} = \{f\}$ is a singleton, $\mathbb{G}_n f$ is just $\sqrt n$ times the sample-mean deviation of $f(X)$ and the ordinary CLT applies. If $\mathcal{F} = \mathcal{F}_{\mathrm{cdf}} = \{\mathbf{1}_{(-\infty, t]} : t \in \mathbb{R}\}$, then $\mathbb{G}_n(\mathbf{1}_{(-\infty, t]}) = \sqrt n(F_n(t) - F(t))$ — the $\sqrt n$-rescaled CDF-deviation Topic 29 §29.8 worked with. The empirical process is the uniform-index generalisation of both.

For any fixed $f \in \mathcal{F}$ with $P f^2 < \infty$,

by the ordinary CLT (Topic 11 §11.5 Thm 3). This tells us $\mathbb{G}_n$ evaluated at any one $f$ is asymptotically Gaussian; it tells us nothing about joint or uniform behaviour across $\mathcal{F}$. Topic 32’s two organising theorems — uniform LLN (§32.4) and uniform CLT (§32.5) — fill that gap.

The distribution-function class $\mathcal{F}_{\mathrm{cdf}} := \{\mathbf{1}_{(-\infty, t]} : t \in \mathbb{R}\}$ is parametrised by the real line, one function per threshold $t$. The empirical process indexed by this class is $\mathbb{G}_n(\mathbf{1}_{(-\infty, t]}) = \sqrt n(F_n(t) - F(t))$, which we’ll just write $\mathbb{G}_n(t)$ when no confusion arises. This is the class Donsker’s theorem (§32.5 Thm 3) handles in full, discharging the §29.8 IOU. $\mathcal{F}_{\mathrm{cdf}}$ has VC dimension $1$ (see §32.4 Def 6), so it’s also the easiest case of §32.4’s G-C-for-VC theorem.

Fix a parametric family $\{F_\alpha : \alpha \in A\}$ with $A \subseteq \mathbb{R}$ and an observable $q \in (0, 1)$. The class $\mathcal{F} = \{\mathbf{1}\{x \le F_\alpha^{-1}(q)\} : \alpha \in A\}$ contains one indicator per candidate $\alpha$, and $P_n f_\alpha =$ ECDF evaluated at the $q$-th quantile under $\alpha$. $\mathcal{F}$ has VC dimension 1 when $\alpha \mapsto F_\alpha^{-1}(q)$ is monotone (which is the normal case — bigger $\alpha$ shifts the quantile one way). §32.4 Thm 2 applies: $\sup_{\alpha \in A} |P_n f_\alpha - P f_\alpha| \to 0$ a.s., a uniform LLN over the whole family. This is the workhorse result that makes MLE consistent over a parametric family — the statistician’s specialisation of the ML learning-theory bound.

Pointwise LLN (for each $f$, $P_n f \to P f$ a.s.) does NOT imply uniform LLN ($\sup_f |P_n f - P f| \to 0$ a.s.) — the classical Vapnik–Chervonenkis counterexample takes $\mathcal{X} = [0, 1]$, $P$ = Lebesgue, and $\mathcal{F} = \{\mathbf{1}_A : A \text{ finite}\}$; every $f \in \mathcal{F}$ satisfies $P f = 0$, but $\sup_f |P_n f| = 1$ almost surely (pick $A = \{X_1, \dots, X_n\}$). The class is too rich: you can always find some $f$ that indicator-fits the sample perfectly. §32.4 makes precise the complexity condition — finite VC dimension — that excludes these pathological classes and rescues uniform LLN.

For each $\omega$, the path $f \mapsto \mathbb{G}_n(\omega)(f)$ is a bounded function on $\mathcal{F}$ as long as $\mathcal{F}$ has a finite envelope. It lives naturally in the Banach space $\ell^\infty(\mathcal{F})$ of bounded functions $\mathcal{F} \to \mathbb{R}$ with the sup-norm $\|z\|_\mathcal{F} := \sup_{f \in \mathcal{F}} |z(f)|$. The right limit-theorem statement for $\mathbb{G}_n$ is “weak convergence in $\ell^\infty(\mathcal{F})$” — a more delicate notion than ordinary weak convergence because the sup itself need not be measurable. §32.3 handles that machinery.

For a set $\mathcal{F}$, the space $\ell^\infty(\mathcal{F})$ is the set of bounded functions $z : \mathcal{F} \to \mathbb{R}$, equipped with the sup-norm

$(\ell^\infty(\mathcal{F}), \|\cdot\|_\mathcal{F})$ is a Banach space. The empirical process $\mathbb{G}_n$ is an $\ell^\infty(\mathcal{F})$-valued random element whenever $\mathcal{F}$ has a square-integrable envelope: $\sup_{f \in \mathcal{F}} |f| \le F$ with $P F^2 < \infty$ (see §32.6 Def 11 for the formal envelope condition).

For any subset $A \subseteq \Omega$ of the sample space (measurable or not), define

For a function $T : \Omega \to \mathbb{R}$, the outer expectation is $\mathbb{E}^* T := \inf\{\mathbb{E} S : S \ge T, S \text{ measurable}\}$. When $T$ is measurable, $\mathbb{P}^*$ and $\mathbb{E}^*$ collapse to the ordinary $\mathbb{P}$ and $\mathbb{E}$. The construction is due to Hoffmann–Jørgensen (1984) and handles exactly the case of $\sup_f \mathbb{G}_n(f)$ where the supremum over an uncountable class need not be measurable.

A sequence of $\ell^\infty(\mathcal{F})$-valued random elements $\mathbb{G}_n$ converges weakly to a tight random element $\mathbb{G}$, written $\mathbb{G}_n \rightsquigarrow \mathbb{G}$, if

“Tight” means $\mathbb{G}$ concentrates its mass on compact subsets: for every $\varepsilon > 0$ there is a compact $K_\varepsilon \subseteq \ell^\infty(\mathcal{F})$ with $\Pr(\mathbb{G} \notin K_\varepsilon) < \varepsilon$. Tightness is essential because $\ell^\infty(\mathcal{F})$ is not separable for uncountable $\mathcal{F}$ — without it the limit law is ill-defined.

Take $\mathcal{F} = \mathcal{F}_{\mathrm{cdf}}$, sample $X_1 \sim \mathrm{Uniform}(0, 1)$, and consider the map $\omega \mapsto \sup_{t \in \mathbb{R}} \mathbb{G}_1(\omega)(t) = \sup_t \sqrt 1\,(\mathbf{1}\{X_1 \le t\} - t)$. Since $\mathcal{F}_{\mathrm{cdf}}$ is indexed by uncountably many $t$, the supremum is over an uncountable family of measurable functions and need not itself be measurable in a general measure-theoretic sense (any specific construction using the axiom of choice can produce a non-measurable sup). The fix: work with the outer probability $\mathbb{P}^*\bigl(\sup_t \mathbb{G}_n(t) > x\bigr)$ instead. For the classes we actually encounter — VC classes in §32.4, bracketing-finite classes in §32.6 — the supremum is measurable, because continuity of the sample paths a.s. allows reduction to a countable dense index set; outer probability collapses back to probability, and no harm is done.

The outer-probability machinery (VDW1996 §1.3, KOS2008 §7) is the standard fix for non-measurable suprema. It’s the analog of using the outer Lebesgue measure in real analysis: you give up working with ordinary $\sigma$-additivity on all subsets, but you gain the ability to make probabilistic statements about quantities that aren’t technically measurable. Every theorem from §32.4 onwards is stated using $\mathbb{E}^*$ implicitly; we’ll suppress the star except where it matters.

For every Donsker class $\mathcal{F}$ we meet in §§32.4–32.8, the limit process $\mathbb{G}_P$ has a.s. uniformly continuous sample paths with respect to the $L^2(P)$ pseudo-metric on $\mathcal{F}$. Continuity lets you recover $\sup_{f \in \mathcal{F}} \mathbb{G}_P(f)$ from the sup over any countable dense subset, and that sup is measurable. So all our $\mathbb{P}^*$ statements coincide with ordinary $\mathbb{P}$ statements on the event “the limit process is continuous” — which is a full-probability event. The measurability housekeeping is real, but its contribution to the bottom line is zero.

Let $\mathcal{F}$ be a class of $\{0, 1\}$-valued functions on $\mathcal{X}$. For any finite set $\{x_1, \dots, x_n\} \subseteq \mathcal{X}$, the restriction of $\mathcal{F}$ to this set is the finite set of labellings $\{(f(x_1), \dots, f(x_n)) : f \in \mathcal{F}\} \subseteq \{0, 1\}^n$. The shatter coefficient is

A set $\{x_1, \dots, x_n\}$ is shattered by $\mathcal{F}$ if its restriction has cardinality $2^n$ — every $\{0,1\}^n$-labelling is realised. The VC dimension of $\mathcal{F}$ is the largest $n$ such that some $n$-point set is shattered:

If $s_{\mathcal{F}}(n) = 2^n$ for every $n$, the class has infinite VC dimension (and is too rich to be Glivenko–Cantelli).

A class $\mathcal{F}$ is a Glivenko–Cantelli class for $P$ (or $P$-GC) if

Equivalently: the uniform LLN holds on $\mathcal{F}$ under $P$. Thm 2 below says that any VC-finite class is $P$-GC for every $P$ — uniformity is both over $f \in \mathcal{F}$ and over the distribution. That distribution-free property is what makes the result useful in ML, where we never know $P$.

Let $\mathcal{F}$ have VC dimension $V < \infty$. Then for every $n \ge 1$,

The shatter coefficient — which a priori could grow as fast as $2^n$ — is forced into polynomial growth in $n$ the moment the VC dimension is finite. This is the pigeonhole miracle that makes §32.4 Thm 2 work: the finite-class bound in Step 4 of the proof below only costs a factor of $s_{\mathcal{F}}(n) \le (n+1)^V$, not $2^n$.

Proof (sketch). The classical argument is by induction on the size of the sample set, with the inductive step carefully tracking which subsets remain shattered under a one-point extension. Full proof in SAU1972 (3 pages, self-contained); independently in SHE1972 and VAP1971. We omit it here — the proof is elegant but the combinatorics don’t carry over to Donsker or the delta method, so it doesn’t earn its real estate in a topic whose mathematical through-line is fidi+tightness.

Let $\mathcal{F}$ be a class of $\{0, 1\}$-valued measurable functions on $(\mathcal{X}, \mathcal{A})$ with finite VC dimension $V := \mathrm{VC}(\mathcal{F})$. Then, for any probability measure $P$ on $(\mathcal{X}, \mathcal{A})$,

Consider $\mathcal{F} = \{\mathbf{1}\{w \cdot x \le b\} : w \in \mathbb{R}^d,\, b \in \mathbb{R}\}$, the class of halfspace indicators in $\mathbb{R}^d$. Take any $d + 1$ points in general position (no $d + 1$ on a common affine hyperplane) — these shatter: for any target labelling, solve the linear system $\mathrm{sign}(w \cdot x_i - b) = \pm 1$ coordinate-wise, and a non-degenerate Radon separation always exists. So $\mathrm{VC}(\mathcal{F}) \ge d + 1$.

The matching upper bound is Radon’s theorem: any $d + 2$ points in $\mathbb{R}^d$ admit a partition into two subsets whose convex hulls intersect. Pick such a partition and target the labelling +1 for one subset, −1 for the other; a separating hyperplane would have to put both convex hulls on opposite sides, which is impossible because they share a point. No halfspace realises this labelling, so $d + 2$ points never shatter, and $\mathrm{VC}(\mathcal{F}) = d + 1$.

The class $\mathcal{F} = \{\mathbf{1}\{a_1 \le x_1 \le b_1, a_2 \le x_2 \le b_2\}\}$ of axis-aligned rectangles in $\mathbb{R}^2$ shatters the four-point diamond $\{(0, 1), (1, 0), (0, -1), (-1, 0)\}$: for any target labelling, put the tightest axis-aligned rectangle around the “+1”-labelled points — the four-point geometry guarantees no “−1” point lies inside. So $\mathrm{VC}(\mathcal{F}) \ge 4$.

Now take any $5$ points. Form the tightest axis-aligned bounding box around them. Each of the four sides of this box is “supported” by at least one of the five points (the side coincides with the extremal $x$- or $y$-coordinate); by pigeonhole at least one point is not extremal on any side. Label the non-extremal point $-1$ and the four extremal points $+1$. Any rectangle containing the four $+1$-points must contain their axis-aligned bounding box, which contains the non-extremal point — so it labels the $-1$-point as $+1$. No rectangle realises this labelling, and $\mathrm{VC}(\mathcal{F}) = 4$.

Topic 10 §10.7 Ex 8 asked: is Glivenko–Cantelli what makes ERM work? and left the answer as a forward-pointer to “empirical-process theory (coming in the Statistical Inference track)”. Thm 2 discharges that IOU. Concretely: fix a loss $\ell$ and a hypothesis class $\Theta$ such that the induced loss class $\{\ell(\cdot; \theta) : \theta \in \Theta\}$ has VC dimension $V$. Let $\hat\theta_n = \arg\min_\theta \hat R_n(\theta)$ and $\theta^\star = \arg\min_\theta R(\theta)$. Feeding Thm 2’s high-probability bound through the ERM triangle inequality gives

with probability $\ge 1 - n^{-c}$ for any $c > 0$. The $\sqrt{V/n}$ scaling is the cleanest statement of ERM consistency the topic produces, and the Topic 10 IOU is paid in full.

The five-step proof above is a template, not a one-off. Symmetrisation → Rademacher randomisation → Sauer reduction → Hoeffding + union bound → Borel–Cantelli. Every VC-flavoured, PAC-flavoured, and Rademacher-complexity result in statistical learning theory reuses at least three of these five moves, usually in the same order. Once you’ve digested the Thm 2 proof, the PAC-Bayes bound is a symmetrisation + change-of-measure; Rademacher-complexity bounds are a symmetrisation + contraction; uniform-convergence-of-risk is this proof with a generic loss class instead of $\{0,1\}$-indicators. The Hoeffding step is the only one that genuinely requires ”$f$ is bounded”; everything else works for general $\mathcal{F}$, with Hoeffding replaced by Bernstein or Talagrand (§32.9).

VC dimension is the binary-classification complexity measure; for multi-class problems the Natarajan dimension takes over, for real-valued regression classes it’s the pseudo-dimension or fat-shattering dimension, and for kernel methods Rademacher complexity gives sharper data-dependent rates that VC cannot. Each refinement costs more machinery but delivers the uniform-convergence payoff for a broader hypothesis class. All three are deferred to formalML’s generalization-bounds topic, which carries the full menu. §32.4 stays at classical binary VC because it’s the cleanest case and the one that carries the rest of the topic — the symmetrisation + Sauer combo is the reusable pattern.

Thm 2 combined with Ex 8 is what Shalev-Shwartz and Ben-David (2014, Ch. 6) call the fundamental theorem of statistical learning: a binary hypothesis class $\Theta$ is PAC-learnable if and only if it has finite VC dimension, and the sample complexity of learning it is $\Theta(V / \varepsilon^2)$ up to log factors. The iff is striking — finite VC is both necessary and sufficient for uniform generalisation — and it’s the cleanest structural result in statistical learning theory. Topic 32’s most visible ML payoff is this theorem; everything else in the topic either builds toward it (§§32.1–32.3) or lifts it to richer settings (§§32.5–32.9). formalML picks up from here and develops neural-net-scale generalisation bounds where classical VC fails and Rademacher complexity takes over.

A standard Brownian bridge $\mathbb{B}^\circ$ is a centred Gaussian process on $[0, 1]$ with covariance function

and boundary conditions $\mathbb{B}^\circ(0) = \mathbb{B}^\circ(1) = 0$ almost surely. (The name “bridge” captures the latter: it’s a Brownian motion pinned at both endpoints.) Given a continuous CDF $F$ on $\mathbb{R}$, the $F$-Brownian bridge is the process $\mathbb{B}_F : \mathbb{R} \to \mathbb{R}$ defined by

a centred Gaussian process with covariance $\mathrm{Cov}(\mathbb{B}_F(s), \mathbb{B}_F(t)) = F(s \wedge t) - F(s)F(t)$. Both processes have continuous sample paths a.s. (Lem 3 below).

Let $W$ be a standard Brownian motion on $[0, 1]$. The process $\mathbb{B}^\circ(t) := W(t) - t\,W(1)$ is a standard Brownian bridge: centred Gaussian, covariance $s \wedge t - st$, and $\mathbb{B}^\circ(0) = \mathbb{B}^\circ(1) = 0$. Continuous sample paths on $[0, 1]$ a.s. are inherited from $W$‘s continuity. Full construction and verification in BIL1999 §14. The brownianBridgePath helper in nonparametric.ts §17 implements the discretised version used by EmpiricalProcessExplorer’s reference overlay.

Let $X_1, X_2, \dots$ be iid with continuous CDF $F$, and let $F_n$ denote the empirical CDF. Then

where $\mathbb{B}_F := \mathbb{B}^\circ \circ F$ and $\mathbb{B}^\circ$ is a standard Brownian bridge on $[0, 1]$.