# PAC-learning in the presence of evasion adversaries

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

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Jun 2018.

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

- [Recent Advances in Adversarial Training for Adversarial Robustness](https://mlsanity.com/paper/2102.01356/) (2021)
- [Probabilistic Margins for Instance Reweighting in Adversarial Training](https://mlsanity.com/paper/2106.07904/) (2021)
- [Calibration and Consistency of Adversarial Surrogate Losses](https://mlsanity.com/paper/2104.09658/) (2021)
- [Adversarial Robustness with Semi-Infinite Constrained Learning](https://mlsanity.com/paper/2110.15767/) (2021)
- [Probabilistically Robust Learning: Balancing Average- and Worst-case Performance](https://mlsanity.com/paper/2202.01136/) (2022)
- [On the Existence of the Adversarial Bayes Classifier (Extended Version)](https://mlsanity.com/paper/2112.01694/) (2021)
- [Adversarial Rademacher Complexity of Deep Neural Networks](https://mlsanity.com/paper/2211.14966/) (2022)
- [Benign Overfitting in Adversarially Robust Linear Classification](https://mlsanity.com/paper/2112.15250/) (2021)
- [Adversarial robustness of sparse local Lipschitz predictors](https://mlsanity.com/paper/2202.13216/) (2022)
- [Understanding Generalization in Adversarial Training via the Bias-Variance Decomposition](https://mlsanity.com/paper/2103.09947/) (2021)
- [Provable Robustness of Adversarial Training for Learning Halfspaces with Noise](https://mlsanity.com/paper/2104.09437/) (2021)
- [A Law of Robustness beyond Isoperimetry](https://mlsanity.com/paper/2202.11592/) (2022)
- [It Is All About Data: A Survey on the Effects of Data on Adversarial Robustness](https://mlsanity.com/paper/2303.09767/) (2023)
- [Formulating Robustness Against Unforeseen Attacks](https://mlsanity.com/paper/2204.13779/) (2022)
- [On the Computability of Robust PAC Learning](https://mlsanity.com/paper/2406.10161/) (2024)
- [PAC Learning with Improvements](https://mlsanity.com/paper/2503.03184/) (2025)
- [Probably Approximately Correct Federated Learning](https://mlsanity.com/paper/2304.04641/) (2023)
- [Strategic Classification with Non-Linear Classifiers](https://mlsanity.com/paper/2505.23443/) (2025)
- [Uniformly Stable Algorithms for Adversarial Training and Beyond](https://mlsanity.com/paper/2405.01817/) (2024)
- [When are Local Queries Useful for Robust Learning?](https://mlsanity.com/paper/2210.06089/) (2022)
- [mathscrH-Consistency Estimation Error of Surrogate Loss Minimizers](https://mlsanity.com/paper/2205.08017/) (2022)
- [On robust overfitting: adversarial training induced distribution matters](https://mlsanity.com/paper/2311.16526/) (2023)
- [Robust optimization for adversarial learning with finite sample complexity guarantees](https://mlsanity.com/paper/2403.15207/) (2024)

## Abstract (arXiv)

The existence of evasion attacks during the test phase of machine learning algorithms represents a significant challenge to both their deployment and understanding. These attacks can be carried out by adding imperceptible perturbations to inputs to generate adversarial examples and finding effective defenses and detectors has proven to be difficult. In this paper, we step away from the attack-defense arms race and seek to understand the limits of what can be learned in the presence of an evasion adversary. In particular, we extend the Probably Approximately Correct (PAC)-learning framework to account for the presence of an adversary. We first define corrupted hypothesis classes which arise from standard binary hypothesis classes in the presence of an evasion adversary and derive the Vapnik-Chervonenkis (VC)-dimension for these, denoted as the adversarial VC-dimension. We then show that sample complexity upper bounds from the Fundamental Theorem of Statistical learning can be extended to the case of evasion adversaries, where the sample complexity is controlled by the adversarial VC-dimension. We then explicitly derive the adversarial VC-dimension for halfspace classifiers in the presence of a sample-wise norm-constrained adversary of the type commonly studied for evasion attacks and show that it is the same as the standard VC-dimension, closing an open question. Finally, we prove that the adversarial VC-dimension can be either larger or smaller than the standard VC-dimension depending on the hypothesis class and adversary, making it an interesting object of study in its own right.