证明目标：由 dyadic nets 推出离散 Dudley sum。

完整证明：假设 $\operatorname{diam}(T)\le1$，并取 $2^{-k}$-net $T_k$，满足 $|T_k|\le\mathcal N(T,d,2^{-k})$。固定 $t_0\in T_0$，对每个 $t\in T$ 取最近点 $\pi_k(t)\in T_k$。由 net 性质，$d(\pi_k(t),\pi_{k-1}(t))\le d(\pi_k(t),t)+d(t,\pi_{k-1}(t))\le 3\cdot2^{-k}$。若 $X_t$ 在这些近似点上收敛到 $X_t$，则

取上确界和期望，并交换求和，得到

每个增量的 $\psi_2$ 范数至多 $CK2^{-k}$，而候选对数至多 $|T_k||T_{k-1}|$。Subgaussian 最大值估计给出第 $k$ 层贡献不超过 $CK2^{-k}\sqrt{\log |T_k|}$。代入 $|T_k|\le\mathcal N(T,d,2^{-k})$ 并求和，即得离散 Dudley inequality。一般 $T$ 可先对有限 net 证明，再用单调极限传递。

证明目标：把离散 Dudley sum 转成 entropy integral。

完整证明：先按尺度归一化，使 $\operatorname{diam}(T)\le1$。由 Theorem 8.1.4，

函数 $\varepsilon\mapsto\mathcal N(T,d,\varepsilon)$ 随 $\varepsilon$ 下降而不减。对 $\varepsilon\in[2^{-k-1},2^{-k}]$，有 $\sqrt{\log\mathcal N(T,d,\varepsilon)}\ge \sqrt{\log\mathcal N(T,d,2^{-k})}$，且区间长度为 $2^{-k-1}$。因此每个 dyadic 项可由相邻区间积分控制：

对 $k$ 求和得到积分形式。若直径不是 $1$，按尺度缩放 metric；若 $T$ 不有限，先取有限子集并使用上确界的单调收敛。

证明目标：把 Theorem 8.1.3 应用到 canonical Gaussian process。

完整证明：令 $X_x=\langle g,x\rangle$，$x\in T$。则 $X_x-X_y=\langle g,x-y\rangle$ 是方差 $\|x-y\|_2^2$ 的 Gaussian 变量，所以 $\|X_x-X_y\|_{\psi_2}\le C\|x-y\|_2$。Theorem 8.1.3 给出

左边就是 $w(T)$，结论成立。

证明目标：证明一维 Lipschitz 函数类的 uniform LLN。

完整证明：通过缩放和平移，可把问题化为 $\mathcal F=\{f:[0,1]\to[0,1]:\|f\|_{\mathrm{Lip}}\le1\}$。定义 empirical process $X_f=n^{-1}\sum_i f(X_i)-\mathbb Ef(X)$。对 $f,g\in\mathcal F$，令 $Z_i=(f-g)(X_i)-\mathbb E(f-g)(X)$。这些变量独立、均值零，且 $\|Z_i\|_{\psi_2}\le C\|f-g\|_\infty$。由独立 subgaussian 和的估计，

因此 $X_f$ 在 metric $d(f,g)=n^{-1/2}\|f-g\|_\infty$ 下具有 subgaussian increments。Dudley inequality 给出

Lipschitz 函数类的 covering number 满足 $\log\mathcal N\le C/\varepsilon$，故积分 $\int_0^1\varepsilon^{-1/2}d\varepsilon$ 有界，得到 $C/\sqrt n$。恢复 Lipschitz 常数 $L$ 得到原命题。

证明目标：证明函数数目不超过 shattered subsets 数目。

完整证明：对 $|\Omega|$ 归纳。取一点 $x_0\in\Omega$，令 $\Omega_0=\Omega\setminus\{x_0\}$。把 $\mathcal F$ 在 $\Omega_0$ 上的 restrictions 分成两类：只出现一种 $x_0$ 延拓的类 $\mathcal F_1$，以及同时出现 $0$ 与 $1$ 两种 $x_0$ 延拓的类 $\mathcal F_2$。于是 $|\mathcal F|=|\mathcal F_1|+2|\mathcal F_2|$。归纳假设控制 $\mathcal F_1\cup\mathcal F_2$ 在 $\Omega_0$ 上 shattered 的集合数，也控制 $\mathcal F_2$ 在 $\Omega_0$ 上 shattered 的集合数。若 $\Lambda$ 被 $\mathcal F_2$ shattered，则 $\Lambda\cup\{x_0\}$ 被 $\mathcal F$ shattered，因为对 $\Lambda$ 的任意标记和 $x_0$ 的任意取值都有相应函数。两类 shattered sets 不相交并合并后至少有 $|\mathcal F|$ 个，归纳完成。

证明目标：由 VC dimension 得到标记数上界。

完整证明：若 $\operatorname{vc}(\mathcal F)=d$，则 $\mathcal F$ 不能 shatter 任意大小超过 $d$ 的 subset。Pajor lemma 给出 $|\mathcal F|$ 不超过 shattered subsets 总数。所有 shattered subsets 都有大小 $0,\dots,d$，故

当 $1\le d\le n$ 时，标准二项式估计 $\sum_{k=0}^d\binom nk\le(en/d)^d$ 给出第二个上界。$d=0$ 或 $d=n$ 的边界情形按定义直接处理。

证明目标：说明有限布尔组合不会让 VC dimension 失控。

完整证明：设 $\mathcal H$ 由两个类 $\mathcal F,\mathcal G$ 的 pointwise min/max 组成。若 $\mathcal H$ shatter 了 $m$ 个点，则在这些点上的标记数为 $2^m$。另一方面，$\mathcal F$ 在该点集上的 restrictions 数至多 $\Pi_{\mathcal F}(m)$，$\mathcal G$ 至多 $\Pi_{\mathcal G}(m)$，每对 restrictions 经固定布尔运算最多产生一个 $\mathcal H$ restriction，所以

