on Dudley's Theorem

Overview

This post explores Dudley’s Theorem, a cornerstone of the theory of stochastic processes. It provides a foundational upper bound on the expected supremum of a sub-Gaussian process by quantifying the “complexity” of the index set using Metric Entropy. The theorem represents the birth of the Chaining method, which bridges geometry and probability to control the global behavior of random fluctuations.

🏷️ Complexity and Metric Entropy

To bound a stochastic process $\{X_t{\}}_{t\in T}$, we must measure how “large” the index set $T$ is relative to the process’s fluctuations.

Definitions

• Canonical Metric: For a process $X_t$, we define a natural metric $d(t,s)=\Vert X_t-X_s{\Vert }_{{\psi }_2}$ (the sub-Gaussian norm of the increment).
• Covering Number ($N(T,d,ϵ)$): The minimum number of balls of radius $ϵ$ required to cover $T$.
• Metric Entropy: The quantity $\log N(T,d,ϵ)$. It measures the “bits of information” needed to resolve the set $T$ at scale $ϵ$.

🏷️ The Chaining Mechanism

Dudley’s insight (Dudley, 1967) was that a process can be decomposed into a series of approximations at different scales. Instead of looking at a single point, we “chain” together a sequence of increasingly refined points $t_0,t_1,t_2,\dots$ that converge to any $t\in T$.

1. Multi-Scale View: At each level $k$, we approximate $T$ with a finite net ${\mathcal{N}}_k$ of size $N(T,d,2^{-k})$.

2. Path Decomposition: Any $X_t$ can be written as a telescoping sum:

   $$X_t=X_{t_0}+\sum _{k=1}^{\infty }(X_{t_k}-X_{t_{k-1}})$$

   where $t_k$ is the closest point to $t$ in the $k$-th net.

3. Control: By bounding the fluctuations of the increments $(X_{t_k}-X_{t_{k-1}})$ and using a union bound over the nets, we control the total path.

🏷️ Main Theorem and Proof

Dudley’s Entropy Bound

Let $\{X_t{\}}_{t\in T}$ be a centered sub-Gaussian process with respect to a metric $d$. Then:

$$\mathbb{E}\underset{t\in T}{\sup }{X}_t\le C{\int }_0^{\text{diam}(T)}\sqrt{\log N(T,d,ϵ)}dϵ$$

where $C$ is a universal constant.

Proof: The Convergence of Chains

The proof formalizes the multi-scale decomposition using a Union Bound over each scale of the chain.

Incremental Error: At scale $k$, the distance between $t_k$ and $t_{k-1}$ is at most ${ϵ}_k+{ϵ}_{k-1}\approx 3\cdot 2^{-k}$. For a sub-Gaussian process, the probability of a large increment is $P(|X_{t_k}-X_{t_{k-1}}|>u)\le 2\exp (-u^2/2{ϵ}_k^2)$.

Union Bound: The number of possible pairs $(t_k,t_{k-1})$ is bounded by the size of the nets $|{\mathcal{N}}_k|\cdot |{\mathcal{N}}_{k-1}|\le N_k^2$. Taking a union bound, the maximum increment at level $k$ satisfies:

$$\mathbb{E}\underset{t\in T}{\max }|X_{t_k}-X_{t_{k-1}}|\le C{ϵ}_k\sqrt{\log N_k}$$

Integration: Summing over all levels $k$:

$$\mathbb{E}\underset{t\in T}{\sup }{X}_t\le \sum _{k=1}^{\infty }\mathbb{E}\underset{t\in T}{\max }|X_{t_k}-X_{t_{k-1}}|\le C\sum _{k=1}^{\infty }{2}^{-k}\sqrt{\log N(T,d,2^{-k})}$$

This sum is a Riemann sum approximation of the integral $\int \sqrt{\log N(T,d,ϵ)}dϵ$. The convergence of the integral ensures that the process is almost surely bounded and continuous.

Lemma: Expectation of the Maximum

The transition from the Union Bound to the expectation bound $\mathbb{E}\max |X_i|\le \sigma \sqrt{2\log M}$ is a fundamental result in high-dimensional probability.

Derivation:

1. Jensen’s Inequality: For any $\lambda >0$, by the convexity of the exponential function:

$$\exp (\lambda \mathbb{E}\underset{1\le i\le M}{\max }{X}_i)\le \mathbb{E}\exp (\lambda \underset{i}{\max }{X}_i)=\mathbb{E}\underset{i}{\max }{e}^{\lambda X_i}$$

2. Union Bound on MGF: We bound the maximum by the sum:

$$\mathbb{E}\underset{i}{\max }{e}^{\lambda X_i}\le \sum _{i=1}^M\mathbb{E}{e}^{\lambda X_i}$$

