# Adversarially Robust PAC Learning with Optimal VC Rates

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 59 of its 79 references that are in the map.
- First posted on arXiv 21 Sep 2026.

## Builds on (most cited first, 30 of 59)

- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Universal and Transferable Adversarial Attacks on Aligned Language Models](https://mlsanity.com/paper/2307.15043/) (2023)
- [Towards Evaluating the Robustness of Neural Networks](https://mlsanity.com/paper/1608.04644/) (2016)
- [Jailbroken: How Does LLM Safety Training Fail?](https://mlsanity.com/paper/2307.02483/) (2023)
- [Not what you've signed up for: Compromising Real-World LLM-Integrated Applications with Indirect Prompt Injection](https://mlsanity.com/paper/2302.12173/) (2023)
- [Certified Adversarial Robustness via Randomized Smoothing](https://mlsanity.com/paper/1902.02918/) (2019)
- [Obfuscated Gradients Give a False Sense of Security: Circumventing Defenses to Adversarial Examples](https://mlsanity.com/paper/1802.00420/) (2018)
- [Robustness May Be at Odds with Accuracy](https://mlsanity.com/paper/1805.12152/) (2018)
- [Ignore Previous Prompt: Attack Techniques For Language Models](https://mlsanity.com/paper/2211.09527/) (2022)
- [On Adaptive Attacks to Adversarial Example Defenses](https://mlsanity.com/paper/2002.08347/) (2020)
- [Overfitting in adversarially robust deep learning](https://mlsanity.com/paper/2002.11569/) (2020)
- [On Evaluating Adversarial Robustness](https://mlsanity.com/paper/1902.06705/) (2019)
- [Adversarially Robust Generalization Requires More Data](https://mlsanity.com/paper/1804.11285/) (2018)
- [Do Adversarially Robust ImageNet Models Transfer Better?](https://mlsanity.com/paper/2007.08489/) (2020)
- [Uncovering the Limits of Adversarial Training against Norm-Bounded Adversarial Examples](https://mlsanity.com/paper/2010.03593/) (2020)
- [Audio Adversarial Examples: Targeted Attacks on Speech-to-Text](https://mlsanity.com/paper/1801.01944/) (2018)
- [Tactics of Adversarial Attack on Deep Reinforcement Learning Agents](https://mlsanity.com/paper/1703.06748/) (2017)
- [A Universal Law of Robustness via Isoperimetry](https://mlsanity.com/paper/2105.12806/) (2021)
- [Smooth Adversarial Training](https://mlsanity.com/paper/2006.14536/) (2020)
- [VC Classes are Adversarially Robustly Learnable, but Only Improperly](https://mlsanity.com/paper/1902.04217/) (2019)
- [Interpreting Adversarially Trained Convolutional Neural Networks](https://mlsanity.com/paper/1905.09797/) (2019)
- [The Optimal Sample Complexity of PAC Learning](https://mlsanity.com/paper/1507.00473/) (2015)
- [Defensive Distillation is Not Robust to Adversarial Examples](https://mlsanity.com/paper/1607.04311/) (2016)
- [A law of robustness for two-layers neural networks](https://mlsanity.com/paper/2009.14444/) (2020)
- [Proper Learning, Helly Number, and an Optimal SVM Bound](https://mlsanity.com/paper/2005.11818/) (2020)
- [Sample compression schemes for VC classes](https://mlsanity.com/paper/1503.06960/) (2015)
- [MagNet and "Efficient Defenses Against Adversarial Attacks" are Not Robust to Adversarial Examples](https://mlsanity.com/paper/1711.08478/) (2017)
- [Are Perceptually-Aligned Gradients a General Property of Robust Classifiers?](https://mlsanity.com/paper/1910.08640/) (2019)

## Abstract (arXiv)

We study the problem of adversarially robust PAC learning. In this framework, the learner observes independent samples from an unknown distribution over X × 0,1, as in classical PAC learning. However, given a perturbation map U : X → 2X known to the learner, the goal is to output, with high probability, a predictor that correctly classifies every perturbation z ∈ U(x) of most future examples (x,y) drawn from the same underlying distribution. We determine the optimal U-independent sample complexity of this problem in both the realizable and agnostic settings. More specifically, for every concept class H of operatornameVC dimension d, we prove upper bounds of O big( d/ε + log(1/δ)/ε big) in the realizable setting and O big( d/ε2 + log(1/δ)/ε2 big) in the agnostic setting, together with an optimal first-order refinement of the latter. These bounds match the corresponding lower bounds for classical PAC learning. Consequently, and perhaps surprisingly, adversarial robustness incurs no additional distribution-free statistical cost, uniformly over all perturbation maps. Our bounds improve exponentially on those of [Montasser, Hanneke, and Srebro; COLT '19]. On the technical side, we present short and elementary proofs based on a new algorithmic principle that we call binomial-bagging. We believe that binomial-bagging and its analysis may be of independent interest.