大规模学习理论

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

1. PAC 学习框架

1.1 PAC 学习定义

定义 1.1（PAC 学习）
设为输入空间上的数据分布，为目标概念（Target Concept），为假设空间。称假设空间是 PAC 可学习的，如果存在学习算法，使得对任意（精度参数）和（置信参数），以至少的概率，满足

其中为算法在样本上的输出，样本数至多为某个函数。

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

其中为经验风险，为泛化风险（期望风险）。

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

定理 1.1（Hoeffding 不等式 + 联合界）
设为有限假设空间，。对任意，由 Hoeffding 不等式，

对所有应用联合界（Union Bound），令失败概率至多为：

解得

定理 1.2（有限假设空间泛化界）
以至少的概率，对所有有

证明：

对每个特定假设，定义事件。由 Hoeffding 不等式。

由 Union Bound：

设此上界等于，得

取，整理即得

推论 1.1
令为最优假设，则以至少的概率：

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

2. VC 维与 Rademacher 复杂度

2.1 VC 维定义

定义 2.1（打散 Shattering）
设为定义在上的二值函数类，为一个点集。如果对上的任意一种标记，都存在使得（对所有成立），则称 被打散。

定义 2.2（VC 维）
的 Vapnik-Chervonenkis 维定义为

被 打 散

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

若对任意都存在可被打散的点集，则。

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

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

定理 2.1（Sauer-Shelah Lemma）
若，则对所有：

（ 当 时 ）

当固定、时，。

2.2 VC 维泛化界

定理 2.2（VC 维泛化界）
设的 VC 维为，样本数为。以至少的概率，对所有有

关键引理：一致收敛界

引理 2.1（Symmetrization）
对任意假设类和样本：

其中为独立 Rademacher 随机变量，为独立复本（ghost sample）。

引理 2.2（Massart’s Lemma）
设为有限集合，则

定理 2.2 的证明思路：

由 Symmetrization 和 Massart’s Lemma，对任意：

其中为 Rademacher 复杂度（见下节）。由 Sauer-Shelah Lemma：

代入即得 VC 维泛化界。

2.3 Rademacher 复杂度

定义 2.4（Rademacher 复杂度）
设为从到的函数类，为固定样本。则

其中，各独立同分布，。

定义 2.5（经验 Rademacher 复杂度）

引理 2.3（Rademacher 复杂度的期望界）
对函数类，有

且（有限的特殊情形）。

定理 2.3（Rademacher 泛化界）
以至少的概率，对所有有

更精确地：

证明：

步骤 1：使用 Symmetrization

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

由于更换单个样本只会使改变至多，由 McDiarmid 不等式：

令，解得。

步骤 3：结合ERM 形式

对ERM ，有

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

因此 Rademacher 界在较小时优于纯 VC 维界（对的依赖从改善为）。

2.4 函数空间的 Rademacher 复杂度

对于实值函数空间，定义

引理 2.4（Contraction Lemma）
设为 -Lipschitz 函数（即），则

其中。

3. 神经网络学习理论

3.1 深度网络的 VC 维上界

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

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

证明思路：

每一层参数量为，将该层的权重矩阵分解为符号向量和幅度向量的乘积。
由 ReLU 的分段线性性质，整个网络将输入空间划分为至多个线性区域。
每个线性区域对应一个线性分类器，因此整个网络产生的不同二值向量数目至多为。
由 Sauer-Shelah 引理，。结合总参数的上界，整理得。

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

3.2 过参数化区域的行为

定义 3.1（过参数化）
设网络参数数量（样本数），或更精确地，网络宽度（每层神经元数）随增长且满足。

现象 3.1（过参数化与可实现性）
在过参数化设定下，神经网络在训练集上可以零误差拟合（），即存在参数配置使得对所有训练样本成立。

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

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

其中是 RKHS 范数（见 NTK 理论）。

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

定义 3.2（Neural Tangent Kernel）
设为神经网络的输出。NTK 定义为

其中为关于参数的梯度。

定理 3.3（Jacot et al., 2018 — NTK 极限）
当网络宽度（各层宽度按特定比例初始化），且参数以更新（很小）时，网络输出的演化由常微分方程描述：

且在训练过程中保持不变（等于其初始值）。

推论 3.2（无穷宽网络 = 核ridge回归）
在 NTK 极限下，神经网络的训练行为等价于在特征空间中进行 kernel ridge regression，其核矩阵为：

对应的泛化风险为

定义 3.3（NTK 范数与复杂度）
定义 RKHS 空间，配备内积。则

备注：该式仅对训练集核矩阵、RKHS 单位范数球成立，其中。

3.4 表征复杂度（Representation Complexity）

定义 3.4（表征复杂度）
设为神经网络从输入到某隐藏层的表示映射。表征复杂度定义为表示空间在某种度量下的复杂度，例如covering number 或 metric entropy。

