Empirical Processes and Chaining

Why This Matters

The central question of learning theory is: how fast does the empirical risk converge to the population risk, uniformly over a function class? This question reduces to bounding the supremum of an empirical process. Dudley's entropy integral and Talagrand's generic chaining are the two main tools for this task.

Dudley's bound converts covering number estimates (geometric information about the function class) into bounds on the expected supremum. Generic chaining improves on Dudley by a logarithmic factor in many cases. Together, they represent the culmination of the covering number approach to learning theory.

Formal Setup

Definition

Empirical Process

Given i.i.d. samples $X_1, \ldots, X_n$ from distribution $P$ and a function class $\mathcal{F}$, the empirical process is:

$G_n(f) = \sqrt{n}\left(\frac{1}{n}\sum_{i=1}^n f(X_i) - \mathbb{E}[f(X)]\right) = \sqrt{n}(P_n f - Pf)$

where $P_n = \frac{1}{n}\sum_{i=1}^n \delta_{X_i}$ is the empirical measure.

Definition

Supremum of the Empirical Process

The quantity of interest for uniform convergence is:

$\sup_{f \in \mathcal{F}} |G_n(f)| = \sqrt{n} \sup_{f \in \mathcal{F}} |P_n f - Pf|$

Bounding $\mathbb{E}[\sup_{f \in \mathcal{F}} |G_n(f)|]$ controls how well empirical risk approximates population risk uniformly over $\mathcal{F}$.

Definition

Covering Number

The covering number $N(\epsilon, \mathcal{F}, d)$ is the minimum number of balls of radius $\epsilon$ (in metric $d$) needed to cover $\mathcal{F}$. The metric entropy is $\log N(\epsilon, \mathcal{F}, d)$.

The Chaining Idea

The naive approach is to discretize $\mathcal{F}$ at a single resolution $\epsilon$ and take a union bound over the $\epsilon$-net. This gives:

$\mathbb{E}\left[\sup_{f \in \mathcal{F}} |G_n(f)|\right] \lesssim \epsilon\sqrt{n} + \sqrt{\log N(\epsilon, \mathcal{F}, L_2(P_n))}$

The problem: choosing $\epsilon$ involves a tradeoff. Small $\epsilon$ controls approximation error but increases the covering number. Large $\epsilon$ is the reverse.

Chaining resolves this by discretizing at all scales simultaneously. Build a sequence of increasingly fine $\epsilon$-nets $\mathcal{F}_0 \subset \mathcal{F}_1 \subset \cdots$ with $\epsilon_k = 2^{-k}$. For each $f \in \mathcal{F}$, write $f = f_0 + (f_1 - f_0) + (f_2 - f_1) + \cdots$ where $f_k$ is the nearest point to $f$ in the $k$-th net. Bound each increment separately.

Main Theorems

Theorem

Dudley's Entropy Integral

Statement

Let $\mathcal{F}$ be a function class with envelope $F$ (meaning $|f| \leq F$ for all $f \in \mathcal{F}$) and let $\sigma^2 = \sup_{f \in \mathcal{F}} \text{Var}(f(X))$. Then:

$\mathbb{E}\left[\sup_{f \in \mathcal{F}} |G_n(f)|\right] \leq C \int_0^{\sigma} \sqrt{\log N(\epsilon, \mathcal{F}, L_2(P))}\, d\epsilon$

where $C$ is a universal constant. The integral converges whenever the covering numbers grow at most polynomially as $\epsilon \to 0$.

Intuition

At each scale $\epsilon$, the contribution to the supremum is controlled by $\sqrt{\log N(\epsilon)}$ (a union bound over the net at that scale). Chaining integrates these contributions across all scales. Coarse scales (large $\epsilon$) contribute little because the net is small. Fine scales (small $\epsilon$) contribute little because the increments are small. The integral balances these.

Proof Sketch

Fix a sequence of scales $\epsilon_k = 2^{-k} \sigma$ and corresponding $\epsilon_k$-nets $\mathcal{N}_k$. For each $f$, let $\pi_k(f)$ be the closest point in $\mathcal{N}_k$. Write:

$G_n(f) = G_n(\pi_0(f)) + \sum_{k=1}^K [G_n(\pi_k(f)) - G_n(\pi_{k-1}(f))] + G_n(f) - G_n(\pi_K(f))$

The first term is bounded by $\sqrt{\log |\mathcal{N}_0|}$ via a union bound. Each increment has sub-Gaussian parameter $O(\epsilon_k / \sqrt{n})$ and there are $|\mathcal{N}_k|$ choices, giving $\sqrt{\log |\mathcal{N}_k|}$ per scale. Summing over scales gives the integral.

Why It Matters

This is the standard tool for converting covering number estimates into generalization bounds. For a class with $\log N(\epsilon) = O(d \log(1/\epsilon))$ (like VC classes or linear predictors), the integral evaluates to $O(\sqrt{d})$, recovering the standard $O(\sqrt{d/n})$ generalization bound without going through VC theory.

Failure Mode

Dudley's bound is not tight in general. It can be loose by a $\sqrt{\log n}$ factor compared to the true expected supremum. For classes where the covering numbers have complex structure at different scales, generic chaining gives tighter results.

Theorem

Talagrand's Generic Chaining (Majorizing Measures)

Statement

For a centered Gaussian process $(X_t)_{t \in T}$, define the $\gamma_2$ functional:

