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 学习性中相应现象的理解可能会带来新的见解。