用袋装法结合鲁棒经验风险最小化，实现线性样本复杂度的对抗鲁棒学习。
Bagging Robustly Learns VC Classes with Linear Sample Complexity
- 用多重自助采样生成多个鲁棒模型，投票决定最终预测。
- 样本复杂度仅与双对偶VC维 $d^ullet$ 线性相关，远优于旧有上界。
- 适用于需高效对抗鲁棒性的机器学习场景，如安全关键系统。
我们重新研究了测试时对抗样本下的预测器学习问题。证明了VC类在对抗鲁棒学习下具有线性于VC维 $d$ 的样本复杂度，相比Montasser、Hanneke和Srebro（2019）的上界实现指数级改进。这一结果通过一个简单的非正规算法实现：将Breiman（1996）的经典袋装法与鲁棒经验风险最小化（RERM）结合。该算法在 $O(d^ullet)$ 个独立自助样本上计算RERM，并输出多数投票结果，其中 $d^ullet$ 表示双对偶VC维。我们还给出了下界：在此预言机模型中，任何学习器至少需要 $Ω(d^ullet)$ 次RERM预言机调用，即使拥有任意多训练样本亦然。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。