# Black-box Certification and Learning under Adversarial Perturbations

arXiv: https://arxiv.org/abs/2006.16520 · HTML: https://mlsanity.com/paper/2006.16520/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Jun 2020.

## Built on by (most cited first, 13 of 13)

- [Cross-Entropy Loss Functions: Theoretical Analysis and Applications](https://mlsanity.com/paper/2304.07288/) (2023)
- [Adversarially Robust Learning with Unknown Perturbation Sets](https://mlsanity.com/paper/2102.02145/) (2021)
- [A Characterization of Semi-Supervised Adversarially-Robust PAC Learnability](https://mlsanity.com/paper/2202.05420/) (2022)
- [Transductive Robust Learning Guarantees](https://mlsanity.com/paper/2110.10602/) (2021)
- [Adversarially Robust Learning with Tolerance](https://mlsanity.com/paper/2203.00849/) (2022)
- [Adversarially Robust PAC Learnability of Real-Valued Functions](https://mlsanity.com/paper/2206.12977/) (2022)
- [Robust Empirical Risk Minimization with Tolerance](https://mlsanity.com/paper/2210.00635/) (2022)
- [On the Computability of Robust PAC Learning](https://mlsanity.com/paper/2406.10161/) (2024)
- [On Proper Learnability between Average- and Worst-case Robustness](https://mlsanity.com/paper/2211.05656/) (2022)
- [Boosting Barely Robust Learners: A New Perspective on Adversarial Robustness](https://mlsanity.com/paper/2202.05920/) (2022)
- [When are Local Queries Useful for Robust Learning?](https://mlsanity.com/paper/2210.06089/) (2022)
- [On the (Un-)Avoidability of Adversarial Examples](https://mlsanity.com/paper/2106.13326/) (2021)
- [Exact Certification of Neural Networks and Partition Aggregation Ensembles against Label Poisoning](https://mlsanity.com/paper/2604.11416/) (2026)

## Abstract (arXiv)

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.