若 $\operatorname{vc}(\mathcal F),\operatorname{vc}(\mathcal G)\le d$，Sauer-Shelah 给出右侧至多 $(em/d)^{2d}$。当 $m>C d\log d$ 或在一般参数下 $m>C(d_F+d_G)\log(d_F+d_G)$ 时，上式矛盾。因此组合类的 VC dimension 由原类维度控制。更多输入函数或任意布尔公式时，将 product bound 换成 $\prod_i\Pi_{\mathcal F_i}(m)$ 即可。

证明目标：用随机样本点保持有限 Boolean 函数族的分离性。

完整证明：设 $f,g$ 在 $L^2(\mu)$ 中 $\varepsilon$-separated。对 Boolean 函数，$\|f-g\|_{L^2(\mu)}^2=\mathbb P\{f(X)\ne g(X)\}\ge\varepsilon^2$。令 $Y_i=\mathbf1_{\{f(X_i)\ne g(X_i)\}}$，则 $\mathbb EY_i\ge\varepsilon^2$。Bernstein 或 Chernoff bound 给出

对至多 $N^2$ 对函数做 union bound。取 $n\ge C\varepsilon^{-2}\log N$ 即可保持所有对的经验分离；书中用 $\varepsilon^{-4}$ 的宽松选择可直接配合后续 $L^2$ 距离尺度，仍足以推出结论。

证明目标：证明 finite VC dimension 推出 $L^2(\mu)$ covering bound。

完整证明：令 $N$ 是 $\mathcal F$ 中 maximal $\varepsilon$-separated subset 的大小。由 packing-covering equivalence，控制 $N$ 即可控制 covering number。对该 $N$ 个函数应用 Lemma 8.3.14，存在样本点集 $\Omega_n$，其中 $n\le C\varepsilon^{-4}\log N$，使这些函数限制到 $\Omega_n$ 后仍两两不同。因此 $N\le|\mathcal F|_{\Omega_n}|$。Sauer-Shelah Lemma 给出

解这个不等式可得 $\log N\le Cd\log(C/\varepsilon)$。于是 $\mathcal N(\mathcal F,L^2(\mu),\varepsilon)\le N\le(C/\varepsilon)^{Cd}$。

证明目标：证明 Boolean VC class 的 uniform LLN。

完整证明：先用 empirical symmetrization：

条件在样本 $X_1,\dots,X_n$ 上，右侧是 Rademacher process。其增量在 empirical $L^2(\mu_n)$ metric 下 subgaussian，尺度为 $n^{-1/2}$。Dudley inequality 给出

对固定 $\mu_n$ 应用 Theorem 8.3.13，$\log\mathcal N\le Cd\log(C/\varepsilon)$。积分 $\int_0^1\sqrt{\log(C/\varepsilon)}\,d\varepsilon$ 有界，因此得到 $C\sqrt{d/n}$。

证明目标：由 VC LLN 推出经验分布函数一致收敛率。

完整证明：取函数类 $\mathcal F=\{\mathbf1_{(-\infty,t]}:t\in\mathbb R\}$。这个类的 VC dimension 至多 $1$；若使用闭区间/半无限区间的书中约定，也可用上界 $2$。对该类应用 Theorem 8.3.15，得到

括号中正是 $|F_n(t)-F(t)|$。

证明目标：由 uniform deviation 控制 ERM 的 excess risk。

完整证明：令 $\Delta=\sup_{f\in\mathcal F}|R_n(f)-R(f)|$。ERM 定义给出 $R_n(f_n^*)\le R_n(f^*)$。于是

故 $R(f_n^*)-R(f^*)\le2\Delta$。对期望取上界，只需控制损失函数类 $\mathcal L=\{(f-T)^2:f\in\mathcal F\}$ 的 uniform deviation。Boolean 情形下 $(f-T)^2$ 表示 $f$ 与 $T$ 是否不同，映射 $f\mapsto(f-T)^2$ 保持 VC dimension。Theorem 8.3.15 给出 $\mathbb E\Delta\le C\sqrt{\operatorname{vc}(\mathcal F)/n}$，结论成立。

证明目标：用 admissible sequence 控制 subgaussian process 上确界。

完整证明：取任意 admissible sequence $(T_k)$，并对每个 $t$ 取 $\pi_k(t)\in T_k$ 使 $d(t,\pi_k(t))=d(t,T_k)$。写 telescope sum：

第 $k$ 层可能出现的 pair 数不超过 $|T_k||T_{k-1}|\le2^{2^k}2^{2^{k-1}}\le2^{2^{k+1}}$。每个增量的 $\psi_2$ 范数至多 $K[d(t,T_k)+d(t,T_{k-1})]$。Subgaussian 最大值估计给出该层贡献不超过

若按每个 $t$ 累加，而不是把 supremum 提前到每一层，就得到

最后对 admissible sequence 取 infimum，得到 $CK\gamma_2(T,d)$。

证明目标：用 generic chaining 与 majorizing measure 比较 subgaussian process 和 Gaussian process。

完整证明：令 $d(t,s)=\|Y_t-Y_s\|_{L^2}$。假设给出 $\|X_t-X_s\|_{\psi_2}\le Kd(t,s)$，所以 Theorem 8.5.2 得

对 Gaussian process $Y$，Talagrand majorizing measure theorem 给出 $\gamma_2(T,d)\le C\mathbb E\sup_tY_t$。合并即可。

证明目标：把 Talagrand comparison 写成 Gaussian width 形式。

完整证明：取 canonical Gaussian process $Y_x=\langle g,x\rangle$，$x\in T$。其 canonical metric 为 $\|x-y\|_2$。若 $\|X_x-X_y\|_{\psi_2}\le K\|x-y\|_2$，Corollary 8.5.6 给出

