Notes/机器学习/深度学习模型/0-基础知识/6-学习理论.md

title, tags

title	tags
6-学习理论	学习理论 VC维度 PAC学习 数学基础

大规模学习理论

本章梳理统计学习理论的核心数学框架，从 PAC 学习、VC 维、Rademacher 复杂度出发，建立深度神经网络泛化能力的理论根基。重点覆盖神经网络学习理论、泛化与优化的交互（双下降现象）、算法稳定性分析以及信息论泛化界。

---

1. PAC 学习框架

1.1 PAC 学习定义

定义 1.1（PAC 学习）
设 \mathcal{D} 为输入空间 \mathcal{X} 上的数据分布，c: \mathcal{X} \to \{0,1\} 为目标概念（Target Concept），\mathcal{H} 为假设空间。称假设空间 \mathcal{H} 是 PAC 可学习的，如果存在学习算法 $\mathcal{A}$，使得对任意 $\epsilon > 0$（精度参数）和 $\delta > 0$（置信参数），以至少 1-\delta 的概率，满足

R(h) := \mathbb{P}_{(x,y)\sim\mathcal{D}}[h(x) \neq c(x)] \leq \epsilon

其中 h = \mathcal{A}(S) 为算法在样本 S 上的输出，样本数 m 至多为某个函数 $m_{\mathcal{H}}(\epsilon, \delta)$。

定义 1.2（ERM — Empirical Risk Minimizer）
经验风险最小化算法定义为

\hat{h} = \arg\min_{h \in \mathcal{H}} \hat{R}(h), \quad \hat{R}(h) = \frac{1}{m} \sum_{i=1}^m \mathbf{1}\{h(x_i) \neq y_i\}

其中 \hat{R}(h) 为经验风险，R(h) 为泛化风险（期望风险）。

1.2 有限假设空间下的泛化界

定理 1.1（Hoeffding 不等式 + 联合界）
设 \mathcal{H} 为有限假设空间，$|\mathcal{H}| = k$。对任意 $h \in \mathcal{H}$，由 Hoeffding 不等式，

\mathbb{P}\left( |R(h) - \hat{R}(h)| \geq \epsilon \right) \leq 2 \exp(-2m\epsilon^2)

对所有 h \in \mathcal{H} 应用联合界（Union Bound），令失败概率至多为 $\delta$：

k \cdot 2 \exp(-2m\epsilon^2) \leq \delta \quad \Longrightarrow \quad \exp(-2m\epsilon^2) \leq \frac{\delta}{2k}

解得

\epsilon = \sqrt{\frac{\ln(2k/\delta)}{2m}}

定理 1.2（有限假设空间泛化界）
以至少 1-\delta 的概率，对所有 h \in \mathcal{H} 有

R(h) \leq \hat{R}(h) + \sqrt{\frac{\ln |\mathcal{H}| + \ln(1/\delta)}{2m}}

证明：

对每个特定假设 $h \in \mathcal{H}$，定义事件 $E_h = {|R(h) - \hat{R}(h)| > \epsilon}$。由 Hoeffding 不等式 $\mathbb{P}(E_h) \leq 2e^{-2m\epsilon^2}$。

由 Union Bound：

\mathbb{P}\left(\bigcup_{h \in \mathcal{H}} E_h\right) \leq \sum_{h \in \mathcal{H}} \mathbb{P}(E_h) \leq 2|\mathcal{H}| e^{-2m\epsilon^2}

设此上界等于 $\delta$，得

2|\mathcal{H}| e^{-2m\epsilon^2} = \delta \quad \Longrightarrow \quad e^{-2m\epsilon^2} = \frac{\delta}{2|\mathcal{H}|}

-2m\epsilon^2 = \ln\delta - \ln(2|\mathcal{H}|) \quad \Longrightarrow \quad \epsilon^2 = \frac{\ln(2|\mathcal{H}|/\delta)}{2m}

取 $\epsilon = \sqrt{\frac{\ln(2|\mathcal{H}|/\delta)}{2m}}$，整理即得

R(h) \leq \hat{R}(h) + \sqrt{\frac{\ln |\mathcal{H}| + \ln(1/\delta)}{2m}}

推论 1.1
令 h^* = \arg\min_{h \in \mathcal{H}} R(h) 为最优假设，则以至少 1-\delta 的概率：

R(\hat{h}) - R(h^*) \leq 2\sqrt{\frac{\ln |\mathcal{H}| + \ln(1/\delta)}{2m}}

即 ERM 的 excess risk 被该上界控制。

---

2. VC 维与 Rademacher 复杂度

2.1 VC 维定义

