Lecture 16: Dudley’s Entropy Integral
Chaining, sub-Gaussian processes, and the limits of metric entropy
Sudakov’s minoration, proved in Lecture 12, bounds the expected supremum of a Gaussian process from below by the metric entropy of its index set at a single scale. This lecture proves the matching upper bound, Dudley’s inequality, which integrates the entropy over all scales. The proof is chaining, a multiscale version of the net arguments used since Lecture 8, and it applies to a class of processes much wider than Gaussian ones: all that is needed is a sub-Gaussian bound on increments. The lecture ends with examples showing where the entropy integral is sharp and where it is not. The gap it leaves is the subject of the generic chaining lectures.
1 Sub-Gaussian processes
Definition 1 (Sub-Gaussian process) Let \((T,d)\) be a metric space. A centered process \((X_t)_{t\in T}\) is sub-Gaussian with respect to \(d\) if \[ \|X_t-X_s\|_{\psi_2}\leq d(t,s) \qquad\text{for all }s,t\in T . \]
If the increments satisfy \(\|X_t-X_s\|_{\psi_2}\leq Kd(t,s)\) instead, the process is sub-Gaussian with respect to \(Kd\), and every bound below scales by \(K\). The metric need not be the canonical one; any metric dominating the \(\psi_2\) distance will do, at the cost of larger covering numbers.
Gaussian processes. If \((X_t)\) is centered Gaussian with canonical metric \(d\), then \(X_t-X_s\sim N(0,d(t,s)^2)\), and the sub-Gaussian–\(\psi_2\) comparison of Lecture 5 gives \(\|X_t-X_s\|_{\psi_2}\leq2d(t,s)\). So a Gaussian process is sub-Gaussian with respect to \(2d\).
Rademacher processes. Let \(\varepsilon_1,\ldots,\varepsilon_n\) be independent random signs and \(T\subseteq\mathbb R^n\). The process \(X_t=\sum_i\varepsilon_it_i\) has increments \(\sum_i\varepsilon_i(t_i-s_i)\), which are \(\|t-s\|_2^2\)-subgaussian by the Pythagorean theorem of Lecture 5, so the process is sub-Gaussian with respect to \(2\|t-s\|_2\). Its expected supremum is the Rademacher complexity of \(T\), mentioned in Lecture 3.
Empirical processes. Let \(Y_1,\ldots,Y_n\) be i.i.d. in a space \(\mathcal Y\) and let \(\mathcal F\) be a class of functions \(f:\mathcal Y\to[-1,1]\). The process \[ X_f:=\frac1{\sqrt n}\sum_{i=1}^n\big(f(Y_i)-\mathbb Ef(Y_i)\big) \] has increments that are sums of independent bounded variables, so by Hoeffding’s lemma of Lecture 4 it is sub-Gaussian with respect to \(C\|f-g\|_\infty\). Sharper metrics, such as the \(L^2\) distance under the law of \(Y_1\), are available with more work.
Two facts about finitely many sub-Gaussian variables drive the proof.
Lemma 1 (Maximum of finitely many sub-Gaussian variables) Let \(Y_1,\ldots,Y_N\) be random variables with \(\|Y_i\|_{\psi_2}\leq L\), \(N\geq2\). Then for every \(u\geq0\), \[ \mathbb P\Big\{\max_{i\leq N}|Y_i|\geq L\big(\sqrt{\log N}+u\big)\Big\}\leq2e^{-u^2}, \qquad \mathbb E\max_{i\leq N}|Y_i|\leq CL\sqrt{\log N}. \]
By the Markov direction of the equivalence theorem of Lecture 5, \(\mathbb P\{|Y_i|\geq s\}\leq2e^{-s^2/L^2}\). A union bound at \(s=L(\sqrt{\log N}+u)\) gives, using \((\sqrt{\log N}+u)^2\geq\log N+u^2\), \[ \mathbb P\Big\{\max_i|Y_i|\geq s\Big\}\leq2Ne^{-\log N-u^2}=2e^{-u^2}. \] For the expectation, integrate the tail: \(\mathbb E\max_i|Y_i|\leq L\sqrt{\log N}+L\int_0^\infty2e^{-u^2}\,du\leq L(\sqrt{\log N}+\sqrt\pi)\), and \(\sqrt\pi\leq3\sqrt{\log2}\leq3\sqrt{\log N}\).
2 Dudley’s inequality
For a metric space \((T,d)\) recall the covering number \(N(T,d,\varepsilon)\) from Lecture 1, with centers in \(T\). It equals \(1\) once \(\varepsilon\geq\operatorname{diam}(T)\), so the integrals below are really over \([0,\operatorname{diam}(T)]\).
Theorem 1 (Dudley’s inequality) Let \((X_t)_{t\in T}\) be a centered process, sub-Gaussian with respect to a metric \(d\) for which \((T,d)\) is separable. Then \[ \mathbb E\sup_{t\in T}X_t\leq C\int_0^\infty\sqrt{\log N(T,d,\varepsilon)}\,d\varepsilon , \] and for every \(u\geq0\), with probability at least \(1-2e^{-u^2}\), \[ \sup_{s,t\in T}|X_t-X_s|\leq C\Big[\int_0^\infty\sqrt{\log N(T,d,\varepsilon)}\,d\varepsilon+u\operatorname{diam}(T)\Big]. \]
The proof is a walk. Fix a base point \(t_0\) and, for each \(t\), a chain of approximations \(\pi_{k_0}(t)=t_0,\pi_{k_0+1}(t),\pi_{k_0+2}(t),\ldots\) drawn from nets of \(T\) at the dyadic scales \(2^{-k}\), converging to \(t\). The increment \(X_t-X_{t_0}\) is the sum of the increments along the chain. At scale \(k\) there are only \(N(T,d,2^{-k})^2\) possible links, each an increment of \(\psi_2\) norm at most \(2^{-k+2}\), so a union bound controls all links at that scale by \(2^{-k}\sqrt{\log N(T,d,2^{-k})}\), and summing over \(k\) gives a Riemann sum for the entropy integral. The single-scale net argument of Lecture 8 stopped after one step and could not control the remainder \(X_t-X_{\pi(t)}\) uniformly in \(t\); chaining simply keeps going.
Step 0: reductions. It suffices to treat finite \(T\). For separable \((T,d)\) and the supremum convention of Lecture 10, applied along a countable dense subset, \(\sup_TX\) is the increasing limit of suprema over finite subsets \(T'\subseteq T\), so the expectation bound follows by monotone convergence and the tail bound by passing to the limit in the events. The covering numbers of a subset are controlled by those of \(T\): covering \(T\) by \(N(T,d,\varepsilon/2)\) balls of radius \(\varepsilon/2\) and picking a point of \(T'\) in each ball that meets \(T'\) gives \(N(T',d,\varepsilon)\leq N(T,d,\varepsilon/2)\), and the change of variable \(\varepsilon\mapsto\varepsilon/2\) costs a factor \(2\) in the integral.
So let \(T\) be finite, with \(D:=\operatorname{diam}(T)\). Let \(k_0\) be the integer with \(2^{-k_0-1}<D\leq2^{-k_0}\), and for \(k\geq k_0\) let \(T_k\subseteq T\) be a \(2^{-k}\)-net of \(T\) with \(|T_k|=N_k:=N(T,d,2^{-k})\). We may take \(T_{k_0}=\{t_0\}\), and since \(T\) is finite, \(T_k=T\) for all large \(k\). For \(t\in T\) let \(\pi_k(t)\in T_k\) be a nearest point, so \(d(t,\pi_k(t))\leq2^{-k}\) and \(\pi_k(t)=t\) for large \(k\).
Step 1: the chain. For every \(t\in T\), \[ X_t-X_{t_0}=\sum_{k>k_0}\big(X_{\pi_k(t)}-X_{\pi_{k-1}(t)}\big), \] a finite sum since the terms vanish once \(\pi_k(t)=t\). Each link joins two points at distance \[ d\big(\pi_k(t),\pi_{k-1}(t)\big)\leq d(\pi_k(t),t)+d(t,\pi_{k-1}(t))\leq2^{-k}+2^{-k+1}\leq2^{-k+2}, \] so \(\|X_{\pi_k(t)}-X_{\pi_{k-1}(t)}\|_{\psi_2}\leq2^{-k+2}\). As \(t\) ranges over \(T\), the pair \((\pi_k(t),\pi_{k-1}(t))\) ranges over a set of at most \(N_kN_{k-1}\leq N_k^2\) pairs.
Step 2: each scale. Apply Lemma 1 at scale \(k\) to the at most \(N_k^2\) variables \(X_a-X_b\), \((a,b)\) a possible link, with \(L=2^{-k+2}\). For \(u_k\geq0\), \[ \mathbb P\Big\{\sup_{t\in T}\big|X_{\pi_k(t)}-X_{\pi_{k-1}(t)}\big|\geq2^{-k+2}\big(\sqrt{2\log N_k}+u_k\big)\Big\}\leq2e^{-u_k^2}, \] when \(N_k\geq2\); when \(N_k=1\) the link is trivial and the event is empty.
Step 3: summing the scales. Take \(u_k:=u+\sqrt{k-k_0}\). The failure probabilities sum to at most \(\sum_{j\geq1}2e^{-(u+\sqrt j)^2}\leq2e^{-u^2}\sum_{j\geq1}e^{-j}\leq2e^{-u^2}\). On the complementary event, for every \(t\), \[ |X_t-X_{t_0}|\leq\sum_{k>k_0}2^{-k+2}\Big(\sqrt{2\log N_k}+u+\sqrt{k-k_0}\Big) \leq4\sqrt2\sum_{k>k_0}2^{-k}\sqrt{\log N_k}+4\cdot2^{-k_0}\big(u+2\big), \] using \(\sum_{j\geq1}2^{-j}\sqrt j\leq2\). Since \(2^{-k_0}<2D\), the last term is at most \(8D(u+2)\), and \(16D\leq16\cdot2\int_0^{D/2}d\varepsilon\) can be absorbed into the entropy integral because \(\log N(T,d,\varepsilon)\geq\log2\) for \(\varepsilon<D/2\) (two points at distance \(D\) cannot share a ball of radius less than \(D/2\)). Applying the bound to \(s\) and \(t\) and using the triangle inequality gives the tail bound with the dyadic sum in place of the integral.
Step 4: from the sum to the integral. For each \(k\), \(2^{-k}=2\int_{2^{-k-1}}^{2^{-k}}d\varepsilon\), and on that interval \(N(T,d,\varepsilon)\geq N_k\) since \(\varepsilon\leq2^{-k}\). Hence \[ \sum_{k>k_0}2^{-k}\sqrt{\log N_k}\leq2\sum_{k>k_0}\int_{2^{-k-1}}^{2^{-k}}\sqrt{\log N(T,d,\varepsilon)}\,d\varepsilon\leq2\int_0^\infty\sqrt{\log N(T,d,\varepsilon)}\,d\varepsilon . \]
Step 5: the expectation. Since \(\mathbb EX_{t_0}=0\), \(\mathbb E\sup_tX_t=\mathbb E\sup_t(X_t-X_{t_0})\leq\mathbb E\sup_t|X_t-X_{t_0}|\), and integrating the tail bound over \(u\) gives the claim.
The hypothesis \(\mathbb EX_t=0\) is used only in the last step; the tail bound on \(\sup|X_t-X_s|\) needs no centering. For a Gaussian process the metric is the canonical one up to the factor \(2\), and the theorem says \[ c\,\sup_{\varepsilon>0}\varepsilon\sqrt{\log N(T,d,\varepsilon)} \leq\mathbb E\sup_{t\in T}X_t \leq C\int_0^\infty\sqrt{\log N(T,d,\varepsilon)}\,d\varepsilon , \] the left side being Sudakov’s minoration. The lower bound is the largest rectangle under the graph of \(\varepsilon\mapsto\sqrt{\log N(T,d,\varepsilon)}\) and the upper bound is the area under it. When the graph is roughly a hyperbola \(\varepsilon^{-1}\) the two differ by a logarithm, and the examples below show that the gap is real.
3 Where the entropy integral is sharp
The Euclidean ball. For \(T=B_2^n\) with the Gaussian width process, the volumetric bound of Lecture 1 gives \(N(T,\varepsilon)\leq(3/\varepsilon)^n\) for \(\varepsilon\leq1\), so \[ \int_0^2\sqrt{\log N(T,\varepsilon)}\,d\varepsilon\leq\sqrt n\int_0^1\sqrt{\log(3/\varepsilon)}\,d\varepsilon+\sqrt{\log2}\leq C\sqrt n , \] the integral converging because \(\sqrt{\log(3/\varepsilon)}\) is integrable at \(0\). Since \(w(B_2^n)=\mathbb E\|g\|_2\asymp\sqrt n\), Dudley’s bound is sharp up to the constant.
Sparse vectors. For \(T=U_s\), the \(s\)-sparse vectors in the unit ball, \(U_s\) is a union of \(\binom ns\) balls of dimension \(s\), so \(N(U_s,\varepsilon)\leq\binom ns(3/\varepsilon)^s\leq(en/s)^s(3/\varepsilon)^s\) and \[ \int_0^2\sqrt{\log N(U_s,\varepsilon)}\,d\varepsilon \leq\int_0^1\Big(\sqrt{s\log(en/s)}+\sqrt{s\log(3/\varepsilon)}\Big)d\varepsilon+\sqrt{\log2} \leq C\sqrt{s\log(en/s)} . \] This matches the width computed in Lecture 13, so Dudley is sharp here too, and it recovers the sparse-width bound of Exercise Sheet 3 by a different route. The subadditivity of \(\sqrt{a+b}\leq\sqrt a+\sqrt b\) is what lets the two sources of entropy, the choice of support and the ball within it, be integrated separately.
Let \(G\) be a Gaussian tensor with independent \(N(0,1)\) entries indexed by \(\{1,\ldots,d\}^p\), and for \(u\in S^{d-1}\) let \(X_u:=\langle G,u^{\otimes p}\rangle\). By the tensor identity of Lecture 15, \(\mathbb EX_uX_v=\langle u,v\rangle^p\), so \(\operatorname{Var}X_u=1\) and \[ d(u,v)^2=2\big(1-\langle u,v\rangle^p\big). \] For \(p=2\), \(X_u=\langle Gu,u\rangle\) is a quadratic form and \(\sup_uX_u\) is the largest eigenvalue of \((G+G^{\mathsf T})/2\), of order \(\sqrt d\). For larger \(p\) the metric changes character: \(d(u,v)\leq\varepsilon\) forces \(\langle u,v\rangle^p\geq1-\varepsilon^2/2\), hence \(\|u-v\|_2\lesssim\varepsilon/\sqrt p\), so \(N(T,d,\varepsilon)\approx N(S^{d-1},\varepsilon/\sqrt p)\) and the entropy integral is \[ \int_0^{\sqrt2}\sqrt{d\log(C\sqrt p/\varepsilon)}\,d\varepsilon\asymp\sqrt{d\log p} \qquad(p\geq2). \] Sudakov at \(\varepsilon=1\) gives the same order from below, since a \(1\)-separated set in \(d\) is a \(\sqrt{(2\log2)/p}\)-separated set on the sphere, and a maximal such subset of a hemisphere, which avoids antipodal pairs, has \(p^{cd}\) points by the volume argument of Lecture 1. So \(\mathbb E\sup_uX_u\asymp\sqrt{d\log p}\) for \(2\leq p\leq e^d\), both bounds are sharp, and the supremum genuinely grows with \(p\) at fixed \(d\): the process decorrelates faster on the sphere as \(p\) grows, and more of the \(\sqrt{2\log(\text{number of points})}\) behavior of independent Gaussians appears.
4 Where it is not
Let \(T=\{t_n:n\geq1\}\subseteq\ell^2\) with \(t_n=e_n/\sqrt{1+\log n}\), and let \(X_{t}=g(t)\) be the isonormal process of Lecture 10 restricted to \(T\). Then \(X_{t_n}=Z_n/\sqrt{1+\log n}\) for i.i.d. standard Gaussians \(Z_n\).
The supremum is finite. For \(s>\sqrt2\), \[ \mathbb P\Big\{\sup_nX_{t_n}\geq s\Big\}\leq\sum_{n\geq1}\mathbb P\{Z_n\geq s\sqrt{1+\log n}\} \leq\sum_{n\geq1}e^{-s^2(1+\log n)/2}=e^{-s^2/2}\sum_{n\geq1}n^{-s^2/2}<\infty , \] and the sum decays in \(s\) fast enough that \(\mathbb E\sup_nX_{t_n}<\infty\).
The entropy integral is infinite. For \(m<n\), \[ d(t_m,t_n)^2=\|t_m-t_n\|_2^2=\frac1{1+\log m}+\frac1{1+\log n}\geq\frac2{1+\log n}, \] so the first \(n\) points are \(\varepsilon\)-separated as long as \(2/(1+\log n)\geq\varepsilon^2\), that is \(n\leq e^{2/\varepsilon^2-1}\). Hence \(\log N(T,d,\varepsilon/2)\geq2/\varepsilon^2-1\), and \(\sqrt{\log N(T,d,\varepsilon)}\gtrsim1/\varepsilon\) for small \(\varepsilon\), which is not integrable at \(0\).
The covering numbers grow like \(\exp(c/\varepsilon^2)\), which is the critical rate: a hair slower and Dudley converges, as for the Euclidean ball. What Dudley cannot see is that the points that force the large covering numbers, the \(t_n\) with \(n\) large, contribute almost nothing to the supremum because their variances \(1/(1+\log n)\) are tiny. Entropy counts points; it does not weigh them.
A second, more elementary failure is worth recording. For \(T=B_1^n\) the width is \(\mathbb E\|g\|_\infty\asymp\sqrt{\log n}\), while the covering numbers of Lecture 2 give an entropy integral of order \(\sqrt{\log n}\cdot\log n\) once the scales below \(n^{-1/2}\) are included. Dudley’s bound is off by a logarithm. Sudakov, on the other hand, is sharp for \(B_1^n\), so the truth sits at the lower bound. For the sparse vectors it sat at the upper bound. Neither inequality can be the whole story.
5 Where we go next
Dudley’s inequality is a tool of enormous reach. The next lecture applies it to empirical processes, proving a uniform law of large numbers over a class of Lipschitz functions and the continuity of Brownian motion. After that, Talagrand’s generic chaining closes the gap exposed in this lecture: it replaces the entropy integral, which uses the same net at every point of \(T\), by a functional that lets the nets adapt to the geometry, and for Gaussian processes it is sharp in both directions.