证明目标：控制 $\sup_{x\in T,y\in S}\langle Ax,y\rangle$。

完整证明：设 $X_{xy}=\langle Ax,y\rangle=\sum_i y_i\langle A_i,x\rangle$。对 $(x,y),(u,v)$，分解

第一项是独立 subgaussian 行的线性组合，$\psi_2$ 范数至多 $CK\|x-u\|_2\|y\|_2\le CK\operatorname{rad}(S)\|x-u\|_2$。第二项同理至多 $CK\operatorname{rad}(T)\|y-v\|_2$。因此

定义 Gaussian comparison process

其中 $g,h$ 独立标准 Gaussian。它的 $L^2$ 增量控制右侧到常数因子。Talagrand comparison 给出

最后分离 supremum：

结论成立。

证明目标：说明积分上限可取 $\operatorname{diam}(T)$。

完整证明：若 $\varepsilon>\operatorname{diam}(T)$，任取 $t_0\in T$，则 $T\subset B(t_0,\varepsilon)$，所以 $\mathcal N(T,d,\varepsilon)=1$。因此 $\log\mathcal N=0$，该尺度以后对 Dudley integral 没有贡献。

证明目标：证明 $\log\mathcal N(\mathcal F,\|\cdot\|_\infty,\varepsilon)\le C/\varepsilon$。

完整证明：把 $[0,1]$ 划分为 $m=\lceil c/\varepsilon\rceil$ 个小区间。对每个格点，函数值位于 $[0,1]$，用步长 $c\varepsilon$ 量化。Lipschitz 条件使相邻格点的真实函数值相差至多 $1/m\le C\varepsilon$，因此只需记录第一个格点值和每一步量化后的增量，选择数至多 $\exp(Cm)$。用分段线性插值生成 net，任意 $f$ 与其量化插值的 sup norm 距离至多 $\varepsilon$。故 covering number 至多 $e^{C/\varepsilon}$。

证明目标：证明 intervals 的 VC dimension 不超过 $2$。

完整证明：取任意三个有序点 $x_1<x_2<x_3$。标记 $(0,1,0)$ 要求区间包含 $x_2$ 但不包含 $x_1,x_3$。任何区间若包含中间点并排除两端，可以取很短区间实现；但标记 $(1,0,1)$ 要求同时包含 $x_1,x_3$ 又排除 $x_2$。区间的凸性说明包含两端必包含中间点，因此该标记不能实现。故三个点不能被 shattered。

证明目标：说明 $\mathbb R^2$ 中 half-planes 的 VC dimension 小于 $4$。

完整证明：若四点中有一点在其余三点凸包内，将内部点标记为 $1$、外部三点标记为 $0$，任何包含内部点的半平面若排除三个外部点，会与凸包包含关系矛盾。若四点为凸四边形，按对角线交替标记两个相对顶点为 $1$、另两个为 $0$。半平面与凸四边形的交是凸集，不可能只取两个相对顶点而不取其间边界结构。因此四点不能全被 shattered。

证明目标：说明 generic chaining 至少与 Dudley 一样强。

完整证明：给定每个尺度的 optimal $2^{-k}$-net $T_k$，可把它稀疏化或重排成 admissible sequence。对该序列，任意 $t$ 满足 $d(t,T_k)\le2^{-k}$，于是

右侧就是 Dudley 型 sum。对 nets 取 infimum 得 $\gamma_2$ 被 Dudley functional 控制。

证明目标：补齐 $\langle Ax,y\rangle$ 的 subgaussian increment。

完整证明：写差值为 $\sum_i y_i\langle A_i,x-u\rangle+\sum_i(y_i-v_i)\langle A_i,u\rangle$。第一和是独立均值零 subgaussian 变量的加权和，$\psi_2$ 范数至多 $CK(\sum_i y_i^2\|x-u\|_2^2)^{1/2}=CK\|y\|_2\|x-u\|_2$。第二和同理至多 $CK\|y-v\|_2\|u\|_2$。再用 $\|y\|_2\le\operatorname{rad}(S)$、$\|u\|_2\le\operatorname{rad}(T)$ 即得。

证明目标：把 Dudley chaining 升级为高概率界。

完整证明：在 Theorem 8.1.4 的第 $k$ 层，对所有候选 pair 的最大增量使用 subgaussian tail：

以概率至少 $1-2e^{-z_k^2}$ 成立。取 $z_k=u+k$，则 $\sum_ke^{-z_k^2}\le Ce^{-u^2}$。对 $k$ 求和，得到 Dudley sum 加上 $CK\sum_k2^{-k}(u+k)\le CK(u+1)$。按直径尺度恢复一般情形。

证明目标：用 Gaussian concentration 证明高概率版。

完整证明：设 $Z=\sup_t(X_t-X_{t_0})$。由 Dudley inequality，$\mathbb EZ$ 由 entropy integral 控制。作为 underlying Gaussian vector 的函数，$Z$ 的 Lipschitz 常数等于 $\operatorname{diam}(T,d)$，因为改变 Gaussian realization 时所有线性泛函变化由 canonical metric 控制。Gaussian concentration 给出 $Z\le\mathbb EZ+C\operatorname{diam}(T)u$，概率至少 $1-e^{-u^2}$。合并即得。

证明目标：证明 dyadic sum 与 integral 等价到常数。

完整证明：令 $f(\varepsilon)=\sqrt{\log\mathcal N(T,d,\varepsilon)}$，则 $f$ 随 $\varepsilon$ 下降而不增。对区间 $I_k=[2^{-k-1},2^{-k}]$，有 $f(2^{-k})\le f(\varepsilon)\le f(2^{-k-1})$。因此

对 $k$ 求和并平移指标，得到 integral 与 dyadic sum 的双向常数比较。

证明目标：对 $T_n=\{e_k/\sqrt{1+\log k}:1\le k\le n\}$，证明 $w(T_n)$ 一致有界，但 Dudley integral 随 $n$ 发散。