定义 2.1（打散 Shattering）
设 \mathcal{H} 为定义在 \mathcal{X} 上的二值函数类，C = \{x_1, \dots, x_k\} \subseteq \mathcal{X} 为一个点集。如果对 C 上的任意一种标记 $(y_1, \dots, y_k) \in {0,1}^k$，都存在 h \in \mathcal{H} 使得 $h(x_i) = y_i$（对所有 i 成立），则称 C 被 \mathcal{H} 打散。

定义 2.2（VC 维）
\mathcal{H} 的 Vapnik-Chervonenkis 维定义为

\text{VC}(\mathcal{H}) = \max\{ k : \exists \{x_1, \dots, x_k\} \subseteq \mathcal{X} \text{ 被 } \mathcal{H} \text{ 打散} \}

备注：本节 VC 维为二分类定义；深度学习回归任务常用伪维数（Pseudo-dimension），定义为实值函数类被"打散"的最多点数，概念上为二分类 VC 维的自然推广。

若对任意 k 都存在可被打散的 k 点集，则 $\text{VC}(\mathcal{H}) = \infty$。

定义 2.3（Growth 函数）
Growth 函数定义为

\Pi_{\mathcal{H}}(m) = \max_{x_1,\dots,x_m \in \mathcal{X}} |\{ (h(x_1), \dots, h(x_m)) : h \in \mathcal{H} \}|

即 m 个点上产生的不同二值向量（ dichotomy ）的最大数目。

定理 2.1（Sauer-Shelah Lemma）
若 $\text{VC}(\mathcal{H}) = d$，则对所有 $m \geq 1$：

\Pi_{\mathcal{H}}(m) \leq \sum_{i=0}^d \binom{m}{i} \leq \left(\frac{em}{d}\right)^d \quad \text{（当 } m > d \text{ 时）}

当 d 固定、m \to \infty 时，$\Pi_{\mathcal{H}}(m) = O(m^d)$。

2.2 VC 维泛化界

定理 2.2（VC 维泛化界）
设 \mathcal{H} 的 VC 维为 $d_{\text{VC}}$，样本数为 $n$。以至少 1-\delta 的概率，对所有 h \in \mathcal{H} 有

R(h) \leq \hat{R}(h) + O\left( \sqrt{ \frac{ d_{\text{VC}} \ln(n/d_{\text{VC}}) + \ln(1/\delta) }{ n } } \right)

关键引理：一致收敛界

引理 2.1（Symmetrization）
对任意假设类 \mathcal{H} 和样本 $S$：

\mathbb{P}_S\left( \sup_{h \in \mathcal{H}} (R(h) - \hat{R}(h)) \geq \epsilon \right) \leq 2 \mathbb{P}_{S,S'}\left( \sup_{h \in \mathcal{H}} \frac{1}{n} \sum_{i=1}^n \sigma_i (h(x_i) - h(x_i')) \geq \epsilon \right)

其中 \sigma_i 为独立 Rademacher 随机变量，S' = \{(x_i', y_i')\} 为独立复本（ghost sample）。

引理 2.2（Massart's Lemma）
设 \mathcal{A} \subseteq \{0,1\}^n 为有限集合，则

\mathbb{E}_\sigma\left[ \sup_{a \in \mathcal{A}} \frac{1}{n} \sum_{i=1}^n \sigma_i a_i \right] \leq \sqrt{\frac{2 \ln |\mathcal{A}|}{n}}

定理 2.2 的证明思路：

由 Symmetrization 和 Massart's Lemma，对任意 $h \in \mathcal{H}$：

\mathbb{E}_S[\sup_{h \in \mathcal{H}} (R(h) - \hat{R}(h))] \leq 2 \mathbb{E}_S[\mathfrak{R}_n(\mathcal{H})]

其中 \mathfrak{R}_n(\mathcal{H}) 为 Rademacher 复杂度（见下节）。由 Sauer-Shelah Lemma：

\mathfrak{R}_n(\mathcal{H}) \leq \sqrt{\frac{2d_{\text{VC}} \ln(2n/d_{\text{VC}})}{n}}

代入即得 VC 维泛化界。

2.3 Rademacher 复杂度

定义 2.4（Rademacher 复杂度）
设 \mathcal{H} 为从 \mathcal{X} 到 \mathbb{R} 的函数类，S = (x_1, \dots, x_n) 为固定样本。则

\mathfrak{R}_n(\mathcal{H}) = \mathbb{E}_{\boldsymbol{\sigma} \sim \{-1,+1\}^n}\left[ \sup_{h \in \mathcal{H}} \frac{1}{n} \sum_{i=1}^n \sigma_i h(x_i) \right]

