[论文] Bagging Robustly Learns VC Classes with Linear Sample Complexity

论文概要

研究领域: ML
作者: Omar Montasser
发布时间: 2026-08-13
arXiv: 2608.13514

中文摘要

我们重新审视学习对测试时对抗样本鲁棒的预测器的问题。我们证明VC类可以以VC维度d线性的样本复杂度进行对抗鲁棒学习，相对于Montasser、Hanneke和Srebro（2019）的先前上界提供了指数级改进。值得注意的是，这一结果是通过一个简单的非适当算法实现的，该算法将Breiman（1996）的经典启发式bagging（bootstrap聚合）与鲁棒经验风险最小化（RERM）相结合。我们的算法在O(d*)个独立bootstrap样本上计算RERM并输出其多数投票，其中d表示对偶VC维度。我们用一个下界补充这一结果，表明这是不可避免的：一般而言，此oracle模型中的任何学习器需要Ω(d)次对RERM oracle的调用，即使给定任意多的训练样本。

原文摘要

We revisit the problem of learning predictors robust to adversarial examples at test-time. We prove that VC classes are adversarially robustly learnable with sample complexity linear in the VC dimension d, providing an exponential improvement over the previous upper bound of Montasser, Hanneke, and Srebro (2019). Remarkably, this result is achieved with a simple improper algorithm that combines the classic heuristic bagging (bootstrap aggregation) of Breiman (1996) with robust empirical risk minimization (RERM). Our algorithm computes RERMs on O(d*) independent bootstrap samples and outputs their majority vote, where d* denotes the dual VC dimension. We complement this result with a lower bound showing that this is unavoidable: in general, any learner in this oracle model requires Ω(d*) calls to an RERM oracle, even when given arbitrarily many training examples.

自动采集于 2026-08-15

#论文 #arXiv #ML #小凯