3. Sub-Gaussian Assumption: By definition, $\mathbb{E}{e}^{\lambda X_i}\le e^{{\lambda }^2{\sigma }^2/2}$. Thus:

$$\exp (\lambda \mathbb{E}\max X_i)\le M{e}^{{\lambda }^2{\sigma }^2/2}$$

4. Logarithmic Bound: Taking the logarithm:

$$\mathbb{E}\max X_i\le \frac{\log M}{\lambda }+\frac{\lambda {\sigma }^2}{2}$$

5. Optimization: Minimizing with respect to $\lambda$ (setting $\lambda =\frac{\sqrt{2\log M}}{\sigma }$) yields the sharp bound:

$$\mathbb{E}\underset{1\le i\le M}{\max }{X}_i\le \sigma \sqrt{2\log M}$$

🏷️ Insights and Refinements

Slepian’s Comparison: Correlation vs. Supremum

A critical refinement of Dudley’s result is Slepian’s Lemma. It addresses the intuition that correlation between variables “shrinks” the expected maximum.

The Principle: Consider two Gaussian processes $\{X_t\}$ and $\{Y_t\}$ with identical variances $\mathbb{E}{X}_t^2=\mathbb{E}{Y}_t^2$. If the increments of $Y$ are “more spread out” than $X$, i.e., $\mathbb{E}(X_t-X_s{)}^2\le \mathbb{E}(Y_t-Y_s{)}^2$ for all $t,s$, then:

$$\mathbb{E}\underset{t\in T}{\sup }{X}_t\le \mathbb{E}\underset{t\in T}{\sup }{Y}_t$$

Intuition: Imagine $n$ identical variables. If they are i.i.d., they have the maximum “room” to fluctuate independently, leading to a large maximum ($\approx \sqrt{2\log n}$). If they are perfectly correlated ($X_1=X_2=\cdots =X_n$), they move as a single block, and the maximum is just the expectation of a single variable (zero). Slepian’s Lemma formalizes this: independence is the “worst-case” for fluctuations.

Sharpness and Generic Chaining

While Dudley’s bound is powerful, it is not always sharp. The integral captures the “average” complexity across scales but can fail for processes with “highly correlated” increments (where the entropy integral overcounts complexity).

• The Improvement: Michel Talagrand [@talagrand2014upper] refined this into Generic Chaining, replacing the entropy integral with the ${\gamma }_2$ functional.
• The Majorizing Measure Theorem: Talagrand proved that for Gaussian processes, the supremum is perfectly characterized (both upper and lower bound) by the ${\gamma }_2$ functional:

$$\frac{1}{L}{\gamma }_2(T,d)\le \mathbb{E}\underset{t\in T}{\sup }{X}_t\le L{\gamma }_2(T,d)$$

where ${\gamma }_2(T,d)=\inf {\sup }_{t\in T}{\sum }_{k=0}^{\infty }{2}^{k/2}d(t,A_k(t))$ and $A_k$ is a sequence of nested partitions of $T$. The $\inf$ is taken over all admissible sequences of partitions $({\mathcal{A}}_k{)}_{k\ge 0}$ satisfying the cardinality constraint $|{\mathcal{A}}_k|\le 2^{2^k}$. Unlike Dudley’s fixed nets, this allowing for spatially adapted resolution. It allocates more “budget” to geometrically complex regions of $T$, finding the optimal chaining tree that minimizes the total cost for the worst-case point $t$.

Applications in Learning Theory

In machine learning (as seen in on improved Nyström bounds), Dudley’s theorem is used to bound the Rademacher Complexity of function classes.

• If a function class has a small metric entropy (e.g., its “effective dimension” is small), then it will generalize well because its random fluctuations (noise) are constrained by the integral.
• This links directly to the spectral decay of kernels; rapid decay in eigenvalues often implies a rapidly shrinking metric entropy (see also [@vershynin2018high]).

📝 Notes

• The “Diam(T)” limit in the integral can often be replaced by the scale where the covering number becomes 1.
• This technique shares the “log-summation” logic found in on Moser iteration, where a sequence of geometrically improving bounds is summed to reach a global limit.

🔗 See Also

• on Slepian’s lemma and Gaussian comparison --- Comparison inequalities provide the fundamental lower bounds for metric entropy that establish the sharpness of the chaining upper bound.
• on improved Nyström bounds --- The complexity of the kernel space, which determines the Nyström error, is quantified by the same metric entropy used in Dudley’s bound.
• on eigenvalue estimate of kernel --- Covering numbers and eigenvalues are dual views of set complexity (Carl’s Inequality).
• on sum-product in finite fields via entropy --- The entropy framework in combinatorics uses similar “information bits” logic to bound set expansion.

📚 References

🐻  Dudley, R.M. 1967. The sizes of compact subsets of Hilbert space and continuity of Gaussian processes. Journal of Functional Analysis 1(3), 290–330.