翻译状态说明
本页为第 8 章的结构化精校翻译，覆盖正文、Notes、Exercises 8.1-8.41、原书 Figure 8.1-8.10，并为原文明确证明、正文隐藏验证和习题加入学习笔记证明跳转。
第 8 章 Chaining
第 7 章中，Gaussian comparison 把随机过程的上确界转化为索引集合的几何量。本章进入更一般的情形：当随机过程只有 subgaussian increments，而未必是 Gaussian process 时，如何控制
$$ \mathbb E\sup_{t\in T}X_t? $$
核心方法叫做 chaining。它不试图一次性把 $t$ 与固定点 $t_0$ 连接起来，而是用越来越细的 net 构造一条多尺度路径：
$$ t_0\to \pi_0(t)\to \pi_1(t)\to \pi_2(t)\to\cdots\to t. $$
每一层只付出该尺度的误差，再把所有尺度相加。Dudley inequality 是最基础的 chaining bound；generic chaining 则把“每一层最坏误差再求和”改成“每一点沿路径求和后再取上确界”，从而得到更精细的 $\gamma_2$ functional。
8.1 Dudley inequality
设 $(X_t)_{t\in T}$ 是 metric space $(T,d)$ 上的随机过程。若存在 $K\ge0$ 使得对所有 $t,s\in T$，
$$\|X_t-X_s\|_{\psi_2}\le K d(t,s), \tag{8.1}$$则称该过程具有 subgaussian increments。
Gaussian process 的 canonical metric 为 $d(t,s)=\|X_t-X_s\|_{L^2}$。由于 centered Gaussian 的 $\psi_2$ 范数与标准差等价，Gaussian process 自动具有 subgaussian increments。
若 $(X_t)_{t\in T}$ 是均值为零且满足 (8.1) 的随机过程，则
$$\mathbb E\sup_{t\in T}X_t\le CK\int_0^\infty\sqrt{\log\mathcal N(T,d,\varepsilon)}\,d\varepsilon.$$ 查看学习笔记：Theorem 8.1.3 完整证明
若 $\operatorname{diam}(T)\le1$，则 Dudley bound 可写成离散多尺度求和：
$$\mathbb E\sup_{t\in T}X_t\le CK\sum_{k\ge0}2^{-k}\sqrt{\log\mathcal N(T,d,2^{-k})}.$$ 查看学习笔记：Theorem 8.1.4 完整证明证明思想是选择 $2^{-k}$-net $T_k$，令 $\pi_k(t)$ 是 $t$ 在 $T_k$ 中的近似点，然后把
$$ X_t-X_{t_0} =\sum_{k\ge1}\bigl(X_{\pi_k(t)}-X_{\pi_{k-1}(t)}\bigr) $$
写成各尺度增量之和。每个尺度的最大值由 subgaussian 最大值估计控制，最后对 $k$ 求和。
离散 Dudley inequality 通过 dyadic decomposition 转成 integral form。反过来，积分形式与 dyadic sum 等价；这留给 Exercise 8.3。
8.1.1 Variations and Examples
Chaining 也给出增量上确界版本：对任意 $t_0\in T$，可控制 $\mathbb E\sup_t|X_t-X_{t_0}|$，因此不必只考虑单边 $\sup_tX_t$。
同一 chaining 论证可升级为高概率界；每个尺度使用 subgaussian tail，再对尺度做 union bound。
查看学习笔记：Exercise 8.1 证明积分上限可截到 $\operatorname{diam}(T)$，因为尺度大于直径时一个球即可覆盖 $T$。
查看学习笔记：积分上限截断验证任意有界集合 $T\subset\mathbb R^n$ 的 Gaussian width 满足
$$w(T)\le C\int_0^\infty\sqrt{\log\mathcal N(T,\varepsilon)}\,d\varepsilon.$$ 查看学习笔记：Theorem 8.1.8 完整证明对 Euclidean ball $B_2^n$，体积法给出 $\mathcal N(B_2^n,\varepsilon)\le(3/\varepsilon)^n$，Dudley integral 得到 $w(B_2^n)\lesssim\sqrt n$，与真实量同阶。
Dudley inequality 并不总是 tight。取
$$ T=\left\{\frac{e_k}{\sqrt{1+\log k}}:k=1,\dots,n\right\}, $$
则 Gaussian width 有界，但 Dudley integral 会随 $n$ 增大。这说明单纯的 metric entropy 不足以完全捕捉随机过程大小，也为 generic chaining 埋下伏笔。
8.2 应用：empirical processes
8.2.1 The Monte Carlo method
给定概率空间 $(\Omega,\mu)$ 和函数 $f:\Omega\to\mathbb R$，目标是计算积分
$$ \int_\Omega f\,d\mu=\mathbb Ef(X). $$
Monte Carlo 方法取独立样本 $X_1,\dots,X_n\sim\mu$，用经验平均
$$ \frac1n\sum_{i=1}^nf(X_i) $$
估计该积分。
对单个固定函数，Monte Carlo 误差的典型期望尺度为 $O(n^{-1/2})$，来自大数定律与方差缩放。
Monte Carlo 的基本误差率不直接依赖维度；只要能从 $\mu$ 抽样并计算 $f(X_i)$，就可实施。
8.2.2 Lipschitz law of large numbers
一个样本不能同时估计所有函数的积分。若函数可在样本点之间剧烈振荡，则经验平均会完全误判整体积分。
令
$$\mathcal F=\{f:[0,1]\to\mathbb R:\|f\|_{\mathrm{Lip}}\le L\}.$$若 $X,X_1,\dots,X_n$ 是取值于 $[0,1]$ 的 i.i.d. 随机变量，则
$$\mathbb E\sup_{f\in\mathcal F}\left|\frac1n\sum_{i=1}^nf(X_i)-\mathbb Ef(X)\right|\le \frac{CL}{\sqrt n}.$$ 查看学习笔记：Theorem 8.2.3 完整证明对函数类 $\mathcal F$，定义
$$X_f=\frac1n\sum_{i=1}^nf(X_i)-\mathbb Ef(X),\qquad f\in\mathcal F.$$这个由函数 $f$ 索引的随机过程称为 empirical process。
Theorem 8.2.3 的证明把 $X_f$ 视为随机过程，先验证其在 $\|\cdot\|_{L^\infty}$ 下具有 subgaussian increments，再用 Dudley inequality 与 Lipschitz 函数类 covering number
$$ \mathcal N(\mathcal F,\|\cdot\|_{L^\infty},\varepsilon)\le e^{C/\varepsilon}. $$
查看学习笔记：Lipschitz 函数类 covering number 验证
8.2.3 Empirical measure
经验测度定义为
$$ \mu_n=\frac1n\sum_{i=1}^n\delta_{X_i}. $$
于是
$$ \frac1n\sum_{i=1}^nf(X_i)-\mathbb Ef(X)=\int f\,d\mu_n-\int f\,d\mu. $$
当 $\mathcal F$ 是 Lipschitz 函数类时，上式的上确界可解释为 Wasserstein distance。Kantorovich-Rubinstein duality 说明 Theorem 8.2.3 也可称为 Wasserstein law of large numbers。
8.3 VC dimension
8.3.1 Definition and examples
若 Boolean 函数类 $\mathcal F$ 能在有限集 $\Lambda\subset\Omega$ 上实现全部 $2^{|\Lambda|}$ 种二元标记，则称 $\Lambda$ 被 $\mathcal F$ shattered。$\operatorname{vc}(\mathcal F)$ 是可被 shattered 的集合最大基数；若无最大值，则为 $\infty$。
区间指标函数类的 VC dimension 为 $2$：两个点可被区间实现全部标记，三个有序点无法实现只取中间点的标记。
半平面指标函数类在 $\mathbb R^2$ 中的 VC dimension 为 $3$：一般位置的三个点可被 shattered；四个点总存在不可线性分离的标记。
半空间在 $\mathbb R^n$ 中的 VC dimension 为 $n+1$。这与参数个数相符，但参数个数只是启发，不是普遍定理。
8.3.2 Pajor Lemma
若 $\mathcal F$ 是有限集合 $\Omega$ 上的 Boolean 函数类，则
$$|\mathcal F|\le |\{\Lambda\subseteq\Omega:\Lambda\text{ is shattered by }\mathcal F\}|.$$ 查看学习笔记：Lemma 8.3.7 完整证明8.3.3 Sauer-Shelah Lemma
若 $\mathcal F$ 是 $n$ 点集合上的 Boolean 函数类，且 $d=\operatorname{vc}(\mathcal F)<n$，则
$$|\mathcal F|\le \sum_{k=0}^d\binom nk\le \left(\frac{en}{d}\right)^d.$$ 查看学习笔记：Lemma 8.3.9 完整证明8.3.4 Growth function
函数类 $\mathcal F$ 的 growth function 定义为
$$\Pi_{\mathcal F}(n)=\max_{|\Lambda|=n}|\mathcal F|_\Lambda|,$$即把 $\mathcal F$ 限制到 $n$ 个点上最多能得到多少种不同标记。
若 $d=\operatorname{vc}(\mathcal F)<\infty$，则
$$ 2^d\le \Pi_{\mathcal F}(n)\le \left(\frac{en}{d}\right)^d. $$
若两个 Boolean 函数类 $\mathcal F,\mathcal G$ 的 VC dimension 有界，则由 pointwise min/max 等有限布尔组合得到的新函数类，其 VC dimension 仍可由原来的 VC dimension 控制。
查看学习笔记：Proposition 8.3.11 完整证明
8.3.5 Covering numbers via VC dimension
若 $\mathcal F$ 是 probability space $(\Omega,\mu)$ 上 VC dimension 为 $d$ 的 Boolean 函数类，则对 $\varepsilon\in(0,1)$，
$$\mathcal N(\mathcal F,L^2(\mu),\varepsilon)\le \left(\frac{C}{\varepsilon}\right)^{Cd}.$$ 查看学习笔记：Theorem 8.3.13 完整证明若有限 Boolean 函数族在 $L^2(\mu)$ 中两两 $\varepsilon$-separated，则用 $O(\varepsilon^{-4}\log N)$ 个随机样本点限制后，它们仍以常数倍尺度分离。
查看学习笔记：Lemma 8.3.14 完整证明Theorem 8.3.13 的证明先取 maximal packing，再用 Lemma 8.3.14 把底空间缩小到随机样本点集，最后在有限点集上应用 Sauer-Shelah Lemma。
8.3.6 VC law of large numbers
若 Boolean 函数类 $\mathcal F$ 的 VC dimension 为 $d<\infty$，则
$$\mathbb E\sup_{f\in\mathcal F}\left|\frac1n\sum_{i=1}^nf(X_i)-\mathbb Ef(X)\right|\le C\sqrt{\frac dn}.$$ 查看学习笔记：Theorem 8.3.15 完整证明对 i.i.d. 实随机变量 $X_1,\dots,X_n$，经验 CDF $F_n$ 满足
$$\mathbb E\sup_t|F_n(t)-F(t)|\le \frac{C}{\sqrt n}.$$ 查看学习笔记：Theorem 8.3.17 完整证明
8.4 应用：statistical learning theory
统计学习的基本设置如下：有未知 target function $T:\Omega\to\{0,1\}$，我们观察训练数据
$$ (X_i,T(X_i)),\qquad i=1,\dots,n, $$
目标是从 hypothesis class $\mathcal F$ 中选择函数预测新样本。
8.4.1 Risk, fit and complexity
真实风险定义为
$$ R(f)=\mathbb P\{f(X)\ne T(X)\}=\mathbb E(f(X)-T(X))^2. $$
在 $\mathcal F$ 中的最佳函数为
$$ f^*=\arg\min_{f\in\mathcal F}R(f). $$
模型类过小会 underfit，过大则会 overfit。合适的模型类需要在 fit 与 complexity 之间取平衡。
8.4.2 Empirical risk minimization
经验风险定义为
$$ R_n(f)=\frac1n\sum_{i=1}^n(f(X_i)-T(X_i))^2. $$
Empirical risk minimizer 为
$$ f_n^*=\arg\min_{f\in\mathcal F}R_n(f). $$
8.4.3 VC generalization bound
若 target $T$ 是 Boolean function，且 hypothesis class $\mathcal F$ 具有有限 VC dimension，则
$$\mathbb E R(f_n^*)\le R(f^*)+C\sqrt{\frac{\operatorname{vc}(\mathcal F)}{n}}.$$ 查看学习笔记：Theorem 8.4.5 完整证明证明先用 pointwise inequality
$$ R(f_n^*)-R(f^*)\le 2\sup_{f\in\mathcal F}|R_n(f)-R(f)|, $$
再对损失函数类 $\mathcal L=\{(f-T)^2:f\in\mathcal F\}$ 应用 VC law of large numbers。
8.5 Generic chaining
Dudley inequality 虽然通用，但可有 logarithmic gap。Generic chaining 通过更精细地安排每个点自己的多尺度路径，改进 Dudley sum。
8.5.1 A makeover of Dudley inequality
Dudley sum 的粗糙之处在于每个尺度都取全局最坏点：
$$ \sum_k2^{k/2}\sup_{t\in T}d(t,T_k). $$
Generic chaining 把 supremum 放到求和外面：
$$ \sup_{t\in T}\sum_k2^{k/2}d(t,T_k). $$
8.5.2 The $\gamma_2$ functional and generic chaining
一列集合 $(T_k)_{k\ge0}$ 称为 admissible sequence，若 $|T_0|=1$ 且 $|T_k|\le 2^{2^k}$。定义
$$\gamma_2(T,d)=\inf_{(T_k)}\sup_{t\in T}\sum_{k\ge0}2^{k/2}d(t,T_k),$$其中 infimum 取遍所有 admissible sequences。
若 $(X_t)_{t\in T}$ 是均值为零、具有 subgaussian increments 的随机过程，则
$$\mathbb E\sup_{t\in T}X_t\le CK\gamma_2(T,d).$$ 查看学习笔记：Theorem 8.5.2 完整证明Generic chaining 也有增量上确界和高概率版本；证明与 Dudley 的高概率版本相同，但第一步从较粗尺度开始，以便吸收尾部参数 $u$。
8.5.3 Majorizing measure and comparison theorems
若 $(X_t)_{t\in T}$ 是 centered Gaussian process，且 $d(t,s)=\|X_t-X_s\|_{L^2}$，则
$$\mathbb E\sup_{t\in T}X_t\asymp \gamma_2(T,d).$$上界来自 Theorem 8.5.2；下界是 Talagrand majorizing measure theorem 的深层部分，本书不展开证明。
若 $(X_t)$ 是 subgaussian process，$(Y_t)$ 是 Gaussian process，且
$$\|X_t-X_s\|_{\psi_2}\le K\|Y_t-Y_s\|_{L^2},$$则
$$\mathbb E\sup_{t\in T}X_t\le CK\,\mathbb E\sup_{t\in T}Y_t.$$ 查看学习笔记：Corollary 8.5.6 完整证明若 $T\subset\mathbb R^n$，且随机过程满足
$$\|X_x-X_y\|_{\psi_2}\le K\|x-y\|_2,$$则
$$\mathbb E\sup_{x\in T}X_x\le CKw(T).$$ 查看学习笔记：Corollary 8.5.8 完整证明一个直接后果是：若 $X$ 是 $\mathbb R^n$ 中的 subgaussian random vector，则
$$ \mathbb E\sup_{x\in T}\langle X,x\rangle\lesssim \|X\|_{\psi_2}w(T). $$
8.6 Chevet inequality
令 $A$ 为 $m\times n$ 随机矩阵，其行 $A_i$ 独立、均值为零且 subgaussian。若 $T\subset\mathbb R^n$、$S\subset\mathbb R^m$ 有界，则
$$\mathbb E\sup_{x\in T,y\in S}\langle Ax,y\rangle \le CK\{w(T)\operatorname{rad}(S)+w(S)\operatorname{rad}(T)\}.$$ 查看学习笔记：Theorem 8.6.1 完整证明证明模仿第 7.3 节 Gaussian matrix norm 的比较思路，但用 Talagrand comparison 取代 Sudakov-Fernique。索引为 $(x,y)\in T\times S$，过程为 $X_{xy}=\langle Ax,y\rangle$。增量由两项控制：
$$ \|X_{xy}-X_{uv}\|_{\psi_2} \lesssim K\bigl(\|x-u\|_2\operatorname{rad}(S)+\|y-v\|_2\operatorname{rad}(T)\bigr). $$
比较 Gaussian process 取
$$ Y_{xy}=\operatorname{rad}(S)\langle g,x\rangle+\operatorname{rad}(T)\langle h,y\rangle. $$
取 $T=S^{n-1}$、$S=S^{m-1}$，Chevet inequality 给出 familiar bound $\mathbb E\|A\|\lesssim\sqrt m+\sqrt n$。
若 $A$ 为 i.i.d. Gaussian matrix，则 Chevet inequality 可取 sharp constant 1，并且有反向下界到常数因子。
查看学习笔记：Exercise 8.39 证明8.7 Notes
Chaining 思想可追溯到 Kolmogorov 关于 Brownian motion 连续性的证明。Dudley integral inequality 来自 Dudley 的工作，empirical processes 与 VC theory 则是现代统计学习理论的基础工具。
VC dimension 源于 Vapnik 与 Chervonenkis。Pajor Lemma、Sauer-Shelah Lemma、growth function 与 covering number estimates 共同解释了为什么有限 VC dimension 可以推出 uniform law of large numbers。
Generic chaining 与 majorizing measure theorem 是 Talagrand 理论的核心。本章只使用其上界和比较形式；完整下界需要更深的 multiscale argument。Chevet inequality 则把 chaining/比较思想转化为随机矩阵双线性型的统一范数控制。