Empirical Processes and Chaining

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$.

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.

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.

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.

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.

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.

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.

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.

Let $(X_t)_{t \in T}$ be a centered Gaussian process with canonical metric $d(s, t) = \sqrt{\mathbb{E}[(X_s - X_t)^2]}$. Then for every $\epsilon > 0$:

$\mathbb{E}\left[\sup_{t \in T} X_t\right] \geq \frac{c \cdot \epsilon}{\sqrt{\log 2}} \sqrt{\log D(\epsilon, T, d)}$

for a universal constant $c$. Equivalently, since $D(\epsilon) \leq N(\epsilon) \leq D(\epsilon/2)$:

$\mathbb{E}\left[\sup_{t \in T} X_t\right] \geq c' \cdot \epsilon \sqrt{\log N(2\epsilon, T, d)}$

A packing of size $D(\epsilon)$ in $T$ produces $D(\epsilon)$ Gaussians with pairwise standard deviation at least $\epsilon$. The maximum of $N$ independent or weakly correlated standard Gaussians grows like $\sqrt{2 \log N}$, so taking the maximum over the packing gives a contribution of order $\epsilon \sqrt{\log D(\epsilon)}$. The minoration extracts this single-scale lower bound; supremum over $\epsilon$ is the sharpest version.

Combined with Dudley's upper bound, Sudakov gives:

$c \sup_{\epsilon > 0} \epsilon \sqrt{\log N(\epsilon)} \leq \mathbb{E}\left[\sup_t X_t\right] \leq C \int_0^\infty \sqrt{\log N(\epsilon)}\, d\epsilon$

The two bounds match up to a $\sqrt{\log |T|}$ factor in the worst case, and exactly when $\log N(\epsilon)$ is regularly varying. This is why Talagrand's $\gamma_2$ functional was needed: it closes the gap and gives a characterization up to universal constants.

Sudakov is sharp only at the single optimizing scale and only for Gaussian processes (or sub-Gaussian processes via a comparison theorem). For sub-exponential or heavy-tailed processes, neither Sudakov nor Dudley directly applies; you need separate tools (Bernstein-type concentration, generic chaining with $\gamma_1 + \gamma_2$).

Let $(X_t)_{t \in T}$ and $(Y_t)_{t \in T}$ be centered Gaussian processes on a finite index set $T$. If

$\mathbb{E}[(X_s - X_t)^2] \geq \mathbb{E}[(Y_s - Y_t)^2] \quad \text{for all } s, t \in T,$

then

$\mathbb{E}\left[\sup_{t \in T} X_t\right] \geq \mathbb{E}\left[\sup_{t \in T} Y_t\right]$

Larger increments push points apart more, so the maximum spreads farther from zero in expectation. The comparison is on increments, not on marginal variances; only the geometry of the process matters.

Slepian's inequality is the stronger statement: under the same increment condition plus equal marginal variances ($\mathbb{E}[X_t^2] = \mathbb{E}[Y_t^2]$), every tail probability of $\sup X_t$ exceeds the corresponding probability for $\sup Y_t$. Sudakov-Fernique drops the equal-variance condition at the cost of giving only an expectation comparison.

This is the key tool to pass from a Gaussian process indexed by a function class to a canonical Gaussian process whose suprema are explicit. Examples:

• Random matrix operator norm: the operator norm of an $n \times n$ Gaussian matrix can be sandwiched between two reference processes, yielding $\mathbb{E}\|G\|_{\text{op}} \leq 2\sqrt{n}$ (Gordon's theorem).
• Comparison to white noise: bounds on suprema of empirical processes often pass through comparison with a Gaussian process built from Brownian motion.
• Chevet-type inequalities: bilinear bounds for products of two function classes use Sudakov-Fernique on the bilinear Gaussian process $X_{u, v} = \langle u, G v \rangle$.

Both processes must be Gaussian. The inequality fails for sub-Gaussian processes in general; the Talagrand-Borell-Tsirelson comparison theorems are the sub-Gaussian replacements but require additional structure.

Let $\mathcal{F}$ be a class of real-valued functions on $\mathcal{X}$. Let $\varphi_1, \ldots, \varphi_n : \mathbb{R} \to \mathbb{R}$ be $L$-Lipschitz with $\varphi_i(0) = 0$. Let $\varepsilon_1, \ldots, \varepsilon_n$ be i.i.d. Rademacher signs and $x_1, \ldots, x_n \in \mathcal{X}$ fixed. Then:

$\mathbb{E}_\varepsilon\left[\sup_{f \in \mathcal{F}} \sum_{i=1}^n \varepsilon_i \varphi_i(f(x_i))\right] \leq 2L \cdot \mathbb{E}_\varepsilon\left[\sup_{f \in \mathcal{F}} \sum_{i=1}^n \varepsilon_i f(x_i)\right]$

Dividing both sides by $n$ gives the Rademacher-complexity form:

$\mathfrak{R}_n(\varphi \circ \mathcal{F}) \leq 2L \cdot \mathfrak{R}_n(\mathcal{F})$

The constant $2L$ is the standard Ledoux-Talagrand constant; under the additional assumption that $\mathcal{F}$ is symmetric ($-\mathcal{F} = \mathcal{F}$), the constant tightens to $L$ (Boucheron-Lugosi-Massart, Theorem 11.6).

Pointwise Lipschitz application cannot stretch distances, only contract them. The Rademacher complexity measures how much the function class can correlate with random signs $\pm 1$ on the data. Contraction passes through this correlation up to a factor of the Lipschitz constant. The anchoring $\varphi_i(0) = 0$ removes a deterministic shift that would otherwise add a constant to the supremum without increasing the complexity.

This is the bridge from $\mathfrak{R}_n(\mathcal{H})$ (the quantity you can compute or bound via covering numbers) to $\mathfrak{R}_n(\ell \circ \mathcal{H})$ (the quantity that appears in the generalization bound).

• Margin loss: $\varphi(t) = \min(1, \max(0, 1 - t))$ is $1$-Lipschitz, so the margin-loss complexity is at most $2 \mathfrak{R}_n(\mathcal{H})$.
• Logistic loss: $\varphi(t) = \log(1 + e^{-t})$ is $1$-Lipschitz, same bound.
• Hinge loss: $\varphi(t) = \max(0, 1 - t)$ is $1$-Lipschitz with $\varphi(0) = 1 \neq 0$; use a centering trick or absorb the constant into the bias.

For neural networks where $\mathcal{H}$ is bounded in $\ell_2$ but the post-activation is squashed by a Lipschitz nonlinearity, this gives layer-by- layer Rademacher bounds.

For full statement and proof discussion see contraction inequality.

Two failure modes appear in practice:

1. The anchoring condition $\varphi(0) = 0$ matters. Without it, the inequality picks up a $\mathbb{E}[|\varphi(0)|]$ term that does not vanish even when the function class is centered. Most ML losses can be shifted to satisfy this without changing the learned predictor.
2. Vector contraction is more subtle. For a class of vector-valued functions $f : \mathcal{X} \to \mathbb{R}^k$ with a Lipschitz scalarization, the Maurer (2016) vector contraction inequality gives a bound of order $\sqrt{2}\, L$ per coordinate but requires $k$-dependence in the worst case. This matters for multi-class classification where the effective $k$ is the number of classes.