完整证明：令 $g=(g_1,\dots,g_n)$ 为标准 Gaussian。由于

只需控制右侧。对 $u\ge2$，union bound 与 Gaussian tail 给出

对 $u$ 积分，得到 $\sup_n w(T_n)\le C$。

下面证明 Dudley integral 发散。取整数 $j\ge2$，令 $m_j=\lfloor e^{j^2}\rfloor$。只要 $m_j\le n$，前 $m_j$ 个点两两距离满足

因此当 $\varepsilon\le c/(2j)$ 时，覆盖这 $m_j$ 个点至少需要 $m_j$ 个球，故

在互不相交的区间 $\varepsilon\in[c/(2(j+1)),c/(2j)]$ 上积分，每段贡献至少

对所有 $j\le c\sqrt{\log n}$ 求和，得到 Dudley integral 至少为 $c\sum_{j\le c\sqrt{\log n}}1/j$，随 $n\to\infty$ 发散。

证明目标：证明 Sudakov functional $s(T)$ 与 Dudley integral $d(T)$ 至多相差 $\log n$ 因子。

完整证明：记 $f(\varepsilon)=\sqrt{\log\mathcal N(T,\varepsilon)}$，并设 $D=\operatorname{diam}(T)$。若 $D=0$，结论平凡；以下设 $D>0$。下界来自单个尺度：对任意 $\varepsilon>0$，在区间 $[\varepsilon/2,\varepsilon]$ 上有 $f(t)\ge f(\varepsilon)$，所以

对 $\varepsilon$ 取上确界，得到 $s(T)\le2d(T)$，即按绝对常数等价的 $s(T)\lesssim d(T)$。

证明反向上界。尺度归一化令 $D=1$。由 dyadic 分解，

把和分成 $2^{-k}\ge n^{-2}$ 与 $2^{-k}<n^{-2}$ 两部分。第一部分只有 $O(\log n)$ 项，而且由 $s(T)$ 定义，$2^{-k}f(2^{-k})\le s(T)$，所以贡献至多 $C\log n\,s(T)$。

第二部分用体积覆盖界。把 $T$ 平移进半径 $1$ 的 Euclidean ball 中，则

因此

另一方面，若 $D=1$，存在两点距离为 $1$，故 $\mathcal N(T,1/3)\ge2$，从而 $s(T)\ge c$。所以细尺度贡献也被 $Cs(T)$ 控制。恢复尺度 $D$ 后同样成立，得到 $d(T)\le C\log n\,s(T)$。

证明目标：证明 Dudley integral 的下限可提高到 $a=cw(T)/\sqrt n$。

完整证明：令 $X_t=\langle g,t\rangle$，$g\sim N(0,I_n)$。固定 $\delta>0$，取 $\delta$-net $T_\delta$，并对每个 $t\in T$ 取 $\pi(t)\in T_\delta$ 使 $\|t-\pi(t)\|_2\le\delta$。则

第一项用 Dudley chaining 但只从尺度 $\delta$ 到 $b=\operatorname{diam}(T)$，得到

第二项中所有残差 $t-\pi(t)$ 都落在 $\delta B_2^n$，所以

合并得

选择 $\delta=a=c_0w(T)/\sqrt n$，其中 $c_0>0$ 足够小，使 $\delta\sqrt n\le w(T)/2$。把这一项移到左边，即得

若 $a\ge b$，右端区间为空只可能发生在 $w(T)$ 与 $b\sqrt n$ 同阶的平凡边界；把 $c_0$ 再取小即可保证 $a\le b$，或由 $w(T)\le b\,\mathbb E\|g\|_2$ 直接吸收。

证明目标：把 $\psi_2$ 增量版本改成 $\psi_1$ 增量版本。

完整证明：Dudley chaining 分解不变。第 $k$ 层每个增量的 $\psi_1$ 范数至多 $CK2^{-k}$。Subexponential 最大值估计为 $\mathbb E\max_{j\le N}Z_j\le C\|Z_j\|_{\psi_1}\log N$。因此第 $k$ 层贡献为 $CK2^{-k}\log\mathcal N(T,d,2^{-k})$。把 dyadic sum 转成 integral，得到

证明目标：控制 $d(s,t)\le\delta$ 的局部增量上确界。

完整证明：对每个 $t$ 考虑局部集合 $B(t,\delta)$，或直接对过程 $Y_{s,t}=X_s-X_t$ 以索引集合 $\{(s,t):d(s,t)\le\delta\}$ 应用 chaining。该过程的自然尺度最大为 $\delta$，覆盖可由 $T$ 的 $\varepsilon$-covering 控制。因此 Dudley integral 只需从 $0$ 积到 $\delta$，得到

证明目标：证明一维 Lipschitz 函数类 entropy bound。

