Bagging使VC类对抗鲁棒学习样本复杂度降至线性
Bagging Robustly Learns VC Classes with Linear Sample Complexity
这篇论文把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.
This report is categorized under AITOP's "Papers" desk. Key entities and technical topics under continuous tracking include Bagging, RERM, VC dimension, arXiv.
Source attribution: curated from arXiv cs.LG (@Omar Montasser).
