Black-box Certification and Learning under Adversarial Perturbations

Hassan Ashtiani, Vinayak Pathak, Ruth Urner
Proceedings of the 37th International Conference on Machine Learning, PMLR 119:388-398, 2020.

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.

Cite this Paper


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.} }
Endnote
%0 Conference Paper %T Black-box Certification and Learning under Adversarial Perturbations %A Hassan Ashtiani %A Vinayak Pathak %A Ruth Urner %B Proceedings of the 37th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2020 %E Hal Daumé III %E Aarti Singh %F pmlr-v119-ashtiani20a %I PMLR %P 388--398 %U https://proceedings.mlr.press/v119/ashtiani20a.html %V 119 %X 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.
APA
Ashtiani, H., Pathak, V. & Urner, R.. (2020). Black-box Certification and Learning under Adversarial Perturbations. Proceedings of the 37th International Conference on Machine Learning, in Proceedings of Machine Learning Research 119:388-398 Available from https://proceedings.mlr.press/v119/ashtiani20a.html.

Related Material