691 lines
28 KiB
Markdown
691 lines
28 KiB
Markdown
---
|
||
title: 6-学习理论
|
||
tags:
|
||
- 学习理论
|
||
- 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*.
|