On the Computability of Robust PAC Learning

我们开始研究对抗鲁棒学习的可计算性要求。对抗鲁棒PAC类型的可学习性已经成为一个已经建立的研究领域。然而，在PAC类型的框架中的可计算性要求的影响才刚刚开始显现。我们引入了鲁棒可计算PAC（robust CPAC）学习问题，并提供了一些简单的充分条件。然后，我们展示了在这个设置中的可学习性并不是由其组件的组合所暗示的：既是CPAC又是鲁棒PAC可学习的类并不一定是鲁棒CPAC可学习的类。此外，我们展示了这个新框架展现出一些令人惊讶的效果：对于鲁棒CPAC可学习性，并不需要鲁棒损失是可计算的！为了理解表征性质，我们引入了一个新的维度，即可计算的鲁棒破碎维度。我们证明其有限性是必要的，但不足以保证鲁棒CPAC的可学习性。这可能会为鲁棒PAC可学习性的相应现象提供新的见解，在这种情况下，鲁棒破碎维度的不足已经被猜测是无法学习的，但迄今为止还没有解决。

研究在对抗性环境下，计算要求对PAC学习的影响。论文提出了鲁棒可计算PAC学习的问题，并提供了一些简单的充分条件。

论文介绍了鲁棒可计算PAC（robust CPAC）学习的问题，并提供了一些简单的充分条件。论文还引入了计算鲁棒破碎维度的概念，证明其有限性是必要的，但不足以保证鲁棒CPAC学习的可学习性。

论文展示了一些令人惊讶的效果：对于鲁棒CPAC学习，不要求鲁棒损失是可计算的！论文还提出了一个新的维度，计算鲁棒破碎维度。论文的实验设计使用了哪些数据集，但未提供开源代码。

最近的相关研究包括鲁棒PAC学习的研究，如“Towards Deep Learning Models Resistant to Adversarial Attacks”和“Certified Robustness to Adversarial Examples with Differential Privacy”。