Reducing Adversarially Robust Learning to Non-Robust PAC Learning
Reducing Adversarially Robust Learning to Non-Robust PAC Learning
复制标题
DOI：
--
复制
发表时间：
2020-10
期刊：
影响因子：
--
通讯作者：
Omar Montasser;Steve Hanneke;N. Srebro
中科院分区：
文献类型：
--
作者：
Omar Montasser;Steve Hanneke;N. Srebro
我们研究将对抗性鲁棒学习简化为标准 PAC 学习的问题，即仅使用黑盒非鲁棒学习器来学习对抗性鲁棒预测器的复杂性。我们给出了一个简化，可以使用任何非鲁棒学习器 $\mathcal{A}$ 对于 $\mathcal{C}$ 鲁棒地学习任何假设类 $\mathcal{C}$。对 $\mathcal{A}$ 的调用次数以对数方式取决于每个示例允许的对抗性扰动的数量，并且我们给出了一个下限，表明这是不可避免的。
We study the problem of reducing adversarially robust learning to standard PAC learning, i.e. the complexity of learning adversarially robust predictors using access to only a black-box non-robust learner. We give a reduction that can robustly learn any hypothesis class $\mathcal{C}$ using any non-robust learner $\mathcal{A}$ for $\mathcal{C}$. The number of calls to $\mathcal{A}$ depends logarithmically on the number of allowed adversarial perturbations per example, and we give a lower bound showing this is unavoidable.