Black-box Certification and Learning under Adversarial Perturbations
Hassan Ashtiani, Vinayak Pathak, Ruth Urner
Abstract
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.
BibTeX
@InProceedings{pmlr-v119-ashtiani20a,
title = {Black-box Certification and Learning under Adversarial Perturbations},
author = {Ashtiani, Hassan and Pathak, Vinayak and Urner, Ruth},
booktitle = {Proceedings of the 37th International Conference on Machine Learning},
pages = {388--398},
year = {2020},
editor = {III, Hal Daumé and Singh, Aarti},
volume = {119},
series = {Proceedings of Machine Learning Research},
month = {13--18 Jul},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v119/ashtiani20a/ashtiani20a.pdf},
url = {https://proceedings.mlr.press/v119/ashtiani20a.html},
abstract = {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.}
}