Lecture 17: Applications of Dudley’s Inequality
Uniform laws of large numbers and the continuity of Brownian motion
Dudley’s inequality asks nothing of a process beyond sub-Gaussian increments and a metric with computable covering numbers. This lecture exploits that generality in two directions. The first is statistical: the empirical average of a function class, over all functions in the class at once, is close to the true average, and the price of uniformity is an entropy integral over the class. The second is analytic: a process whose increments are Hölder in the \(\psi_2\) norm has Hölder continuous sample paths, and the exponent lost in the passage is as small as one likes. Brownian motion is the canonical example of both the hypothesis and the conclusion.
1 Empirical processes
Let \(Y,Y_1,\ldots,Y_n\) be i.i.d. random variables with values in a set \(\mathcal Y\), and let \(\mathcal F\) be a class of functions \(f:\mathcal Y\to\mathbb R\). The law of large numbers says that for each fixed \(f\), \[ \frac1n\sum_{i=1}^nf(Y_i)\longrightarrow\mathbb Ef(Y). \] A uniform law of large numbers for \(\mathcal F\) is a bound on \[ \mathbb E\sup_{f\in\mathcal F}\Big|\frac1n\sum_{i=1}^nf(Y_i)-\mathbb Ef(Y)\Big| . \] Such bounds are the basic tool of statistical learning: a learning algorithm chooses \(f\) after seeing the data, so the ordinary law of large numbers, which fixes \(f\) in advance, does not apply to the chosen \(f\). A uniform bound does.
The centered and normalized process \[ X_f:=\frac1{\sqrt n}\sum_{i=1}^n\big(f(Y_i)-\mathbb Ef(Y)\big), \qquad f\in\mathcal F, \] is called the empirical process indexed by \(\mathcal F\).
Lemma 1 (The empirical process is sub-Gaussian) For all \(f,g\in\mathcal F\) with \(\|f-g\|_\infty<\infty\), \[ \|X_f-X_g\|_{\psi_2}\leq2\|f-g\|_\infty . \] So the empirical process is sub-Gaussian with respect to the metric \(d(f,g)=2\|f-g\|_\infty\).
Write \(h=f-g\). Then \(X_f-X_g=n^{-1/2}\sum_i(h(Y_i)-\mathbb Eh(Y))\) is a sum of \(n\) independent, mean-zero variables, each taking values in an interval of length at most \(2\|h\|_\infty\). By Hoeffding’s lemma of Lecture 4 each summand is \(\|h\|_\infty^2\)-subgaussian, so by the Pythagorean theorem of Lecture 5 the sum is \(n\|h\|_\infty^2\)-subgaussian, and after dividing by \(\sqrt n\) the increment is \(\|h\|_\infty^2\)-subgaussian. The sub-Gaussian–\(\psi_2\) comparison of Lecture 5 gives the claim.
Dudley’s inequality now applies verbatim.
Theorem 1 (Uniform law of large numbers via entropy) Let \(\mathcal F\) be a class of functions that is bounded and separable in the supremum norm. Then \[ \mathbb E\sup_{f\in\mathcal F}\Big|\frac1n\sum_{i=1}^nf(Y_i)-\mathbb Ef(Y)\Big| \leq\frac C{\sqrt n}\Big[\int_0^\infty\sqrt{\log N(\mathcal F,\|\cdot\|_\infty,\varepsilon)}\,d\varepsilon+\sup_{f\in\mathcal F}\|f\|_\infty\Big]. \]
Fix \(f_0\in\mathcal F\). By Lemma 1 and the tail form of Dudley’s inequality (Lecture 16), integrated in \(u\), \[ \mathbb E\sup_{f\in\mathcal F}|X_f-X_{f_0}|\leq C\int_0^\infty\sqrt{\log N(\mathcal F,\|\cdot\|_\infty,\varepsilon)}\,d\varepsilon , \] where the factor \(2\) in the metric has been absorbed into \(C\). The base point contributes \(\mathbb E|X_{f_0}|\leq(\mathbb EX_{f_0}^2)^{1/2}\leq\|f_0\|_\infty\). Adding the two and dividing by \(\sqrt n\) gives the claim, since the empirical average deviation is \(X_f/\sqrt n\).
The theorem separates two effects. The factor \(n^{-1/2}\) is the rate of the ordinary law of large numbers, and the bracket is the price of uniformity, a fixed number depending only on the class. The next example computes the price for a natural class.
1.1 Lipschitz functions on an interval
Let \(Y\) take values in \([0,1]\) and let \[ \mathcal F_L:=\big\{f:[0,1]\to\mathbb R:\ \|f\|_{\mathrm{Lip}}\leq L\big\}. \] Adding a constant to \(f\) does not change the deviation \(\frac1n\sum_if(Y_i)-\mathbb Ef(Y)\), so we may restrict to \(f(0)=0\), which forces \(\|f\|_\infty\leq L\).
Lemma 2 (Entropy of Lipschitz functions) Let \(\mathcal F_L^0:=\{f\in\mathcal F_L:f(0)=0\}\). Then for every \(\varepsilon>0\), \[ \log N(\mathcal F_L^0,\|\cdot\|_\infty,\varepsilon)\leq\frac{CL}\varepsilon . \]
By scaling, take \(L=1\). Fix \(\delta>0\) and the grid points \(x_k=k\delta\) for \(0\leq k\leq1/\delta\). Given \(f\in\mathcal F_1^0\), let \(g\) be the piecewise linear function on the grid whose value at \(x_k\) is the nearest point of \((\delta/2)\mathbb Z\) to \(f(x_k)\), with \(g(0)=0\). Then \(|g(x_k)-f(x_k)|\leq\delta/4\), and since \(|f(x_{k+1})-f(x_k)|\leq\delta\), the increment \(g(x_{k+1})-g(x_k)\) lies in \((\delta/2)\mathbb Z\) and has absolute value at most \(3\delta/2\), leaving \(7\) possibilities at each step. So there are at most \(7^{1/\delta}\) functions \(g\). For \(x\in[x_k,x_{k+1}]\), \[ |f(x)-g(x)|\leq|f(x)-f(x_k)|+|f(x_k)-g(x_k)|+|g(x_k)-g(x)|\leq\delta+\frac\delta4+\frac{3\delta}2\leq3\delta . \] Thus \(\mathcal F_1^0\) is covered by \(7^{1/\delta}\) balls of radius \(3\delta\) centered at functions \(g\), which need not lie in \(\mathcal F_1^0\); replacing each center by a point of \(\mathcal F_1^0\) in its ball doubles the radius. Taking \(\varepsilon=6\delta\) gives \(\log N(\mathcal F_1^0,\|\cdot\|_\infty,\varepsilon)\leq(6\log7)/\varepsilon\).
The picture behind the proof is the one in the handwritten notes: a \(1\)-Lipschitz path through a grid of boxes of side \(\delta\) enters, at each step, one of a bounded number of neighboring boxes, and the path is determined up to \(O(\delta)\) by the sequence of boxes.
Corollary 1 (Uniform law of large numbers for Lipschitz functions) For every \(L>0\) and every \(n\geq1\), \[ \mathbb E\sup_{f\in\mathcal F_L}\Big|\frac1n\sum_{i=1}^nf(Y_i)-\mathbb Ef(Y)\Big|\leq\frac{CL}{\sqrt n}. \]
Apply Theorem 1 to \(\mathcal F_L^0\), whose diameter in the supremum norm is at most \(2L\), so the entropy integral runs over \([0,2L]\): \[ \int_0^{2L}\sqrt{\frac{CL}\varepsilon}\,d\varepsilon=\sqrt{CL}\cdot2\sqrt{2L}=C'L , \qquad \sup_{f\in\mathcal F_L^0}\|f\|_\infty\leq L . \]
So the empirical average of a Lipschitz function converges at the parametric rate \(n^{-1/2}\) uniformly over the whole class, with the Lipschitz constant as the only price. The entropy integral converged because \(\sqrt{1/\varepsilon}\) is integrable at \(0\): the class is “small” in exactly the sense that matters for Dudley.
For Lipschitz functions on \([0,1]^d\) the same box-counting argument gives \(\log N(\mathcal F,\|\cdot\|_\infty,\varepsilon)\leq C_d/\varepsilon^d\), and \(\sqrt{\varepsilon^{-d}}\) is not integrable at \(0\) once \(d\geq2\). Dudley’s inequality then gives nothing, although the uniform law of large numbers is true, with the slower rate \(n^{-1/d}\) for \(d\geq3\). The supremum norm is the wrong metric: two functions that differ on a tiny region are far apart in \(\|\cdot\|_\infty\) but produce nearly identical empirical averages. The right metric is the empirical \(L^2\) distance \[ d_n(f,g)^2=\frac1n\sum_{i=1}^n\big(f(Y_i)-g(Y_i)\big)^2 , \] in which the increments are still sub-Gaussian conditionally on the sample, and the covering numbers are much smaller. Problem 1 of Exercise Sheet 4 is a first step in this direction: it shows that covering numbers in \(L^2\) of the population measure are preserved by sampling. Carrying this program through leads to the theory of Vapnik–Chervonenkis classes, which we do not develop.
2 Continuity of sample paths
The second application uses Dudley’s inequality not for its numerical bound but for its uniformity in the index. A process indexed by an interval is a random function, and Dudley controls its oscillation over sub-intervals of every length at once.
Theorem 2 (Hölder continuity criterion) Let \((X_t)_{t\in[0,1]}\) be a centered process and suppose there are \(\beta\in(0,1]\) and \(M>0\) such that \[ \|X_t-X_s\|_{\psi_2}\leq M|t-s|^\beta \qquad\text{for all }s,t\in[0,1]. \] Then for every \(\alpha<\beta\) there is a constant \(C_{\alpha,\beta}\) such that \[ \mathbb E\sup_{s\neq t}\frac{|X_t-X_s|}{|t-s|^\alpha}\leq C_{\alpha,\beta}M , \] the supremum being over \(s,t\) in a countable dense subset of \([0,1]\). In particular \(X\) has a version with \(\alpha\)-Hölder continuous sample paths.
Take \(M=1\) by scaling, and let \(D\) be a countable dense subset of \([0,1]\) containing the dyadic rationals. The process is sub-Gaussian with respect to \(d(s,t)=|t-s|^\beta\).
Step 1: one dyadic interval. Let \(I\) be a dyadic interval of length \(2^{-k}\). Its \(d\)-diameter is \(2^{-k\beta}\), and \(N(I,d,\varepsilon)=N(I,|\cdot|,\varepsilon^{1/\beta})\leq2^{-k}\varepsilon^{-1/\beta}+1\). Substituting \(\varepsilon=2^{-k\beta}\eta\), \[ \int_0^{2^{-k\beta}}\sqrt{\log N(I,d,\varepsilon)}\,d\varepsilon =2^{-k\beta}\int_0^1\sqrt{\log\big(\eta^{-1/\beta}+1\big)}\,d\eta \leq C_\beta2^{-k\beta}. \] By the tail form of Dudley’s inequality (Lecture 16) applied to the process on \(I\cap D\), for every \(v\geq0\), \[ \mathbb P\Big\{\sup_{s,t\in I\cap D}|X_t-X_s|\geq C_\beta2^{-k\beta}(1+v)\Big\}\leq2e^{-v^2}. \]
Step 2: all dyadic intervals at once. There are \(2^k\) dyadic intervals of length \(2^{-k}\). Take \(v=v_k:=\sqrt{2k}+u\) with \(u\geq0\); then \(2^k\cdot2e^{-v_k^2}\leq2e^{-u^2}e^{-k}\), and summing over \(k\geq0\) the probability that some dyadic interval of some length violates its bound is at most \(4e^{-u^2}\).
Step 3: from dyadic intervals to all pairs. On the good event, let \(s<t\) in \(D\) and choose \(k\) with \(2^{-k-1}<t-s\leq2^{-k}\). The points \(s\) and \(t\) lie in the same or in two adjacent dyadic intervals of length \(2^{-k}\), so by the triangle inequality across the shared endpoint, \[ |X_t-X_s|\leq2C_\beta2^{-k\beta}\big(1+\sqrt{2k}+u\big) \leq4C_\beta(t-s)^\beta\Big(1+\sqrt{2\log_2\tfrac1{t-s}}+u\Big). \] Since \(\alpha<\beta\), \((t-s)^{\beta-\alpha}\sqrt{\log_2(1/(t-s))}\) is bounded on \((0,1]\) by a constant \(C'_{\alpha,\beta}\), and hence \[ \sup_{s\neq t}\frac{|X_t-X_s|}{|t-s|^\alpha}\leq C_{\alpha,\beta}(1+u) \] with probability at least \(1-4e^{-u^2}\). Integrating in \(u\) gives the expectation bound.
Step 4: the version. On the almost sure event where the Hölder quotient is finite, \(t\mapsto X_t\) is uniformly continuous on \(D\) and so extends uniquely to an \(\alpha\)-Hölder function on \([0,1]\). Since \(X_{t_k}\to X_t\) in probability as \(t_k\to t\) by the increment hypothesis, the extension agrees with \(X_t\) almost surely at each \(t\), so it is a version of the process.
The proof is chaining at the level of intervals: Dudley handles each dyadic interval, and a union bound with a slowly growing \(v_k\) handles the scales. The loss from \(\beta\) to \(\alpha<\beta\) comes entirely from the \(\sqrt{\log}\) factor in Step 3, which is the cost of the union bound over \(2^k\) intervals. It cannot be removed in general, as the next example shows.
Corollary 2 (Brownian motion is Hölder continuous) Let \((B_t)_{t\in[0,1]}\) be Brownian motion, the centered Gaussian process with covariance \(\min\{s,t\}\) from Lecture 10. Then \(B\) has a version whose sample paths are \(\alpha\)-Hölder continuous for every \(\alpha<\tfrac12\).
\(B_t-B_s\sim N(0,|t-s|)\), so \(\|B_t-B_s\|_{\psi_2}\leq2|t-s|^{1/2}\) by the sub-Gaussian–\(\psi_2\) comparison. Apply Theorem 2 with \(\beta=\tfrac12\) and every \(\alpha<\tfrac12\); a single version works for all \(\alpha\) by taking a sequence \(\alpha_j\uparrow\tfrac12\) and intersecting the almost sure events.
The exponent \(\tfrac12\) itself is not attained. Lévy’s modulus of continuity states that \[ \limsup_{h\downarrow0}\ \sup_{|t-s|\leq h}\frac{|B_t-B_s|}{\sqrt{2h\log(1/h)}}=1 \qquad\text{almost surely}, \] so the paths oscillate by \(\sqrt{2h\log(1/h)}\) over intervals of length \(h\), which is the bound of Step 3 with \(\beta=\tfrac12\) and the logarithm kept. Dudley’s argument, applied with care, is sharp for Brownian motion.
The criterion is a statement about the growth of increments in the \(\psi_2\) norm. Consider the isonormal process on \(H=L^2[0,1]\) from Lecture 10 and the process \(X_t=g(\mathbb 1_{[0,t]})\): this is Brownian motion, and its increments satisfy \(\|X_t-X_s\|_{L^2}=|t-s|^{1/2}\). The two-dimensional Gaussian free field is the Gaussian process on a planar domain whose covariance kernel is \(-\log|t-s|\) up to a bounded function. The kernel diverges on the diagonal, so the variance at a point is infinite and there is no process \(X_t\) to which a criterion of this kind could apply: the field exists only after integrating against test functions, as a random distribution, exactly as the isonormal process \(g(h)\) exists for \(h\in L^2\) but \(g(\delta_t)\) does not. The Hölder criterion marks the boundary between processes that are random functions and processes that are not.
3 Where we go next
Both applications used Dudley’s inequality as a black box, with the whole argument in the computation of covering numbers. The next two lectures return to the inequality itself. Dudley uses one net at each scale for every point of \(T\), and the Talagrand and \(\ell^1\)-ball examples of Lecture 16 showed that this is wasteful when the geometry of \(T\) varies from place to place. Generic chaining lets the nets adapt, and for Gaussian processes the resulting functional \(\gamma_2(T,d)\) is equivalent to \(\mathbb E\sup X\) up to absolute constants, closing the gap between Sudakov and Dudley.