这篇论文把bagging这个老方法用在了对抗鲁棒学习上，直接打破了之前的上界，而且证明样本复杂度跟VC维线性相关，搞理论或鲁棒学习的人值得看看。
一项新研究证明，VC类在测试时对抗鲁棒学习的样本复杂度可达到关于VC维d的线性，相比Montasser等人2019年的上界实现了指数级改进。该算法将Breiman的bagging（自助聚合）与鲁棒经验风险最小化（RERM）结合，在O(d*)个独立bootstrap样本上计算RERM并输出多数投票，其中d*为对偶VC维。作者还给出下界，表明在该预言机模型中任何学习器至少需要Ω(d*)次RERM调用，即使训练样本任意多。
Bagging Robustly Learns VC Classes with Linear Sample Complexity
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^\star)$ independent bootstrap samples and outputs their majority vote, where $d^\star$ 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^\star)$ calls to an RERM oracle, even when given arbitrarily many training examples.