技术摘要：Bagging 能鲁棒地学习具有线性样本复杂度的 VC 类

问题陈述

本文探讨了学习在测试时对对抗样本具有鲁棒性的预测器的基本挑战。给定实例空间 $\mathcal{X}$，标签空间 $\mathcal{Y} = \{-1, 1\}$，以及由扰动映射 $U: \mathcal{X} \to 2^\mathcal{X}$ 定义的对抗者，目标是学习一个预测器 $\hat{f}$，以最小化总体鲁棒风险（population robust risk）：
$$R_U(\hat{f}; P) = \mathbb{E}_{(X,Y) \sim P} \left[ \sup_{Z \in U(X)} \mathbb{1}\{\hat{f}(Z) \neq Y\} \right]$$
其中 $P$ 是关于 $\mathcal{X} \times \mathcal{Y}$ 的未知分布。

本文研究了具有有限 Vapnik-Chervonenkis (VC) 维数 $d$ 的函数类 $\mathcal{F}$ 的可学习性。先前的研究表明，虽然 VC 类在标准 PAC 设置下是可学习的，但对抗性鲁棒学习面临着重大障碍。具体而言，Montasser, Hanneke, 和 Srebro [2019] 指出：

1. 固有学习（Proper learning，即限制输出属于 $\mathcal{F}$）即使对于 VC 维数为 1 的类也可能失败。
2. 非固有学习（Improper learning）是可能的，但已知的最佳样本复杂度上界是关于 $d$ 的指数级。
3. 现有的非固有算法在计算上是低效的，需要调用 $O(nd)$ 次鲁棒经验风险最小化（RERM）算子，且具有极高的开销。

核心问题在于，是否可以设计出既具有样本效率（对 $d$ 呈线性）又具有算子效率（调用次数少的 RERM）的算法，用于对抗性鲁棒学习。

方法论

作者提出了一种简单的非固有学习算法，该算法结合了 Bagging（自助聚合/Bootstrap Aggregation）与 鲁棒经验风险最小化 (RERM)。

算法 (Bagging Robust ERMs)

给定大小为 $n$ 的训练集 $S$，置信参数 $\delta$，以及一个 RERM 算子 $\hat{f}$：

1. 设置自助样本数量 $N = O(d^\star + \log(1/\delta))$，其中 $d^\star$ 是类 $\mathcal{F}$ 的对偶 VC 维数（dual VC dimension）。
2. 对于每个 $i \in \{1, \dots, N\}$：
   • 从特定范围 $J_n = \{n/4, \dots, n-1\}$ 中随机选择一个大小 $t$。
   • 从长度为 $t$ 的 $S$ 的前缀中，有放回地随机抽取一个大小为 $t$ 的自助数据集 $S'_i$。
   • 在 $S'_i$ 上运行 RERM 算子以获得预测器 $\hat{f}_{S'_i} \in \mathcal{F}$。
3. 输出 $N$ 个预测器的多数投票结果：$\text{MAJ}(\hat{f}_{S'_1}, \dots, \hat{f}_{S'_N})$。

理论方法

其分析偏离了之前的样本压缩论证。相反，它采用了一种专门针对鲁棒风险定制的留一法分析（leave-one-out analysis）：

1. RERM 的分布： 作者分析了在随机子集上训练的 RERM 所产生的误差分布。他们证明，对于随机测试样本 $(X, Y)$ 以及任何扰动 $Z \in U(X)$，RERM 误分类 $Z$ 的比例在期望意义上是很小的（$\tilde{O}(d/n)$）。
2. 留一法界限： 通过将此期望应用于经验分布，他们为“全量 Bagging”预测器（即所有可能自助样本的理想化平均值）建立了鲁棒风险界限。
3. 稀疏化： 由于全量 Bagging 预测器在计算上是不可行的，作者使用一种稀疏化技术（Moran 和 Yehudayoff [2016]）来利用仅有的 $N = O(d^\star)$ 个独立的自助样本来近似聚合投票。这一步将算子复杂度直接与对偶 VC 维数 $d^\star$ 联系起来。

核心贡献与结果

1. 上界：线性样本复杂度

主要结果（定理 1）确立了 VC 类可以用对 VC 维数 $d$ 呈线性关系的样本复杂度进行对抗性鲁棒学习。

• 样本复杂度： $O(d/\epsilon + \frac{1}{\epsilon}\log(1/\delta))$。这相对于之前的 $O(\exp(d))$ 界限实现了指数级的提升。
• 算子复杂度： 该算法进行 $N = O(d^\star)$ 次 RERM 算子调用。
• 计算效率： 该算法是可并行的（不同于之前的 Boosting 方法），并且仅产生 $O(d^\star n)$ 的计算开销。
• 不可知设置（Agnostic Setting）： 通过将此可实现结果与来自不可知设置的归约（Montasser 等人 [2019]）相结合，作者推导出了一个样本复杂度为 $\tilde{O}(\sqrt{d/n})$ 且算子复杂度为 $O(d^\star \log n)$ 的不可知学习器。

2. 下界：对偶 VC 维数的必要性

论文证明了在算子复杂度中对对偶 VC 维数 $d^\star$ 的依赖是不可避免的（定理 2）。

• 结果： 存在 VC 维数为 $d$ 且对偶 VC 维数为 $d^\star = 2^{d+1}-1$ 的类，使得任何调用少于 $d^\star - 1$ 次 RERM 算子的算法都无法实现鲁棒学习，无论提供多少训练样本。
• 启示： 与经典 PAC 学习中只需 $O(\log n)$ 或常数次 ERM 调用不同，对抗性鲁棒学习本质上需要 $\Omega(d^\star)$ 次算子查询。这突显了标准学习与鲁棒学习之间在复杂度上的根本分离。

3. 技术特征

结果表明，Montasser, Hanneke, 和 Srebro [2022] 提出的精细复杂度度量 $\dim(\mathcal{F}, U)$ 被 $d$ 所界定，解决了此前关于该度量可能显著大于 $d$ 的猜想。

重要性与主张

本文声称提供了一个计算高效的鲁棒 PAC 学习“配方”。通过展示简单的 Bagging 启发式方法结合 RERM 如何实现最优样本复杂度，这项工作弥合了理论鲁棒性与实际算法效率之间的鸿沟。

关于本文贡献的核心主张包括：

• 指数级改进： 将样本复杂度从关于 $d$ 的指数级降低到线性级。
• 算子效率： 将算子调用次数从 $O(nd)$减少到$O(d^\star)$，使得该方法对于 RERM 计算可行的类而言是可行的。
• 基本极限： 确立了对偶 VC 维数是鲁棒学习中算子效率的正确屏障，这与 VC 维数在标准学习中的角色形成对比。
• 实际相关性： 该算法的可并行性以及对标准 RERM 算子的依赖（这些算子对应于实践中使用的对抗训练启发式方法）表明，这些理论上的改进可以直接应用于现代深度学习语境。

作者指出，尽管该算法是非固有的（输出的是多数投票而非单个属于 $\mathcal{F}$ 的函数），但这是实现这些界限所必需的，这反映了鲁棒设置中固有学习与非固有学习之间的区别。这项工作将算法效率与可证明的鲁棒性统一起来，表明如果接受非固有学习器并利用对偶 VC 维数，高效的鲁棒学习是可能的。