We initiate the study of computability requirements for adversarially robust
learning. Adversarially robust PAC-type learnability is by now an established
field of research. However, the effects of computability requirements in
PAC-type frameworks are only just starting to emerge. We introduce the problem
of robust computable PAC (robust CPAC) learning and provide some simple
sufficient conditions for this. We then show that learnability in this setup is
not implied by the combination of its components: classes that are both CPAC
and robustly PAC learnable are not necessarily robustly CPAC learnable.
Furthermore, we show that the novel framework exhibits some surprising effects:
for robust CPAC learnability it is not required that the robust loss is
computably evaluable! Towards understanding characterizing properties, we
introduce a novel dimension, the computable robust shattering dimension. We
prove that its finiteness is necessary, but not sufficient for robust CPAC
learnability. This might yield novel insights for the corresponding phenomenon
in the context of robust PAC learnability, where insufficiency of the robust
shattering dimension for learnability has been conjectured, but so far a
resolution has remained elusive.

对抗性强健学习的计算要求进行了研究，引入了鲁棒可计算的 CPAC 学习问题，并提供了一些简单的充分条件。同时，展示了该框架的一些令人惊讶的效果，即对于鲁棒 CPAC 可学习性而言，并不需要鲁棒损失是可计算的。引入了可计算鲁棒破碎维度这一新维度，证明了其有限性对于鲁棒 CPAC 学习性是必要的，但不充分。这对于鲁棒 PAC 学习性中相应现象的理解可能会带来新的见解。

关于健壮性 PAC 学习的可计算性

On the Computability of Robust PAC Learning

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.

通过将对抗性鲁棒学习简化到标准的 PAC 学习问题，即仅使用黑盒非鲁棒性学习器学习鲁棒性预测器的学习复杂度，我们提供了一个降低学习复杂度的方法，并证明了其数学上的正确性。同时，我们也给出了一个必要的下界。

将对抗性鲁棒学习降至非鲁棒 PAC 学习

Reducing Adversarially Robust Learning to Non-Robust PAC Learning

Machine learning models are often susceptible to adversarial perturbations of
their inputs. Even small perturbations can cause state-of-the-art classifiers
with high "standard" accuracy to produce an incorrect prediction with high
confidence. To better understand this phenomenon, we study adversarially robust
learning from the viewpoint of generalization. We show that already in a simple
natural data model, the sample complexity of robust learning can be
significantly larger than that of "standard" learning. This gap is information
theoretic and holds irrespective of the training algorithm or the model family.
We complement our theoretical results with experiments on popular image
classification datasets and show that a similar gap exists here as well. We
postulate that the difficulty of training robust classifiers stems, at least
partially, from this inherently larger sample complexity.

本文研究在简单自然数据模型中，对抗鲁棒学习的样本复杂度可以显著大于标准学习，这个差距是信息理论的，且与训练算法或模型家族无关。作者做了一些实验来证实这个结果。我们可以假设训练鲁棒分类器的困难，至少部分来自这种固有的更大的样本复杂度。