其中 $\boldsymbol{\sigma} = (\sigma_1, \dots, \sigma_n)$，各 \sigma_i 独立同分布，$\mathbb{P}(\sigma_i = +1) = \mathbb{P}(\sigma_i = -1) = 1/2$。

定义 2.5（经验 Rademacher 复杂度）

\hat{\mathfrak{R}}_S(\mathcal{H}) = \mathbb{E}_{\boldsymbol{\sigma}}\left[ \sup_{h \in \mathcal{H}} \frac{1}{n} \sum_{i=1}^n \sigma_i h(x_i) \bigg| S \right]

引理 2.3（Rademacher 复杂度的期望界）
对函数类 $\mathcal{H}$，有

\mathbb{E}_S[\hat{\mathfrak{R}}_S(\mathcal{H})] = \mathfrak{R}_n(\mathcal{H})

且 $\mathfrak{R}_n(\mathcal{H}) \leq \sqrt{\frac{\ln |\mathcal{H}|}{2n}}$（有限 \mathcal{H} 的特殊情形）。

定理 2.3（Rademacher 泛化界）
以至少 1-\delta 的概率，对所有 h \in \mathcal{H} 有

R(h) \leq \hat{R}(h) + 2 \mathfrak{R}_n(\mathcal{H}) + O\left( \sqrt{\frac{\ln(1/\delta)}{n}} \right)

更精确地：

R(h) \leq \hat{R}(h) + 2 \mathfrak{R}_n(\mathcal{H}) + 3\sqrt{\frac{\ln(2/\delta)}{2n}}

证明：

步骤 1：使用 Symmetrization

\mathbb{E}_S[\sup_{h \in \mathcal{H}}(R(h) - \hat{R}(h))] \leq 2 \mathfrak{R}_n(\mathcal{H})

步骤 2：McDiarmid 不等式（ bounded differences ）

由于更换单个样本 x_i 只会使 \sup_{h \in \mathcal{H}}(R(h) - \hat{R}(h)) 改变至多 $2/n$，由 McDiarmid 不等式：

\mathbb{P}\left( \sup_{h \in \mathcal{H}}(R(h) - \hat{R}(h)) \geq 2\mathfrak{R}_n(\mathcal{H}) + \epsilon \right) \leq \exp\left(-\frac{n\epsilon^2}{2}\right)

令 $\delta = \exp(-n\epsilon^2/2)$，解得 $\epsilon = \sqrt{\frac{2\ln(1/\delta)}{n}} = \sqrt{\frac{\ln(1/\delta)}{n/2}} = O(\sqrt{\frac{\ln(1/\delta)}{n}})$。

步骤 3：结合ERM 形式

对ERM $\hat{h} = \arg\min_{h \in \mathcal{H}} \hat{R}(h)$，有

R(\hat{h}) \leq \hat{R}(\hat{h}) + \sup_{h \in \mathcal{H}}(R(h) - \hat{R}(h)) \leq \hat{R}(\hat{h}) + 2\mathfrak{R}_n(\mathcal{H}) + O\left(\sqrt{\frac{\ln(1/\delta)}{n}}\right)

推论 2.1（组合 VC 维与 Rademacher）
由 Massart's Lemma 和 Sauer-Shelah Lemma：

\mathfrak{R}_n(\mathcal{H}) \leq \sqrt{\frac{2d_{\text{VC}} \ln(2n/d_{\text{VC}})}{n}}

因此 Rademacher 界在 d_{\text{VC}} 较小时优于纯 VC 维界（对 n 的依赖从 O(\sqrt{\ln n / n}) 改善为 $O(\sqrt{1/n})$）。

2.4 函数空间的 Rademacher 复杂度

对于实值函数空间 $\mathcal{F}$，定义

\mathfrak{R}_n(\mathcal{F}) = \mathbb{E}_{\sigma, (x_i)_i}\left[ \sup_{f \in \mathcal{F}} \frac{1}{n} \sum_{i=1}^n \sigma_i f(x_i) \right]

引理 2.4（Contraction Lemma）
设 \phi: \mathbb{R} \to \mathbb{R} 为 $\rho$-Lipschitz 函数（即 $|\phi(a) - \phi(b)| \leq \rho|a-b|$），则

\mathfrak{R}_n(\phi \circ \mathcal{F}) \leq \rho \cdot \mathfrak{R}_n(\mathcal{F})

其中 $\phi \circ \mathcal{F} = {\phi \circ f : f \in \mathcal{F}}$。

---

3. 神经网络学习理论

3.1 深度网络的 VC 维上界