定理 3.4（深度网络的表征能力）
设有一个深度为、宽度为的 ReLU 网络。则对任意连续函数，存在一个神经网络以精度一致逼近，其参数量上界为

这意味着：深度指数级地提升表征效率（对的依赖从降低为）。

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

深度网络需要个参数才能以精度逼近；
深度网络只需要个参数。

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

4. 泛化与优化的交互

4.1 双下降（Double Descent）现象

定义 4.1（双下降现象）
设模型族（例如参数的神经网络），训练损失和测试风险随（模型规模）变化呈现以下模式：

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

定理 4.1（双下降的理论上界）
设为使得的最小参数数量（插值阈值），则在过参数化区域（），有

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

图示（文字描述）：

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 形式）
设为数据分布，为目标概念，为假设空间。假设存在某个使得。令为 ERM 解。以至少的概率：

更一般地，对非零风险的：

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

定义 4.2（描述长度）
设为假设的描述长度（如 Kolmogorov 复杂度或参数数量）。奥卡姆剃刀的 PAC 版本可表述为：偏好描述长度短小的假设，其泛化界中额外项为。

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

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

（ 依 概 率 ）

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

定义 4.4（非一致收敛）
仅满足对每个固定的有，但收敛速度可能依赖于。

定理 4.3（一致收敛的充分条件）
若的 Rademacher 复杂度满足（当），则具有一致收敛性。

关键区别：

一致收敛：所有同时与真实风险接近，收敛率统一。
非一致收敛：每个单独收敛，但不同的收敛率可以不同。

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

5. 稳定性与泛化

统一假设：本章默认损失函数有界于（即），i.i.d. 采样，分布平稳。

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

定义 5.1（Uniform Stability）
设算法作用在数据集上，为替换第个样本后的数据集。算法称为 -uniformly stable，如果

输 出 空 间

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

其中。

定理 5.1（稳定性 implies 泛化）
如果算法是 -uniformly stable 的，则

以至少的概率成立。

证明思路：

定义为第个样本的随机变量。设，。

考虑泛化误差的期望：

通过对称化（用替换中第个样本），并利用 uniform stability 条件和（Hoeffding），经过一系列不等式操作可得上界。

5.2 SGD 的稳定性

定理 5.2（SGD 的均匀稳定性）
设目标函数为 -光滑的凸或 -光滑的非凸函数。设 SGD 以步长更新，噪声方差有界。则经过步迭代后，输出的均匀稳定性满足

在典型设置下：

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

定理 5.3（Hardt et al., 2016 — SGD 的非一致稳定性）
对于 -光滑的损失函数和固定步长，SGD 输出的解满足

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

定理 5.4（泛化上界 via 稳定性）
设为 -uniformly stable 算法，损失函数有界于。则

证明：

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

由三角不等式和稳定性：

取期望并利用 Hoeffding 不等式可得，结合稳定性项即得结论。

6. 信息论泛化界

6.1 压缩界（Compression Bounds）

定义 6.1（压缩学习）
称学习算法具有压缩率 （），如果存在随机映射（个 bit）和重建函数，使得从个压缩样本即可恢复出一个假设，且该假设在原始样本上的经验风险不超过。

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

其中为的边缘分布。则泛化误差满足

以至少的概率成立。

证明核心：

利用 Donsker-Varadhan 变换：

更具体地，由 Pinsker 不等式 和数据处理不等式，可建立 $泛化误差$ ，从而解出泛化误差上界。

推论 6.1（压缩界形式）
若算法的输出只依赖于个训练样本（压缩），则

从而

6.2 信息瓶颈与泛化

定义 6.2（信息瓶颈，IB）
对随机变量（输入）、（标签）和表示，IB 目标为：

其中为 Lagrange 乘子。

定理 6.2（IB 的泛化解释）
设为由算法和数据集产生的表示。则

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

关键引理：

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

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

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

其中为各向同性高斯噪声，为步长。

定理 6.3（SGLD 的泛化界）
设损失函数为 -光滑且 -强凸（关于），步长满足，。设为 SGLD 的平稳分布（等同于后验）。则

推论 6.2（对比 SGD 与 SGLD）

SGD（无噪声）：确定性映射，输出是点估计，相对较小（通常为）。
SGLD：输出是分布，信息论复杂度可以显著更小，因为噪声注入了”随机性”，减少了算法对具体训练数据的依赖。

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

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

附录：核心不等式汇总

不等式	内容	用途
Hoeffding		有限假设联合界
McDiarmid		浓度不等式
Massart		Rademacher 复杂度（有限）
Sauer-Shelah		VC 维 growth 函数
Donsker-Varadhan		信息论界

参考文献

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

Huajishe Notes

Explorer

6-学习理论