Lecture 18: Generic Chaining
Talagrand’s \(\gamma_2\) functional and the majorizing measure theorem
Dudley’s inequality bounds the supremum of a sub-Gaussian process by an entropy integral, and Lecture 16 showed two ways it can fail: Talagrand’s example, where the integral diverges although the supremum is finite, and the \(\ell^1\) ball, where it is off by a logarithm. In both cases the covering numbers are the wrong bookkeeping. They count how many points are needed to approximate \(T\) at scale \(\varepsilon\) uniformly over \(T\), but different parts of \(T\) may need different resolutions at different scales. Generic chaining keeps the chaining argument and changes only the bookkeeping: instead of fixing the scales and asking how many points each needs, it fixes the number of points at each stage and asks, for each \(t\) separately, how well the stages approximate \(t\). The resulting functional \(\gamma_2(T,d)\) is never larger than Dudley’s integral, and for Gaussian processes it is the answer: it is equivalent to \(\mathbb E\sup X\) up to absolute constants.
1 Rewriting Dudley’s sum
Recall the outcome of chaining in Lecture 16. With \(\varepsilon_k=2^{-k}\) and \(T_k\) an \(\varepsilon_k\)-net of minimal size \(N_k=N(T,d,2^{-k})\), \[ \mathbb E\sup_{t\in T}X_t\leq C\sum_k2^{-k}\sqrt{\log N_k}. \] Each term is the product of a scale and the square root of a log cardinality. Turn the bookkeeping around: fix the cardinalities and let the scales adapt. A sequence of subsets \((T_k)_{k\geq0}\) of \(T\) is admissible if \[ |T_0|=1, \qquad |T_k|\leq2^{2^k}\quad(k\geq1). \] The doubly exponential growth is chosen so that \(\sqrt{\log|T_k|}\leq2^{k/2}\) grows geometrically, which is what makes the sums below converge. Given an admissible sequence, the sets \(T_k\) are nets of \(T\) at the scales \[ \varepsilon_k:=\sup_{t\in T}d(t,T_k), \qquad d(t,A):=\inf_{a\in A}d(t,a), \] and running the chaining argument with these nets gives \[ \mathbb E\sup_{t\in T}X_t\leq C\sum_{k\geq0}2^{k/2}\sup_{t\in T}d(t,T_k). \tag{1}\] Taking the infimum over admissible sequences, the right side is equivalent to Dudley’s integral up to constants (see Lemma 1 below for one direction). So far nothing has happened. The change is to move the supremum outside the sum.
Definition 1 (Talagrand’s \(\gamma_2\) functional) For a metric space \((T,d)\), \[ \gamma_2(T,d):=\inf_{(T_k)}\ \sup_{t\in T}\ \sum_{k\geq0}2^{k/2}d(t,T_k), \] the infimum over all admissible sequences.
Since \(\sup_t\sum_k\leq\sum_k\sup_t\), the functional is at most the quantity in Equation 1 for every admissible sequence, hence at most Dudley’s sum. The difference is that Dudley charges every \(t\) for the worst-approximated point at each scale, while \(\gamma_2\) charges each \(t\) only for its own approximation errors, and the worst total cost over \(t\) is what counts. In a space where the nets that serve some points well at stage \(k\) already serve other points well at all later stages, this matters.
Let \(T=\{0\}\cup\{t_n:n\geq1\}\subseteq\ell^2\) with \(t_n=e_n/\sqrt{1+\log n}\), the set of Lecture 16 with the origin added, which changes neither the supremum of the isonormal process, since \(\sup_nX_{t_n}\geq0\) almost surely, nor the divergence of Dudley’s integral. Take \[ T_k:=\{0\}\cup\{t_n:n\leq2^{2^k}\}, \qquad|T_k|\leq2^{2^k}+1 , \] which is admissible after shifting the index by one. For \(t=t_n\), the distance \(d(t_n,T_k)\) is \(0\) once \(2^{2^k}\geq n\), and is at most \(\|t_n\|_2=1/\sqrt{1+\log n}\) always, using the origin. So \[ \sum_{k\geq0}2^{k/2}d(t_n,T_k)\leq\frac1{\sqrt{1+\log n}}\sum_{k:\,2^{2^k}<n}2^{k/2} \leq\frac{C\,2^{k_n/2}}{\sqrt{1+\log n}}, \] where \(k_n\) is the largest index with \(2^{2^{k_n}}<n\), so that \(2^{k_n}<\log_2n\) and \(2^{k_n/2}<\sqrt{\log_2n}\). The right side is bounded by an absolute constant, uniformly in \(n\), and \(d(0,T_k)=0\). Hence \(\gamma_2(T,d)\leq C\), in agreement with the finiteness of \(\mathbb E\sup_nX_{t_n}\).
The mechanism is visible: the far-out points \(t_n\) with \(n\) huge are approximated by the origin, at a cost \(\|t_n\|_2\) that is tiny, and the stages \(T_k\) with \(2^{2^k}<n\) that fail to contain \(t_n\) are few, about \(\log\log n\) of them, with geometrically growing weights that sum to \(\sqrt{\log n}\). Dudley, by contrast, insisted on covering each \(t_n\) to within \(\varepsilon\) by a point at distance \(\varepsilon\), and paid \(\exp(2/\varepsilon^2)\) points to do so.
2 The generic chaining bound
Theorem 1 (Generic chaining) 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\gamma_2(T,d), \] and for every \(t_0\in T\) and \(u\geq0\), with probability at least \(1-2e^{-u^2}\), \[ \sup_{t\in T}|X_t-X_{t_0}|\leq C(1+u)\gamma_2(T,d). \]
As in Lecture 16 it suffices to treat finite \(T\); the reduction is the same, using that an admissible sequence for \(T\) restricts to one for a subset after replacing each point by a nearest point of the subset, which at most doubles every \(d(t,T_k)\). Fix an admissible sequence \((T_k)\) with \(T_0=\{t_0\}\) and \[ S:=\sup_{t\in T}\sum_{k\geq0}2^{k/2}d(t,T_k) \] close to \(\gamma_2(T,d)\). For \(t\in T\) let \(\pi_k(t)\in T_k\) be a nearest point, so \(d(t,\pi_k(t))=d(t,T_k)\), and \(\pi_k(t)=t\) for large \(k\) since \(T\) is finite.
Step 1: the chain. \(X_t-X_{t_0}=\sum_{k\geq1}(X_{\pi_k(t)}-X_{\pi_{k-1}(t)})\), a finite sum, with links of \(\psi_2\) norm at most \[ d\big(\pi_k(t),\pi_{k-1}(t)\big)\leq d(t,T_k)+d(t,T_{k-1}). \]
Step 2: the increments, uniformly. At stage \(k\) the link \((\pi_k(t),\pi_{k-1}(t))\) is one of at most \(|T_k||T_{k-1}|\leq2^{2^{k+1}}\) pairs \((a,b)\). For a single pair and \(s\geq0\), the sub-Gaussian tail of Lecture 5 gives \(\mathbb P\{|X_a-X_b|\geq d(a,b)s\}\leq2e^{-s^2}\). Take \(s_k:=\sqrt{2^{k+2}\log2}+u\), so that \(s_k^2\geq2^{k+2}\log2+u^2\) and the union bound over the pairs at stage \(k\) gives failure probability at most \[ 2^{2^{k+1}}\cdot2\exp\big(-2^{k+2}\log2-u^2\big)=2\cdot2^{-2^{k+1}}e^{-u^2}. \] Summing over \(k\geq1\), all links at all stages satisfy \(|X_a-X_b|\leq d(a,b)s_k\) outside an event of probability at most \(2e^{-u^2}\sum_{k\geq1}2^{-2^{k+1}}\leq2e^{-u^2}\).
Step 3: summing the chain. On the good event, for every \(t\), \[ |X_t-X_{t_0}|\leq\sum_{k\geq1}\big(d(t,T_k)+d(t,T_{k-1})\big)\big(2^{(k+2)/2}\sqrt{\log2}+u\big). \] The two sums \(\sum_k2^{k/2}d(t,T_k)\) and \(\sum_k2^{k/2}d(t,T_{k-1})=\sqrt2\sum_k2^{(k-1)/2}d(t,T_{k-1})\) are each at most \(\sqrt2\,S\), and since \(2^{k/2}\geq1\) the sums without the weight \(2^{k/2}\) are also at most \(S\). Altogether \(|X_t-X_{t_0}|\leq C(1+u)S\), uniformly in \(t\), which is the tail bound. Integrating in \(u\) and using \(\mathbb EX_{t_0}=0\) gives the expectation bound, and \(S\) may be taken arbitrarily close to \(\gamma_2(T,d)\).
The proof is the proof of Dudley’s inequality with one change: the threshold for the link at stage \(k\) is proportional to the link’s own length \(d(\pi_k(t),\pi_{k-1}(t))\) rather than to the worst link length \(2^{-k+2}\) at that stage. The union bound is unaffected, because the number of pairs at stage \(k\) is controlled by the admissibility condition and not by the scale, and the sum along the chain then produces the \(\gamma_2\) sum for the particular \(t\) rather than Dudley’s sum of suprema.
The tail bound above has scale \(\gamma_2(T,d)\) in the fluctuation term \(u\gamma_2\), whereas for Gaussian processes Borell–TIS (Lecture 11) gives fluctuations on the smaller scale \(\sigma=\sup_t\sqrt{\operatorname{Var}X_t}\). A more careful choice of chain, in which one moves from \(\pi_{k-1}(t)\) to \(\pi_k(t)\) only when \(d(t,T_k)\) is less than half of \(d(t,\pi_{k-1}(t))\), makes the link lengths decrease geometrically and yields \[ \sup_{s,t\in T}|X_t-X_s|\leq C\big[\gamma_2(T,d)+u\operatorname{diam}(T)\big] \] with probability at least \(1-2e^{-u^2}\), for every sub-Gaussian process. This is the form in the handwritten notes, and it is the sub-Gaussian analogue of Borell–TIS: the mean is controlled by the geometry through \(\gamma_2\), and the fluctuations by the diameter alone.
3 Comparison with Dudley and Sudakov
Two lemmas place \(\gamma_2\) between the bounds of Lectures 12 and 16.
Lemma 1 (\(\gamma_2\) is at most Dudley’s integral) For every metric space \((T,d)\), \[ \gamma_2(T,d)\leq C\int_0^\infty\sqrt{\log N(T,d,\varepsilon)}\,d\varepsilon . \]
Assume the integral is finite, so \(T\) is totally bounded. For \(k\geq0\) let \[ \varepsilon_k:=\inf\big\{\varepsilon>0:\ N(T,d,\varepsilon)\leq2^{2^k}\big\}, \] a nonincreasing sequence tending to \(0\), with \(\varepsilon_0\) at most the diameter. Choose \(T_k\) to be a \(2\varepsilon_k\)-net of cardinality at most \(2^{2^k}\), which exists by the definition of \(\varepsilon_k\); then \((T_k)\) is admissible and \(d(t,T_k)\leq2\varepsilon_k\) for every \(t\), so \[ \gamma_2(T,d)\leq2\sum_{k\geq0}2^{k/2}\varepsilon_k . \] For \(\varepsilon<\varepsilon_k\) we have \(N(T,d,\varepsilon)>2^{2^k}\), so \(\sqrt{\log N(T,d,\varepsilon)}\geq2^{k/2}\sqrt{\log2}\) on \((\varepsilon_{k+1},\varepsilon_k)\), and \[ \int_0^\infty\sqrt{\log N(T,d,\varepsilon)}\,d\varepsilon \geq\sqrt{\log2}\sum_{k\geq0}2^{k/2}(\varepsilon_k-\varepsilon_{k+1}). \] Finally, writing \(\varepsilon_k=\sum_{j\geq k}(\varepsilon_j-\varepsilon_{j+1})\) and exchanging the order of summation, \[ \sum_{k\geq0}2^{k/2}\varepsilon_k=\sum_{j\geq0}(\varepsilon_j-\varepsilon_{j+1})\sum_{k\leq j}2^{k/2} \leq\frac{\sqrt2}{\sqrt2-1}\sum_{j\geq0}2^{j/2}(\varepsilon_j-\varepsilon_{j+1}), \] which is at most a constant times the integral.
Lemma 2 (\(\gamma_2\) is at least the Sudakov quantity) For every metric space \((T,d)\) and every \(\varepsilon>0\), \[ \gamma_2(T,d)\geq c\,\varepsilon\sqrt{\log N(T,d,\varepsilon)} . \]
Let \(N=N(T,d,\varepsilon)\geq2\) and let \((T_k)\) be admissible. Let \(k\) be the largest index with \(2^{2^k}<N\), so that \(2^{2^{k+1}}\geq N\) and hence \(2^{k/2}\geq\sqrt{\log_2N}/2\). Since \(|T_k|<N\), the set \(T_k\) is not an \(\varepsilon\)-net of \(T\), so some \(t\in T\) has \(d(t,T_k)\geq\varepsilon\). For this \(t\), \[ \sum_{j\geq0}2^{j/2}d(t,T_j)\geq2^{k/2}d(t,T_k)\geq\frac{\varepsilon\sqrt{\log_2N}}2 . \] Taking the supremum over \(t\) and the infimum over admissible sequences gives the claim.
So for a general metric space, \[ c\,\sup_{\varepsilon>0}\varepsilon\sqrt{\log N(T,d,\varepsilon)} \ \leq\ \gamma_2(T,d)\ \leq\ C\int_0^\infty\sqrt{\log N(T,d,\varepsilon)}\,d\varepsilon , \] and both inequalities can be strict. For Talagrand’s example the right side is infinite while \(\gamma_2\) is bounded. For the \(\ell^1\) ball, Lecture 16 found the right side of order \((\log n)^{3/2}\) and the left side of order \(\sqrt{\log n}\); the theorem below shows that \(\gamma_2(B_1^n)\asymp\sqrt{\log n}\), so \(\gamma_2\) sits at the lower bound there and the entropy integral is what overshoots.
4 The majorizing measure theorem
For Gaussian processes the generic chaining bound is sharp.
Theorem 2 (Talagrand’s majorizing measure theorem) Let \((X_t)_{t\in T}\) be a centered Gaussian process with separable canonical metric \(d\). Then \[ c\,\gamma_2(T,d)\leq\mathbb E\sup_{t\in T}X_t\leq C\gamma_2(T,d) \] for absolute constants \(c,C>0\).
The upper bound is Theorem 1, since a Gaussian process is sub-Gaussian with respect to \(2d\). The lower bound is the deep part. It says that for Gaussian processes, chaining is not merely a technique but the only mechanism: whatever makes \(\mathbb E\sup X\) large must be visible as an admissible sequence that cannot approximate some point cheaply. The next lecture proves the lower bound. Its proof reverses the chaining argument, building a tree of subsets of \(T\) whose branches are well separated at each depth and using Sudakov’s minoration, in the sharp form of the Sudakov–Fernique comparison, to show that the process must pay \(\varepsilon\sqrt{\log(\text{number of branches})}\) at every branching.
The name comes from Fernique’s original formulation of the lower bound in terms of probability measures on \(T\) (Fernique 1975), and Talagrand’s theorem (Talagrand 1987) established the matching upper bound and the equivalence with the \(\gamma_2\) functional; the modern account is (Talagrand 2014).
Three consequences are worth recording.
Gaussian width is a \(\gamma_2\) functional. For \(T\subseteq\mathbb R^n\) with the Euclidean metric, \(w(T)\asymp\gamma_2(T,\|\cdot\|_2)\). The width of every set in Lecture 3 and Lecture 13 could, in principle, be computed by exhibiting an admissible sequence and a matching tree.
Comparison for sub-Gaussian processes. If \((X_t)\) is sub-Gaussian with respect to the canonical metric of a Gaussian process \((Y_t)\) on the same index set, then \[ \mathbb E\sup_tX_t\leq C\gamma_2(T,d)\leq C'\,\mathbb E\sup_tY_t . \] Thus every sub-Gaussian process is dominated by a Gaussian process with the same increments, a statement that has no direct proof and is the main practical use of the theorem. Lecture 19 applies it to random matrices with sub-Gaussian rows.
The gap between Sudakov and Dudley is closed. For Gaussian processes the expected supremum is neither the largest rectangle under the entropy curve nor the area under it. It is \(\gamma_2\), a quantity that sees the entropy of each region of \(T\) at each scale, and it coincides with the rectangle for some sets, with the area for others, and with neither in general.
5 Where we go next
The next lecture completes the proof of the majorizing measure theorem with the tree construction and the sharpened Sudakov lemma from the handwritten notes, and then turns the theorem into a tool: the matrix deviation inequality, which controls \(\sup_{x\in T}\big|\|Ax\|_2-\sqrt m\|x\|_2\big|\) for a matrix \(A\) with independent sub-Gaussian rows by the Gaussian width of \(T\). That inequality is what the covariance estimation problem of Lecture 9 was missing.