Chaining and Dudley's Inequality

Instead of one net, chain many nets from coarse to fine and add up the errors. Dudley's sum turns covering counts at every scale into a bound on the worst fluctuation of a whole process.

A chain of nets from one coarse ball down to fine dots bounds the worst fluctuation by adding the step sizes across scales

Why Does This Exist?

A union bound over one $\varepsilon$ -net pays the full log covering count at the finest scale, which is often too loose. The worst fluctuation of a random process is not decided at one resolution: coarse structure contributes large steps with few alternatives, fine structure contributes tiny steps with many alternatives. Charging every alternative the finest price overpays.

Chaining fixes the accounting. Build nets at geometrically shrinking radii, link each point to its parent one scale up, and bound the supremum (the worst value over the set) by the sum of link fluctuations. Dudley's inequality is that sum written with covering numbers: an integral of $\sqrt{\log N(\varepsilon)}$ over scales. It converts the whole covering curve into one number and underpins fast rates for local Rademacher complexity and generalisation.

Prerequisite in one paragraph. You need covering numbers $N(\varepsilon)$ , the count of radius- $\varepsilon$ balls hiding a set, and sub-Gaussian increments, meaning each difference $X_s - X_t$ has a thin tail scaled by the distance $d(s,t)$ . Covering is in covering and packing numbers; thin tails are in concentration of measure.

Think of It Like This

Zooming a map in fixed steps

To bound the longest detour on any route through a country, you do not list every house. You start with one dot for the whole country, then regional dots, then town dots, then streets. Each zoom step corrects the previous position by a smaller amount, and the number of alternatives grows as the steps shrink.

The total detour is the sum of corrections across zooms. Coarse zooms move far but offer few choices; fine zooms offer millions of choices but each moves metres. Chaining adds those contributions scale by scale instead of charging every house the finest price.

Where the analogy stops: map zooms are nested grids, while chaining nets are arbitrary centres chosen to minimise counts. The sum also carries universal constants the map never had.

How It Actually Works

Let $\{X_t: t \in T\}$ be a mean-zero process with sub-Gaussian increments: $P(|X_s - X_t| \ge u) \le 2\exp(-u^2/2d(s,t)^2)$ for a metric $d$ . Let $D$ be the diameter of $T$ (its largest distance). Dudley's inequality says $E[\sup_t X_t] \le C \int_0^D \sqrt{\log N(T, d, \varepsilon)}\, d\varepsilon$ , where $E$ is mean, $\sup$ is the worst value, $N$ is the covering number and $C$ is a universal constant near $12$ (often quoted as $4.5$ in sharper forms; the shape matters, not the digit).

The construction telescopes. Pick nets $T_k$ at radii $2^{-k}D$ . Every $t$ links to its nearest parent $\pi_k(t)$ one scale up, and $X_t$ equals the sum of increments $X_{\pi_{k+1}(t)} - X_{\pi_k(t)}$ along the chain. Each scale contributes a union bound over $|T_k| \le N(2^{-k}D)$ links of size about $2^{-k}D\sqrt{\log N}$ . Summing over $k$ gives the integral.

Worked example

Take the unit ball in $5$ dimensions with Euclidean distance, diameter $D = 2$ . The volumetric cover gives $\log N(\varepsilon) \le 5\ln(1 + 2/\varepsilon)$ . At $\varepsilon = 0.10$ that is $5\ln 21 \approx 15.2$ as computed on the covering page. The Dudley integral from $0$ to $2$ of $\sqrt{5\ln(1+2/\varepsilon)}\,d\varepsilon$ evaluates numerically to about $3.9$ with the constant $C = 1$ stripped out, so $E[\sup X_t] \le C \times 3.9 \times \sigma$ where $\sigma$ scales the increments.

A single-scale union bound at $\varepsilon = 0.10$ would instead charge $\sqrt{15.2} \approx 3.9$ plus a $0.10$ approximation error on every one of $4.1$ million centres, similar here but far looser when entropy grows like $\varepsilon^{-2}$ , where the integral converges while the single-scale bound blows up. That convergence gap is exactly when chaining wins.

Watch Out For

Integrating the wrong entropy power

Dudley's integral converges when $\sqrt{\log N(\varepsilon)}$ is integrable near zero, for example $\log N \sim \varepsilon^{-p}$ with $p < 2$ . For classes with $p \ge 2$ the integral diverges and the bound is vacuous, yet people quote a finite number by cutting the integral at an arbitrary floor. The cutoff is doing all the work and the theorem promises nothing.

Fix: check integrability first. If the integral diverges, switch to generic chaining with majorizing measures or accept slower rates.

Dropping the diameter limit on the integral

The integral runs $0$ to $D$ , the set diameter. Extending it to infinity or starting it at $1$ silently adds phantom scales with no points in them, inflating or deflating the bound by a factor that dwarfs the constant $C$ .

Fix: cap the top at $D$ and handle the bottom by the finest meaningful scale. Write both limits every time.

The Quick Version

Chaining links coarse-to-fine nets so each scale pays only its own log count.
Dudley bounds the worst fluctuation by the integral of $\sqrt{\log N(\varepsilon)}$ up to the diameter.
A 5-dimensional unit ball gives an integral near 3.9 times the increment scale.
Single-scale union bounds overpay when entropy grows fast; chaining converges where they blow up.
The integral must stop at the diameter and needs integrable entropy near zero to say anything.