$\gamma_2(T, d) = \inf_{\{A_k\}} \sup_{t \in T} \sum_{k=0}^{\infty} 2^{k/2} d(t, A_k)$

where the infimum is over all sequences of sets $A_k$ with $|A_k| \leq 2^{2^k}$. Then:

$\frac{1}{L} \gamma_2(T, d) \leq \mathbb{E}\left[\sup_{t \in T} X_t\right] \leq L \cdot \gamma_2(T, d)$

for a universal constant $L$. The $\gamma_2$ functional characterizes the expected supremum up to universal constants.

Intuition

Generic chaining replaces the uniform covering at each scale (Dudley) with an optimized covering that can vary across the set $T$. Some points in $T$ may need fine resolution while others do not. The $\gamma_2$ functional captures this by allowing different "chains" for different points.

Proof Sketch

The upper bound follows the same chaining idea as Dudley, but with optimized nets $A_k$ instead of minimal coverings. The lower bound (which makes this a characterization, not just an upper bound) uses the Sudakov minoration argument and a sophisticated construction of the admissible sequence.

Why It Matters

This is the definitive result on suprema of Gaussian processes. Since empirical processes can be compared to Gaussian processes via symmetrization and comparison inequalities, this provides the tightest possible bounds on learning theory quantities. It resolves a long-standing question in probability theory about when chaining gives the right answer.

Failure Mode

The $\gamma_2$ functional is hard to compute in general. For most applications, Dudley's entropy integral is sufficient and much more practical. Generic chaining is most useful for proving theoretical optimality results rather than computing explicit bounds.

Connection to Learning Theory

The Rademacher complexity of a function class $\mathcal{F}$ is:

$\mathfrak{R}_n(\mathcal{F}) = \mathbb{E}\left[\sup_{f \in \mathcal{F}} \frac{1}{n} \sum_{i=1}^n \sigma_i f(X_i)\right]$

By symmetrization, $\mathbb{E}[\sup_f |P_n f - Pf|] \leq 2\mathfrak{R}_n(\mathcal{F})$. Dudley's bound then gives:

$\mathfrak{R}_n(\mathcal{F}) \leq \frac{C}{\sqrt{n}} \int_0^\infty \sqrt{\log N(\epsilon, \mathcal{F}, L_2(P_n))}\, d\epsilon$

This is how covering numbers and chaining enter generalization bounds.

Canonical Examples

Example

Linear classifiers in R^d

For $\mathcal{F} = \{x \mapsto \langle w, x \rangle : \|w\| \leq 1, \|x\| \leq 1\}$, the covering number satisfies $\log N(\epsilon, \mathcal{F}, L_2) \leq d \log(3/\epsilon)$. Dudley's integral gives:

$\int_0^1 \sqrt{d \log(3/\epsilon)}\, d\epsilon = O(\sqrt{d})$

So $\mathfrak{R}_n(\mathcal{F}) = O(\sqrt{d/n})$, recovering the standard bound.

Common Confusions

Watch Out

Chaining is not a single-scale argument

The power of chaining comes from simultaneously using approximations at all scales. A single-scale argument (discretize at one $\epsilon$) always involves a tradeoff between approximation error and the size of the net. Chaining eliminates this tradeoff by summing contributions across scales.

Watch Out

Dudley vs Talagrand: when does the difference matter?

For most function classes encountered in ML (VC classes, kernel classes, neural network classes with bounded norms), Dudley's integral gives bounds that are tight up to logarithmic factors. Generic chaining matters when the geometry of the function class has different complexity at different scales, which is rare in standard applications but important in probability theory.

Summary

• Empirical process theory reduces generalization to bounding $\sup_f |P_n f - Pf|$
• Dudley's entropy integral: $\mathbb{E}[\sup |G_n|] \leq C \int \sqrt{\log N(\epsilon)}\,d\epsilon$
• Chaining works by discretizing at all scales simultaneously
• Generic chaining ($\gamma_2$) is tight for Gaussian processes but hard to compute
• For practical ML bounds, Dudley's integral with covering number estimates suffices

Exercises

ExerciseCore

Problem

For a function class with $\log N(\epsilon, \mathcal{F}, L_2) = d \log(1/\epsilon)$, evaluate Dudley's entropy integral up to constants and state the resulting generalization bound.

Hint

Reveal Solution

ExerciseAdvanced

Problem

Explain why a single-scale $\epsilon$-net argument gives a bound of $O(\epsilon + \sqrt{d\log(1/\epsilon)/n})$ and why optimizing over $\epsilon$ gives $O(\sqrt{d\log n / n})$, which is worse than Dudley's $O(\sqrt{d/n})$ by a $\sqrt{\log n}$ factor.

Hint

Reveal Solution

ExerciseResearch

Problem

State Sudakov's minoration: a lower bound on the expected supremum of a Gaussian process in terms of a single-scale packing number. Explain why this shows Dudley's integral cannot be improved by more than a logarithmic factor.

Hint

Reveal Solution

References

Canonical:

• van der Vaart & Wellner, Weak Convergence and Empirical Processes, Chapter 2
• Vershynin, High-Dimensional Probability, Chapter 8

Current:

• Talagrand, Upper and Lower Bounds for Stochastic Processes (2014)

• Boucheron, Lugosi, Massart, Concentration Inequalities (2013), Chapters 2-6

• Wainwright, High-Dimensional Statistics (2019), Chapter 2

• van Handel, Probability in High Dimension (2016), Chapters 1-3

Next Topics

• Minimax lower bounds: using empirical process theory to prove optimality