定理 3.1（经典 VC 维上界，Bartlett et al.）
设神经网络具有 W 个参数（权重），激活函数为 ReLU 或任何分段线性函数，层数为 $L$，深度为 $d$。则

\text{VC}(\mathcal{H}_{\text{NN}}) = O(W \log W)

更精确地，对于具有 L 层、参数总数为 W 的前馈网络：

\text{VC}(\mathcal{H}_{\text{NN}}) \leq W \log W + L \log W = O(W \log W)

证明思路：

1. 每一层参数量为 $W_i$，将该层的权重矩阵 \mathbf{W}_i 分解为符号向量和幅度向量的乘积。
2. 由 ReLU 的分段线性性质，整个网络将输入空间划分为至多 O(W)^L 个线性区域。
3. 每个线性区域对应一个线性分类器，因此整个网络产生的不同二值向量数目至多为 $O(W)^L$。
4. 由 Sauer-Shelah 引理，$\text{VC} \leq \log_2 O(W)^L = O(L \log W)$。结合总参数 W 的上界，整理得 $O(W \log W)$。

推论 3.1（深度 vs. 宽度）
VC 维上界与网络深度 L 只呈对数依赖（$L \log W$），而与宽度呈线性依赖。因此，增加深度比增加宽度更容易在保持 VC 维可控的同时提升表达能力。

3.2 过参数化区域的行为

定义 3.1（过参数化）
设网络参数数量 $W \gg n$（样本数），或更精确地，网络宽度（每层神经元数）随 n 增长且满足 $W = \omega(n)$。

现象 3.1（过参数化与可实现性）
在过参数化设定下，神经网络在训练集上可以零误差拟合（$\hat{R}(h) = 0$），即存在参数配置使得 h(x_i) = y_i 对所有训练样本成立。

关键发现：过参数化并不导致过拟合——这是深度学习"悖论"的核心，即高度过参数化的网络仍能泛化良好。

定理 3.2（过参数化网络的外推）
设 f^* 为目标函数，\hat{f} 为过参数化神经网络的最小范数解或最近解。在适当条件下：

\| f^* - \hat{f} \|_2 \leq O\left( \frac{\|f^*\|_{\mathcal{H}}}{\sqrt{n}} \right)

其中 \|\cdot\|_{\mathcal{H}} 是 RKHS 范数（见 NTK 理论）。

3.3 Neural Tangent Kernel (NTK) 与无穷宽网络

定义 3.2（Neural Tangent Kernel）
设 f(\mathbf{x}, \theta): \mathbb{R}^d \times \mathbb{R}^W \to \mathbb{R} 为神经网络的输出。NTK 定义为

K_{\text{NTK}}(\mathbf{x}, \mathbf{x}') = \nabla_\theta f(\mathbf{x}, \theta) \cdot \nabla_\theta f(\mathbf{x}', \theta)

其中 \nabla_\theta f 为关于参数 \theta 的梯度。

定理 3.3（Jacot et al., 2018 — NTK 极限）
当网络宽度 $m \to \infty$（各层宽度按特定比例初始化），且参数以 \theta = \theta_0 + \eta \theta' 更新（\eta 很小）时，网络输出 f(\mathbf{x}, \theta) 的演化由常微分方程描述：

\frac{d f(\mathbf{x}, \theta(t))}{dt} = \eta \sum_{j=1}^n K_{\text{NTK}}(\mathbf{x}, \mathbf{x}_j) \cdot \frac{\partial \mathcal{L}}{\partial f(\mathbf{x}_j, \theta)}

