论文标题
实现功能的对抗性强大的PAC可学习性
Adversarially Robust PAC Learnability of Real-Valued Functions
论文作者
论文摘要
我们使用$ \ ell_p $损失和任意扰动集研究回归设置中测试时间对抗性攻击的鲁棒性。我们解决了哪些功能类在此设置中可以学习的问题。我们表明，在可实现的和不可知的环境中，有限脂肪的脂肪的尺寸都是可以学习的。此外，对于凸功能类，它们甚至可以正确地学习。相比之下，某些非凸功能类别可证明需要不当学习算法。我们的主要技术是基于由脂肪震动尺寸确定的尺寸的对抗性稳健样品压缩方案的构造。在此过程中，我们引入了一种新型的不可知性样品压缩方案，以实现实现的功能，这可能具有独立感兴趣。
We study robustness to test-time adversarial attacks in the regression setting with $\ell_p$ losses and arbitrary perturbation sets. We address the question of which function classes are PAC learnable in this setting. We show that classes of finite fat-shattering dimension are learnable in both realizable and agnostic settings. Moreover, for convex function classes, they are even properly learnable. In contrast, some non-convex function classes provably require improper learning algorithms. Our main technique is based on a construction of an adversarially robust sample compression scheme of a size determined by the fat-shattering dimension. Along the way, we introduce a novel agnostic sample compression scheme for real-valued functions, which may be of independent interest.