完整证明：见 [隐藏验证](#proof-check-8-2-lipschitz-covering)。将区间网格化，量化函数值并用 Lipschitz 条件控制格点间误差，得到 $\mathcal N\le e^{C/\varepsilon}$。

证明目标：推广 Theorem 8.2.3 到 $[0,1]^d$。

完整证明：用 $\ell_\infty$ 网格把 $[0,1]^d$ 划成边长 $\varepsilon$ 的小方块，格点数为 $O(\varepsilon^{-d})$。量化每个格点函数值并用 Lipschitz 条件插值，得到 $\log\mathcal N(\mathcal F,\|\cdot\|_\infty,\varepsilon)\le C\varepsilon^{-d}$。经验过程增量仍有 $n^{-1/2}\|\cdot\|_\infty$ 因子。用截断 Dudley bound

优化 $\delta$：当 $d=2$ 得 $C(\log n)/\sqrt n$；当 $d>2$，取 $\delta\asymp n^{-1/d}$ 得 $Cn^{-1/d}$。恢复 Lipschitz 常数 $L$ 即得。

证明目标：证明 empirical process 的 symmetrization。

完整证明：令 $X_i'$ 是独立副本。由 Jensen，

引入 Rademacher $\varepsilon_i$，差值分布在乘 $\varepsilon_i$ 后不变，因此右侧等于 $\mathbb E\sup_f|n^{-1}\sum_i\varepsilon_i(f(X_i)-f(X_i'))|$。三角不等式与两个样本同分布给出至多 $2\mathbb E\sup_f|n^{-1}\sum_i\varepsilon_if(X_i)|$。

证明目标：证明两个区间并的 VC dimension 为 $4$。

完整证明：四个有序点可被 shattered：任意标记为 $1$ 的点集合在有序线上最多分成两个连续块，用两个区间分别覆盖。五个点不能被 shattered，因为交替标记 $1,0,1,0,1$ 需要三个互不相连的正块，两个区间并无法实现。因此 VC dimension 为 $4$。

证明目标：证明平面中圆周指标类的 VC dimension 等于 $3$。

完整证明：先证下界。取三个非共线点 $x_1,x_2,x_3$。空标记可由一条远离三点的圆实现；单点标记可取一条很小的圆只经过该点；两点标记可取经过这两点但不经过第三点的圆，因为经过两点的圆心在垂直平分线上连续移动，只有至多两个位置会同时经过第三点；三点全为 $1$ 时取三点确定的外接圆。因此这三个点被 shattered，VC dimension 至少为 $3$。

再证上界。任取四个点。若它们不共圆，则“全为 $1$”的标记无法由任何圆周实现。若它们共圆，则任取其中三个点标记为 $1$、剩下一个标记为 $0$。经过三个非共线点的圆唯一，正是这四点所在的圆，因此必然也经过第四点；若四点中有三点共线，则三个共线点本身就不能同时落在一条非退化圆上。于是任意四点都不能被 shattered，VC dimension 至多为 $3$。

证明目标：证明轴对齐矩形的 VC dimension 为 $4$。

完整证明：取四个点位于菱形的上、下、左、右极值位置。任意正标记点集可用其坐标最小外接矩形实现，并避开负标记点。五个点中至少有一个点在其余点的坐标极值矩形内部，或可由二维偏序论证得到不可分标记；将该内部点标为 $0$，围成它的点标为 $1$，任何轴对齐矩形若包含这些 $1$ 点也包含内部点。故 VC dimension 为 $4$。

证明目标：证明轴对齐正方形的 VC dimension 为 $3$。

完整证明：三个点可取为直角三角形的三个顶点，调节正方形左下角和边长可实现全部标记。四个点不能被 shattered：正方形只有三个有效自由度 $a,b,d$，且包含条件为 $a\le x\le a+d$、$b\le y\le b+d$。Radon 型分离或投影到坐标轴后可构造一个标记，使所需的横向跨度和纵向跨度不相容。因此 VC dimension 为 $3$。

证明目标：证明无顶点数限制的凸多边形类 VC dimension 无限。

完整证明：对任意 $N$，取 $N$ 个点位于同一圆周上并处于凸位置。任意选定正标记点，取这些正点的凸包；若正点为空取空多边形，若全体为正取包含所有点的多边形。由于所有样本点为凸位置，未选点不在所选点凸包内部。因此每种标记都可由某个凸多边形实现，VC dimension 为无限。

证明目标：证明 half-spaces 的 VC dimension 为 $n+1$。

完整证明：下界取 $\mathbb R^n$ 中仿射独立的 $n+1$ 个点。任意二元标记可由 separating hyperplane 实现，这是仿射独立点的线性插值性质。上界使用 Radon theorem：任意 $n+2$ 个点可分成两个 disjoint subsets，其凸包相交。把一个 subset 标为 $1$，另一个标为 $0$。若存在 half-space 实现该标记，则其边界超平面严格分离两个凸包，矛盾。因此 VC dimension 为 $n+1$。

证明目标：证明 $\operatorname{vc}(\mathcal F)\le\dim(\mathcal F)$。

完整证明：若 $\mathcal F$ shatter 了 $m$ 点 $x_1,\dots,x_m$，则对每个 $j$，存在 $f_j\in\mathcal F$ 在 $x_j$ 取 $1$ 而在其余 $x_i$ 取 $0$。这些 restrictions 是 $\mathbb R^m$ 的标准基，因此作为函数在该点集上的限制线性无关。若原函数间有非平凡线性关系，限制后也会有关系，矛盾。故 $\mathcal F$ 至少含 $m$ 个线性无关函数，$m\le\dim(\mathcal F)$。

证明目标：用 Hamming ball 证明两个引理 sharp。

完整证明：令 $\mathcal F$ 为长度 $n$、至多 $d$ 个 $1$ 的 binary strings。其大小为 $\sum_{k=0}^d\binom nk$。任意大小不超过 $d$ 的坐标集都被 shattered，因为可以在这些坐标上指定任意 $1$ 集合，且总 $1$ 数不超过 $d$；大小 $d+1$ 的集合不能被全 $1$ 标记 shattered。因此 VC dimension 为 $d$，Sauer-Shelah 上界取等号。Shattered subsets 正好是大小不超过 $d$ 的坐标集，数量也为 $\sum_{k=0}^d\binom nk=|\mathcal F|$，Pajor lemma 也取等号。

证明目标：证明 growth function 只有指数或多项式两种增长。

完整证明：若对所有 $n$ 都有 $\Pi_{\mathcal F}(n)=2^n$，则为指数型。否则存在最小 $d+1$ 使 $\Pi_{\mathcal F}(d+1)<2^{d+1}$，这表示 $\operatorname{vc}(\mathcal F)\le d$。由 Sauer-Shelah，所有 $n$ 满足 $\Pi_{\mathcal F}(n)\le\sum_{k=0}^d\binom nk\le(en/d)^d$，为多项式型。

证明目标：证明 $k$ 个 VC dimension 至多为 $d$ 的 Boolean 类，经任意固定 Boolean 公式组合后，VC dimension 至多 $Cdk\log k$。

完整证明：设组合类 $\mathcal F$ shatter 了某个 $m$ 点集合 $\Omega_m$。则 $\mathcal F$ 在 $\Omega_m$ 上产生 $2^m$ 个不同标记。另一方面，对每个 $i$，Sauer-Shelah lemma 给出

当 $m\ge d$；若 $m<d$，结论显然成立。固定公式 $\phi$ 后，输出标记完全由 $k$ 个输入 restriction 决定，因此

取对数并令 $y=m/(dk)$，得到

这个不等式推出 $y\le C\log(e k)$：若 $y>4C_0\log(e k)$ 且 $C$ 取足够大，则 $\log(e k y)\le y/(2C_0)$，与上式矛盾。于是 $m\le Cdk\log(e k)$。当 $k\ge2$ 时这就是 $Cdk\log k$；$k=1$ 时直接由假设得到 $\operatorname{vc}(\mathcal F)\le d$。

证明目标：控制 $\operatorname{vc}(\mathcal F\cup\mathcal G)$。

完整证明：若 union 类 shatter 了 $m$ 点，则 $2^m\le \Pi_{\mathcal F}(m)+\Pi_{\mathcal G}(m)$。若 $d_F=\operatorname{vc}(\mathcal F)$、$d_G=\operatorname{vc}(\mathcal G)$，Sauer-Shelah 给出右侧至多 $\sum_{k\le d_F}\binom mk+\sum_{k\le d_G}\binom mk$。当 $m>d_F+d_G+1$ 时，这个和小于 $2^m$，可由二项式对称性或 induction 验证。因此 $\operatorname{vc}(\mathcal F\cup\mathcal G)\le d_F+d_G+1$。取前缀类与后缀类可构造等号例子。

证明目标：说明 Theorem 8.3.13 在 $\varepsilon\ge1$ 时的形式。

完整证明：Boolean functions 的 $L^2$ 距离至多 $1$。若 $\varepsilon\ge1$，一个 ball 即可覆盖整个类，所以 $\mathcal N(\mathcal F,L^2(\mu),\varepsilon)=1$。若使用 open balls 或严格半径，可将常数改为 $2$；对 entropy integral 没有影响。

证明目标：用 Sauer-Shelah 直接证明弱一点的 VC LLN。

完整证明：在样本点 $X_1,\dots,X_n$ 上，函数类 restrictions 数至多 $(en/d)^d$。Symmetrization 后条件于样本，Rademacher process 的上确界只在这有限多个 restrictions 上取最大。Subgaussian 最大值估计给出

乘以 symmetrization 的常数，得到弱版界。

证明目标：用 VC LLN 同时学习所有一维投影 CDF。

完整证明：考虑集合类 $\{x:\langle x,u\rangle\le t\}$，这是 $\mathbb R^n$ 中 half-spaces，VC dimension 为 $n+1$。将 Theorem 8.3.15 应用于其指标函数类，得到

证明目标：证明 random hyperplane signs 保持球面角距离。

完整证明：对固定 $u,v$，一行 Gaussian $g$ 的 sign 不同当且仅当随机超平面 $g^\perp$ 分开 $u,v$。旋转不变性说明该概率等于球面角距离 $\rho(u,v)/\pi$。因此 Hamming distance 的期望为 $\rho(u,v)/\pi$。要做 uniform bound，考虑由成对点 $(u,v)$ 诱导的 half-space disagreement 指标类。该类可表示为两个 half-space 指标的布尔组合，VC dimension 为 $O(n)$。VC law of large numbers 给出 uniform 偏差 $C\sqrt{n/m}$，并用 Markov 或高概率版本得到概率 $0.99$ 结论。

证明目标：在只假设小球反集中条件 (8.55) 时，用 VC law 证明 tall random matrix 的最小奇异值下界，并说明尺度最优。

完整证明：令 $A$ 的第 $i$ 行为 $X_i$。对每个 $u\in S^{n-1}$ 定义 Boolean 函数

集合 $\{x:|\langle x,u\rangle|\ge\varepsilon\}$ 是两个 half-spaces 的并，因此函数类 $\mathcal F=\{f_u:u\in S^{n-1}\}$ 的 VC dimension 至多 $C n$。由假设，$\mathbb Ef_u(X)\ge\delta$ 对所有 $u$ 成立。Theorem 8.3.15 的高概率形式给出，当 $m\ge C\delta^{-2}n$ 时，以概率至少 $0.99$，

在该事件上，对每个 $u$ 都有 $\sum_i f_u(X_i)\ge0.99\delta m$。这些指标等于 $1$ 的行满足 $|\langle X_i,u\rangle|\ge\varepsilon$，所以

对 $u\in S^{n-1}$ 取下确界，得到 $s_n(A)\ge c\varepsilon\sqrt{\delta m}$。把 $C$ 调大、常数吸收到 $0.99$ 形式中，即得题设下界。

最优性可由稀疏行分布看出。取 $X=\varepsilon\theta$ 的概率为 $\delta$，其中 $\theta$ 在球面上取足够各向的分布；其余概率取一个极小向量，使 (8.55) 仍由非零部分贡献。于是有效行数 $N=\#\{i:X_i\ne0\}$ 服从 $\operatorname{Bin}(m,\delta)$，且 $\mathbb EN\le\delta m$。条件在 $N$ 上，$A$ 的非零部分最多只有 $N$ 行，最小奇异值的尺度不能超过 $C\varepsilon\sqrt N$。由 Jensen 不等式，$\mathbb E s_n(A)\le C\varepsilon\mathbb E\sqrt N\le C\varepsilon\sqrt{\delta m}$；调节非零部分的尺度常数可得到题中 $1.01$ 形式。这说明结论中的 $\varepsilon\sqrt{\delta m}$ 量级无法改进。

证明目标：证明 Boolean 函数类若是 uniform Glivenko-Cantelli，则 VC dimension 必须有限。

完整证明：反设 $\operatorname{vc}(\mathcal F)=\infty$。任取 $N$，存在被 $\mathcal F$ shattered 的有限集 $\Lambda=\{x_1,\dots,x_N\}$。令 $P$ 为 $\Lambda$ 上的均匀分布，并取样本 $X_1,\dots,X_m$。若 $N\ge4m$，则样本至多覆盖 $m$ 个不同点，所以未被观察的点数至少 $N-m\ge3N/4$。

在 $\Lambda$ 上，$\mathcal F$ 能实现任意 $0/1$ 标记。给定样本点集合 $S$ 后，取一个函数 $f\in\mathcal F$ 使 $f=0$ 在所有样本点上，同时 $f=1$ 在 $\Lambda\setminus S$ 上。则经验均值为 $P_m f=0$，而总体均值满足

于是 $\sup_{f\in\mathcal F}|P_mf-Pf|\ge3/4$ 对每个样本都成立。uniform Glivenko-Cantelli 要求存在 $m$ 使该上确界在概率或期望意义下趋于 $0$，这与上面的构造矛盾。因此 VC dimension 必有限。

证明目标：证明损失类与原 Boolean 类 VC dimension 相同。

完整证明：对 Boolean $f,h$，$(f-h)^2=f\oplus h$，即与固定函数 $h$ 做逐点异或。对任意有限点集，映射 $f|_\Lambda\mapsto(f\oplus h)|_\Lambda$ 是所有二元标记集合上的双射。因此一个点集被 $\mathcal F$ shattered 当且仅当被 $\{(f-h)^2:f\in\mathcal F\}$ shattered，VC dimension 相同。

证明目标：把学习理论扩展到随机标签。

完整证明：令风险为 $R(f)=\mathbb E(f(X)-Y)^2$ 或 Boolean classification 中的 $\mathbb P\{f(X)\ne Y\}$。经验风险为样本平均损失。ERM excess risk 的代数分解仍成立：$R(f_n^*)-R(f^*)\le2\sup_f|R_n(f)-R(f)|$。若 Boolean 情形，损失类 $\ell_f(x,y)=\mathbf1_{\{f(x)\ne y\}}$ 在扩展域 $\Omega\times\{0,1\}$ 上的 VC dimension 与 $\mathcal F$ 同阶。应用 VC LLN 得同样的 $C\sqrt{\operatorname{vc}(\mathcal F)/n}$ 泛化界。

证明目标：用 Lipschitz LLN 控制实值 ERM。

完整证明：风险为 $R(f)=\mathbb E(f(X)-T(X))^2$，经验风险为样本平均。ERM excess risk 仍由 $2\sup_f|R_n(f)-R(f)|$ 控制。若 $f,T\in[0,1]$ 且 $1$-Lipschitz，则损失函数 $(f-T)^2$ 仍有有界 Lipschitz 常数，因为平方函数在 $[-1,1]$ 上 Lipschitz。Theorem 8.2.3 应用于该损失类，得到 uniform deviation $C/\sqrt n$，从而 $\mathbb ER(f_n^*)\le R(f^*)+C/\sqrt n$。

证明目标：证明当样本数 $n<\operatorname{vc}(\mathcal F)/2$ 时，存在分布和 target function 使任何学习算法都有常数级错误。

完整证明：取被 $\mathcal F$ shattered 的集合 $\Lambda$，大小 $2n$，并令 $P$ 为 $\Lambda$ 上的均匀分布。随机选择一个标记向量 $\sigma\in\{0,1\}^{\Lambda}$，由于 $\Lambda$ 被 shattered，存在 $f_\sigma\in\mathcal F$ 在 $\Lambda$ 上实现该标记。把 $T=f_\sigma$ 作为 target。

任意学习算法看到 $n$ 个样本后，只知道这些样本点上的标签。令 $U$ 为未出现在样本中的点集合。独立均匀抽样下，$\mathbb E|U|\ge 2n(1-1/(2n))^n\ge c n$。对任意 $x\in U$，条件在训练数据上，$\sigma(x)$ 仍是独立 fair bit，因此算法在 $x$ 上的预测错误概率至少 $1/2$。于是对随机 target 和训练集取期望，算法输出 $\hat f$ 的风险满足

因此存在某个 target 和训练样本分布使该算法错误至少为常数。若 VC dimension 无限，则对任意样本数都可取这样的 shattered 集合，所以没有统一可靠学习保证。

证明目标：证明 $\gamma_2$ 被 Dudley integral 控制。

完整证明：取 dyadic nets $S_j$，半径 $\varepsilon_j$ 使 $|S_j|\le\mathcal N(T,\varepsilon_j)$。把这些 nets 按 cardinality budget $2^{2^k}$ 分配为 admissible sequence $T_k$。则 $d(t,T_k)$ 由相应 entropy scale 控制，求和 $\sum_k2^{k/2}d(t,T_k)$ 可通过分部求和转成 $\int_0^\infty\sqrt{\log\mathcal N(T,\varepsilon)}d\varepsilon$。对 $t$ 取 supremum 和对序列取 infimum，得到结论。

证明目标：对 $T=\{0\}\cup\{e_k/\sqrt{1+\log k}:1\le k\le n\}$ 证明 $\gamma_2(T)$ 有界，而 Dudley sum 随 $n$ 发散。

完整证明：记 $t_k=e_k/\sqrt{1+\log k}$，并按 $k$ 从小到大排序。构造 admissible sequence 如下：令 $T_j=\{0,t_1,\dots,t_{N_j}\}$，其中 $N_j=\min(n,\lfloor e^{2^j}\rfloor)$，再在需要时删减到满足 $|T_j|\le2^{2^j}$ 的常数倍版本。常数倍差异可通过平移指标吸收，所以该序列 admissible。

若 $1\le k\le N_j$，则 $d(t_k,T_j)=0$。若 $k>N_j$，取 $0\in T_j$ 得

设 $j(k)$ 为第一个满足 $N_j\ge k$ 的层，则 $2^{j(k)}\asymp\log k$。因此对任意 $t_k$，

对 $t=0$ 路径代价为 $0$，故对所有 $t\in T$ 的上确界有界，得到 $\gamma_2(T)\le C$。

再看 Dudley sum。任何 admissible sequence 在第 $j$ 层最多含 $2^{2^j}$ 个点。若 $2^{2^j}\le n/2$，则至少有一个 $k>2^{2^j}$ 的点未被选入 $T_j$，因而

于是该层 Dudley 项满足 $2^{j/2}\sup_t d(t,T_j)\ge c$。满足 $2^{2^j}\le n/2$ 的层数为 $\asymp\log\log n$，所以 Dudley sum 至少为 $c\log\log n$，随 $n\to\infty$ 发散。这说明把 supremum 放到求和外面的 $\gamma_2$ functional 可以严格优于 Dudley sum。

证明目标：证明 generic chaining 的高概率版。

完整证明：选择 $\kappa$ 使 $2^{\kappa/2}\asymp u$。链从 $t_0$ 直接跳到 $\pi_\kappa(t)$，这一步的大小由 $\operatorname{diam}(T)$ 与 $u$ 控制。之后对 $k\ge\kappa$ 的每层使用 subgaussian tail，并取 $z_k\asymp2^{k/2}+u$，再对所有 admissible pairs 和所有 $k$ 做 union bound。尾项求和得到 $C[\gamma_2(T,d)+u\operatorname{diam}(T)]$，概率至少 $1-2e^{-u^2}$。

证明目标：用 generic chaining 控制一般 empirical process。

完整证明：对 $X_f=n^{-1}\sum_i f(X_i)-\mathbb Ef(X)$，若 $\|f(X)-g(X)\|_{\psi_2}\le d(f,g)$，则中心化与独立和估计给出

应用 Theorem 8.5.2 得

对绝对值可将索引类扩大为 $\mathcal F\cup(-\mathcal F)$ 或固定基点后控制正负两侧，常数不变。

证明目标：证明 expectation、tail 与 moment 版本。

完整证明：在 $T\cup\{0\}$ 上应用 Corollary 8.5.8，得到 $\mathbb E\sup_{x\in T}|X_x|\le CK\gamma(T)$。高概率版使用 Exercise 8.35 应用于 Euclidean metric；canonical Gaussian complexity 给出中心项 $w(T)$，粗跳给出 $u\operatorname{rad}(T)$。Moment bound 由尾积分得到：

由于 $\gamma(T)$ 控制 radius 项到常数因子，得到题设形式。

证明目标：无独立性假设下控制 subgaussian vector 的 $\ell^p$ norm。

完整证明：写 $\|X\|_p=\sup_{y\in B_{p'}^N}\langle X,y\rangle$。过程 $X_y=\langle X,y\rangle$ 满足 $\|X_y-X_z\|_{\psi_2}\le K\|y-z\|_2$。Corollary 8.5.8 给出 $\mathbb E\|X\|_p\le CKw(B_{p'}^N)$。由第 7 章 $\ell^q$ ball 的 width 计算，若 $p\le\log N$ 得 $CK\sqrt p\,N^{1/p}$；若 $p>\log N$ 得 $CK\sqrt{\log N}$。这包括 $p=\infty$ 的情形。

证明目标：在 Gaussian 矩阵情形证明 Chevet 上界可取常数 $1$，并证明相反方向的绝对常数下界。

完整证明：令

其中 $A$ 的元素独立 $N(0,1)$。再令 $g\sim N(0,I_n)$、$h\sim N(0,I_m)$ 独立，并设

两者都是 centered Gaussian processes。对任意 $(x,y),(x',y')$，有

用分解 $xy^\top-x'y'^\top=(x-x')y^\top+x'(y-y')^\top$ 以及 $\|y\|_2\le\operatorname{rad}(S)$、$\|x'\|_2\le\operatorname{rad}(T)$，得到

右边正是 $Y$ 的 canonical metric 按三角不等式控制的尺度。Sudakov-Fernique 比较给出

这就是常数 $1$ 的 Gaussian Chevet 上界。

下界分两步。取 $y_0\in S$ 使 $\|y_0\|_2\ge\frac12\operatorname{rad}(S)$，则

同理，固定 $x_0\in T$ 且 $\|x_0\|_2\ge\frac12\operatorname{rad}(T)$，得到下界 $c\,\operatorname{rad}(T)w(S)$。由于左侧非负，且两个下界分别成立，最大值至少控制二者和的一半：

证明目标：给 Chevet 上确界加尾界。

完整证明：在 Theorem 8.6.1 中已经证明 process $X_{xy}$ 的增量由 product metric 控制。对该过程使用 Talagrand comparison 的高概率版本或 generic chaining 高概率版，得到

概率至少 $1-2e^{-u^2}$。最后一项来自 product index 的 diameter。

证明目标：用 Chevet 控制 $\|A\|_{p\to q}$。

完整证明：由 duality，

把 Theorem 8.6.1 应用于 $T=B_p^n$、$S=B_{q'}^m$。半径为 $\operatorname{rad}(B_p^n)=r(n,p)$、$\operatorname{rad}(B_{q'}^m)=r(m,q')$，Gaussian width 为 $w(B_p^n)=w(n,p)$、$w(B_{q'}^m)=w(m,q')$。代入得到上界。Gaussian 矩阵的下界由 Exercise 8.39 的 reverse Chevet 给出，故同阶 sharp。