且 K_{\text{NTK}}(\mathbf{x}, \mathbf{x}') 在训练过程中保持不变（等于其初始值）。

推论 3.2（无穷宽网络 = 核ridge回归）
在 NTK 极限下，神经网络的训练行为等价于在特征空间 \phi(\mathbf{x}) 中进行 kernel ridge regression，其核矩阵为 $K_{\text{NTK}}$：

\hat{\mathbf{w}} = (K_{\text{NTK}} + \lambda I)^{-1} \mathbf{y}

对应的泛化风险为

R \leq O\left( \frac{\|f^*\|_{K_{\text{NTK}}}^2}{\lambda n} + \lambda \right)

定义 3.3（NTK 范数与复杂度）
定义 RKHS 空间 $\mathcal{H}{K{\text{NTK}}}$，配备内积 $\langle f, g \rangle_{K} = \langle f, g \rangle_{K_{\text{NTK}}}$。则

\mathfrak{R}_n(\mathcal{H}_{K_{\text{NTK}}}) = \mathbb{E}_\sigma\left[ \sup_{\|f\|_K \leq 1} \frac{1}{n} \sum_{i=1}^n \sigma_i f(x_i) \right] = \frac{\sqrt{\mathrm{tr}(K)}}{n}

备注：该式仅对训练集核矩阵、RKHS 单位范数球成立，其中 $\mathrm{tr}(K) = \sum_{i=1}^n K(x_i, x_i)$。

3.4 表征复杂度（Representation Complexity）

定义 3.4（表征复杂度）
设 \Phi: \mathbb{R}^d \to \mathbb{R}^k 为神经网络从输入到某隐藏层的表示映射。表征复杂度定义为表示空间 \Phi(\mathcal{X}) 在某种度量下的复杂度，例如covering number 或 metric entropy。

定理 3.4（深度网络的表征能力）
设有一个深度为 L 、宽度为 W 的 ReLU 网络。则对任意连续函数 $f: [0,1]^d \to \mathbb{R}$，存在一个神经网络 \hat{f} 以精度 \epsilon 一致逼近 $f$，其参数量上界为

W = O\left( \left(\frac{1}{\epsilon}\right)^{d/L} \cdot L^{O(1)} \right)

这意味着：深度指数级地提升表征效率（对 1/\epsilon 的依赖从 O(\epsilon^{-d}) 降低为 $O(\epsilon^{-d/L})$）。

定理 3.5（功率定理，Power of Depth）
存在函数族 \{f_d\} 使得：

• 深度 d 网络需要 O(\exp(d)) 个参数才能以精度 \epsilon 逼近；
• 深度 d+1 网络只需要 O(\text{poly}(d)/\epsilon) 个参数。

即深度带来指数级的表征能力提升。

---

4. 泛化与优化的交互

4.1 双下降（Double Descent）现象

定义 4.1（双下降现象）
设模型族 ${\mathcal{H}m}{m=1}^\infty$（例如 m 参数的神经网络），训练损失 \hat{R}(\hat{h}_m) 和测试风险 R(\hat{h}_m) 随 $m$（模型规模）变化呈现以下模式：

1. classical regime（$m \ll n$）：R 随 m 增加而减小（偏差减小），至某个临界点 m^* 后开始上升（方差增大），形成 classical bias-variance trade-off。
2. interpolation regime（$m \approx m^*$）：R 达到峰值，此时模型刚好能零误差拟合训练数据（插值阈值）。
3. double descent regime（$m \gg n$）：R 再次下降，在严重过参数化区域反而泛化良好。

定理 4.1（双下降的理论上界）
设 \hat{m} 为使得 \hat{R}(\hat{h}_m) = 0 的最小参数数量（插值阈值），则在过参数化区域（$m \gg \hat{m}$），有

R(\hat{h}_m) \leq O\left( \frac{\|f^*\|_{\mathcal{H}}^2}{n} + \frac{\text{complexity}(\mathcal{H}_m)}{n^2} \right)

其中 \text{complexity}(\mathcal{H}_m) 随 m 先增后减（相对于 m 的函数）。第二项在 m 极大时衰减，使得总风险再次降低——这是双下降的数学解释之一。

图示（文字描述）：

R(h)
  |            ****  <- interpolation peak
  |          **    **
  |        **         **     ----->  double descent (test risk)
  |      **               **  /
  |    **                    **
  |  **                       ***  (overparameterized)
  |**
  +---------------------------------> m (parameters)
        ^           ^           ^
     m_GB(under)  m*(interp)  m >> n (overparam)

4.2 奥卡姆剃刀定理（PAC 版本）

定理 4.2（奥卡姆剃刀 — PAC 形式）
设 \mathcal{D} 为数据分布，c 为目标概念，\mathcal{H} 为假设空间。假设存在某个 h^* \in \mathcal{H} 使得 $R(h^*) = 0$。令 \hat{h} 为 ERM 解。以至少 1-\delta 的概率：

R(\hat{h}) \leq \frac{\ln |\mathcal{H}| + \ln(1/\delta)}{n}

更一般地，对非零风险的 $h^*$：

R(\hat{h}) \leq R(h^*) + \sqrt{\frac{\ln |\mathcal{H}| + \ln(1/\delta)}{2n}}

直觉解释：最简单的（参数最少或假设最简洁的）能解释数据的假设，泛化风险最小。这正是奥卡姆剃刀"如无必要，勿增实体"在 PAC 框架下的形式化。

定义 4.2（描述长度）
设 L(h) 为假设 h 的描述长度（如 Kolmogorov 复杂度或参数数量）。奥卡姆剃刀的 PAC 版本可表述为：偏好描述长度短 L(h) 小的假设，其泛化界中额外项为 $O(\sqrt{L(h)/n})$。

4.3 一致收敛与自学（Uniform vs. Non-Uniform Convergence）

定义 4.3（一致收敛）
称假设类 \mathcal{H} 具有一致收敛（Uniform Convergence）性质，如果

\lim_{n \to \infty} \sup_{h \in \mathcal{H}} |R(h) - \hat{R}(h)| = 0 \quad \text{（依概率）}

即收敛速度与 h 的选择无关。

定义 4.4（非一致收敛）
仅满足对每个固定的 h \in \mathcal{H} 有 $|R(h) - \hat{R}(h)| \to 0$，但收敛速度可能依赖于 $h$。

定理 4.3（一致收敛的充分条件）
若 \mathcal{H} 的 Rademacher 复杂度满足 $\mathfrak{R}_n(\mathcal{H}) \to 0$（当 $n \to \infty$），则 \mathcal{H} 具有一致收敛性。

关键区别：

• 一致收敛：所有 h \in \mathcal{H} 同时与真实风险接近，收敛率统一。
• 非一致收敛：每个 h 单独收敛，但不同 h 的收敛率可以不同。

深度学习中的一个关键问题是：常用的神经网络假设类在大规模训练下是否满足一致收敛？答案是否定的——深度网络 \mathcal{H}_{\text{NN}} 的一致收敛上界非常弱（VC 维 O(W\log W) 导致 $O(\sqrt{W\log W/n})$），远差于实际观察到的泛化表现。这催生了研究"非一致收敛"或"隐式正则化"的新方向。

---

5. 稳定性与泛化

统一假设：本章默认损失函数 \ell 有界于 $[0,1]$（即 $0 \leq \ell \leq 1$），i.i.d. 采样，分布平稳。

5.1 随机梯度下降的稳定性分析

定义 5.1（Uniform Stability）
设算法 \mathcal{A} 作用在数据集 S = \{z_1, \dots, z_n\} 上，S^i = \{z_1, \dots, z_{i-1}, z_i', z_{i+1}, \dots, z_n\} 为替换第 i 个样本后的数据集。算法 \mathcal{A} 称为 $\beta$-uniformly stable，如果

\beta = \sup_{S, i, z'} \|\mathcal{A}(S) - \mathcal{A}(S^i)\|_{\text{输出空间}} \leq \beta(n)

对泛化风险而言，通常考虑输出为函数时的差值：

\sup_{S} |R_S(\mathcal{A}(S)) - R_{S^i}(\mathcal{A}(S^i))| \leq \beta

其中 $R_S(h) = \frac{1}{n} \sum_{i=1}^n \ell(h, z_i)$。

定理 5.1（稳定性 implies 泛化）
如果算法 \mathcal{A} 是 $\beta$-uniformly stable 的，则

|R(\mathcal{A}(S)) - \hat{R}_S(\mathcal{A}(S))| \leq 2\beta + O\left( \sqrt{\frac{\ln(1/\delta)}{n}} \right)

以至少 1-\delta 的概率成立。

证明思路：

定义 Z_i 为第 i 个样本的随机变量。设 $h_S = \mathcal{A}(S)$，$h_{S^i} = \mathcal{A}(S^i)$。

考虑泛化误差的期望：

\mathbb{E}_S[R(h_S) - \hat{R}_S(h_S)] = \mathbb{E}_{S, i, z_i'}[R(h_S) - \hat{R}_S(h_S)]

通过对称化（用 S^i 替换 S 中第 i 个样本），并利用 uniform stability 条件 |R_S(h_S) - R_S(h_{S^i})| \leq \beta 和 $|R_{S^i}(h_{S^i}) - \hat{R}S(h{S^i})| \leq \epsilon$（Hoeffding），经过一系列不等式操作可得上界。

5.2 SGD 的稳定性

定理 5.2（SGD 的均匀稳定性）
设目标函数 F(\theta) = \frac{1}{n} \sum_{i=1}^n \ell(h_\theta(x_i), y_i) 为 $L$-光滑的凸或 $\beta$-光滑的非凸函数。设 SGD 以步长 \eta 更新，噪声方差有界 $\sigma^2$。则经过 T 步迭代后，输出 \theta_T 的均匀稳定性满足

\beta \leq \frac{L}{n} \sum_{t=1}^T \eta_t + \sigma \sqrt{\frac{T}{n}} \cdot \max_t \eta_t

在典型设置 \eta_t = \eta / \sqrt{t} 下：

\beta \leq O\left( \frac{L \eta \sqrt{T}}{n} + \frac{\sigma \eta}{\sqrt{n}} \right)

推论 5.1（步长与稳定性）
步长越大，算法稳定性越差（\beta 越大），但过小的步长导致优化收敛慢。存在最优步长平衡这一 trade-off。

定理 5.3（Hardt et al., 2016 — SGD 的非一致稳定性）
对于 $\beta$-光滑的损失函数和固定步长 $\eta \leq 1/\beta$，SGD 输出的解 \hat{\theta} 满足

|R(\hat{\theta}) - \hat{R}(\hat{\theta})| \leq O\left( \frac{\beta \eta T}{n} + \frac{\sigma \sqrt{T \eta}}{n} \right)

5.3 稳定性与泛化的关系定理

定理 5.4（泛化上界 via 稳定性）
设 \mathcal{A} 为 $\beta$-uniformly stable 算法，损失函数 \ell 有界于 $[0, M]$。则

\mathbb{E}_S[R(\mathcal{A}(S))] \leq \mathbb{E}_S[\hat{R}_S(\mathcal{A}(S))] + 2\beta

证明：

定义虚拟样本 S' 为 S 的 i.i.d. 复本。则

\mathbb{E}_S[R(h_S)] = \mathbb{E}_{S, S'}[\hat{R}_{S'}(h_S)]

由三角不等式和稳定性：

|\hat{R}_{S'}(h_S) - \hat{R}_S(h_S)| \leq |R_{S'}(h_S) - \hat{R}_{S'}(h_S)| + |R_S(h_S) - \hat{R}_S(h_S)| + \underbrace{|R_S(h_S) - R_{S'}(h_S)|}_{\leq \beta \text{ by stability}}

取期望并利用 Hoeffding 不等式可得 $\mathbb{E}[|R_S(h_S) - \hat{R}_S(h_S)|] \leq \sqrt{\frac{M^2 \ln 2}{2n}}$，结合稳定性项即得结论。

---

6. 信息论泛化界

6.1 压缩界（Compression Bounds）

定义 6.1（压缩学习）
称学习算法 \mathcal{A} 具有压缩率 $\kappa$（$0 < \kappa < 1$），如果存在随机映射 $Q: (\mathcal{X} \times \mathcal{Y})^n \to \mathcal{Z}^\kappa$（\kappa n 个 bit）和重建函数 $g: \mathcal{Z}^\kappa \times \mathcal{X} \to \mathcal{Y}$，使得从 m = \kappa n 个压缩样本即可恢复出一个假设 $h$，且该假设在原始 n 样本上的经验风险不超过 $0$。

定理 6.1（压缩界 — Russo & Zou, 2015）
设算法 \mathcal{A} 在输入 S 时输出假设 $h_S$。定义 I-measure（信息论复杂度）：

I(S; h_S) = \mathbb{E}_S\left[ D_{\text{KL}}(p(h|S) \| q(h)) \right]

其中 q(h) 为 h_S 的边缘分布。则泛化误差满足

|R(h_S) - \hat{R}_S(h_S)| \leq \sqrt{\frac{2 I(S; h_S)}{n}} + O\left( \frac{1}{n} \right)

以至少 1-\delta 的概率成立。

证明核心：

利用 Donsker-Varadhan 变换：

\mathbb{E}_S[f(S)] = \mathbb{E}_{S, \sigma}[f(S)] \exp\left( \mathbb{E}_{S, \sigma}[D_{\text{KL}}(p(S)\|q)] \right) \cdot \ldots

更具体地，由 Pinsker 不等式 和数据处理不等式，可建立 $I(S; h) \geq n \cdot \text{泛化误差}^2 / 2$，从而解出泛化误差上界。

推论 6.1（压缩界形式）
若算法 \mathcal{A} 的输出 h 只依赖于 m = \kappa n 个训练样本（压缩），则

I(S; h) \leq \kappa n \cdot \ln(2/\delta)

从而

|R(h) - \hat{R}(h)| \leq O\left( \sqrt{\frac{\kappa \ln(1/\delta)}{}} \right)

6.2 信息瓶颈与泛化

定义 6.2（信息瓶颈，IB）
对随机变量 $X$（输入）、$Y$（标签）和表示 $Z = h(X)$，IB 目标为：

\min_{p(z|x)} I(X; Z) - \beta I(Y; Z)

其中 \beta > 0 为 Lagrange 乘子。

定理 6.2（IB 的泛化解释）
设 Z = h_S(X) 为由算法 \mathcal{A} 和数据集 S 产生的表示。则

I(X; Z | S) \leq I(S; h_S)

且泛化误差可被 I(S; h_S) 控制（定理 6.1）。这建立了 信息瓶颈越小，泛化越好 的理论联系。

关键引理：

I(S; h_S) = \mathbb{E}_S\left[ \ln \frac{p(h_S | S)}{q(h_S)} \right] = \mathbb{E}_S\left[ \ln \frac{1}{q(h_S)} \right] - \mathbb{E}_S\left[ \ln \frac{1}{p(h_S | S)} \right]

右边第一项是 h_S 的边缘熵（与模型复杂度相关），第二项是条件熵（与数据拟合程度相关）。因此 I(S; h_S) 同时编码了复杂度和拟合。

6.3 Stochastic Gradient Langevin Dynamics (SGLD) 的泛化性质

定义 6.3（SGLD）
SGLD 采样算法对参数 \theta 的更新为：

\theta_{t+1} = \theta_t - \eta_t \nabla_\theta \hat{R}(\theta_t) + \sqrt{2\eta_t} \cdot \xi_t

其中 \xi_t \sim \mathcal{N}(0, I) 为各向同性高斯噪声，\eta_t 为步长。

定理 6.3（SGLD 的泛化界）
设损失函数 \ell 为 $L$-光滑且 $\beta$-强凸（关于 $\theta$），步长满足 $\sum_t \eta_t = \infty$，$\sum_t \eta_t^2 < \infty$。设 \pi 为 SGLD 的平稳分布（等同于后验 $p(\theta | S) \propto \exp(-n\hat{R}(\theta))$）。则

\mathbb{E}_\pi[R(\theta)] \leq \mathbb{E}_\pi[\hat{R}(\theta)] + O\left( \frac{L}{n} \sqrt{\sum_t \eta_t^2} \right)

推论 6.2（对比 SGD 与 SGLD）

• SGD（无噪声）：确定性映射 $h = \mathcal{A}(S)$，输出是点估计，I(S; h) 相对较小（通常为 $O(\ln |\mathcal{H}|)$）。
• SGLD：输出是分布 $\pi$，信息论复杂度 I(S; \pi) 可以显著更小，因为噪声注入了"随机性"，减少了算法对具体训练数据的依赖。

定理 6.4（噪声作为正则化）
设 \sigma^2 为 SGLD 噪声方差。则有效信息复杂度为

I(S; \pi) \leq I(S; h_{\text{SGD}}) - \Omega(n \sigma^2)

即 SGLD 通过添加噪声，等价于在信息论复杂度上施加了额外的惩罚，从而改善泛化。

---

附录：核心不等式汇总

不等式	内容	用途
Hoeffding	\mathbb{P}(\|\bar{X} - \mathbb{E}[\bar{X}]\| \geq \epsilon) \leq 2e^{-2n\epsilon^2}	有限假设联合界
McDiarmid	\mathbb{P}(f(X_1,\dots,X_n) - \mathbb{E}[f] \geq \epsilon) \leq e^{-2\epsilon^2 / \sum c_i^2}	浓度不等式
Massart	\mathbb{E}_\sigma[\sup_{a \in \mathcal{A}} \frac{1}{n}\sum \sigma_i a_i] \leq \sqrt{\frac{2\ln\|\mathcal{A}\|}{n}}	Rademacher 复杂度（有限）
Sauer-Shelah	\Pi_{\mathcal{H}}(m) \leq \sum_{i=0}^d \binom{m}{i}	VC 维 growth 函数
Donsker-Varadhan	D_{\text{KL}}(P\|Q) = \sup_{f: \Omega \to \mathbb{R}} \mathbb{E}_P[f] - \ln \mathbb{E}_Q[e^f]	信息论界

---

参考文献

1. Vapnik, V. N. (1998). Statistical Learning Theory. Wiley.
2. Shalev-Shwartz, S., & Ben-David, S. (2014). Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press.
3. Bartlett, P. L., & Mendelson, S. (2002). Rademacher and Gaussian complexities: Risk bounds and structural results. JMLR.
4. Bartlett, P. L., Harvey, N., Liaw, C., & Mehrabian, A. (2019). Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks. JMLR.
5. Jacot, A., Hongler, C., & Gabriel, F. (2018). Neural tangent kernel: Convergence and generalization in neural networks. NeurIPS.
6. Belkin, M., Hsu, D., Ma, S., & Mandal, S. (2019). Reconciling modern machine learning practice and the bias-variance trade-off. PNAS.
7. Hardt, M., Recht, B., & Singer, Y. (2016). Train faster, generalize better: Stability of stochastic gradient descent. ICML.
8. Russo, D., & Zou, J. (2015). Controlling bias in adaptive data analysis using information theory. AISTATS.
9. Tishby, N., & Zaslavsky, N. (2015). Deep learning and the information bottleneck principle. IEEE ITW.
10. Chen, Z., Cao, Y., Zou, D., & Gu, Q. (2020). Maximum likelihood principle and generalization. NeurIPS.