We formally study the problem of classification under adversarial
perturbations from a learner's perspective as well as a third-party who aims at
certifying the robustness of a given black-box classifier. We analyze a
PAC-type framework of semi-supervised learning and identify possibility and
impossibility results for proper learning of VC-classes in this setting. We
further introduce a new setting of black-box certification under limited query
budget, and analyze this for various classes of predictors and perturbation. We
also consider the viewpoint of a black-box adversary that aims at finding
adversarial examples, showing that the existence of an adversary with
polynomial query complexity can imply the existence of a sample efficient
robust learner.

该研究从学习者和第三方认证者的角度正式研究了分类问题，并考虑了半监督学习框架下 VC - 类的适当学习的可能性和不可能性结果。该研究还探讨了黑盒认证在有限查询预算下的黑盒对手视角，提出了一些预测器和扰动类别的分析，并证明了具有多项式查询复杂性的对手的存在可以暗示存在样本高效稳健的学习者。