mlsanityData to 7 Oct 2026

Adversarially Robust PAC Learning with Optimal VC Rates

arXiv 2609.24260 ↗First posted 21 Sep 2026stat.ML cs.LG math.STcited by 0

Not on the map. Why?

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.

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

Builds on

59 of 79 references.

References · 59

  1. 2014Explaining and Harnessing Adversarial Examplescited by 7,287
  2. 2017Towards Deep Learning Models Resistant to Adversarial Attackscited by 6,326
  3. 2013Intriguing properties of neural networkscited by 5,114
  4. 2016Towards Evaluating the Robustness of Neural Networkscited by 2,976
  5. 2023Universal and Transferable Adversarial Attacks on Aligned Language Modelscited by 2,914
  6. 2023Jailbroken: How Does LLM Safety Training Fail?cited by 1,565
  7. 2023Not what you've signed up for: Compromising Real-World LLM-Integrated Applications with Indirect Prompt Injectioncited by 1,339
  8. 2019Certified Adversarial Robustness via Randomized Smoothingcited by 1,324
  9. 2018Obfuscated Gradients Give a False Sense of Security: Circumventing Defenses to Adversarial Examplescited by 1,259
  10. 2018Robustness May Be at Odds with Accuracycited by 873
  11. 2022Ignore Previous Prompt: Attack Techniques For Language Modelscited by 760
  12. 2020On Adaptive Attacks to Adversarial Example Defensescited by 547
38 more
  1. 2020Overfitting in adversarially robust deep learningcited by 504
  2. 2019On Evaluating Adversarial Robustnesscited by 442
  3. 2018Adversarially Robust Generalization Requires More Datacited by 318
  4. 2020Do Adversarially Robust ImageNet Models Transfer Better?cited by 315
  5. 2020Uncovering the Limits of Adversarial Training against Norm-Bounded Adversarial Examplescited by 275
  6. 2018Audio Adversarial Examples: Targeted Attacks on Speech-to-Textcited by 268
  7. 2017Tactics of Adversarial Attack on Deep Reinforcement Learning Agentscited by 163
  8. 2021A Universal Law of Robustness via Isoperimetrycited by 150
  9. 2020Smooth Adversarial Trainingcited by 89
  10. 2019VC Classes are Adversarially Robustly Learnable, but Only Improperlycited by 83
  11. 2019Interpreting Adversarially Trained Convolutional Neural Networkscited by 75
  12. 2015The Optimal Sample Complexity of PAC Learningcited by 72
  13. 2016Defensive Distillation is Not Robust to Adversarial Examplescited by 60
  14. 2020A law of robustness for two-layers neural networkscited by 54
  15. 2020Proper Learning, Helly Number, and an Optimal SVM Boundcited by 52
  16. 2015Sample compression schemes for VC classescited by 46
  17. 2017MagNet and "Efficient Defenses Against Adversarial Attacks" are Not Robust to Adversarial Examplescited by 46
  18. 2019Are Perceptually-Aligned Gradients a General Property of Robust Classifiers?cited by 42
  19. 2018On the Robustness of the CVPR 2018 White-Box Adversarial Example Defensescited by 40
  20. 2022Bagging is an Optimal PAC Learnercited by 34
  21. 2023Optimal PAC Bounds Without Uniform Convergencecited by 33
  22. 2019Universal Bayes consistency in metric spacescited by 32
  23. 2020Reducing Adversarially Robust Learning to Non-Robust PAC Learningcited by 28
  24. 2020ARAE: Adversarially Robust Training of Autoencoders Improves Novelty Detectioncited by 27
  25. 2021Realizable Learning is All You Needcited by 25
  26. 2021Adversarially Robust Learning with Unknown Perturbation Setscited by 24
  27. 2022Adversarially Robust Learning: A Generic Minimax Optimal Learner and Characterizationcited by 17
  28. 2018Sequential Attacks on Agents for Long-Term Adversarial Goalscited by 16
  29. 2022A Characterization of Semi-Supervised Adversarially-Robust PAC Learnabilitycited by 13
  30. 2024Revisiting Agnostic PAC Learningcited by 11
  31. 2021Transductive Robust Learning Guaranteescited by 10
  32. 2022Adversarially Robust Learning with Tolerancecited by 9
  33. 2022Adversarially Robust PAC Learnability of Real-Valued Functionscited by 8
  34. 2019Is AmI (Attacks Meet Interpretability) Robust to Adversarial Examples?cited by 7
  35. 2023The Impossibility of Parallelizing Boostingcited by 7
  36. 2021Primal and Dual Combinatorial Dimensionscited by 6
  37. 2022Robust Empirical Risk Minimization with Tolerancecited by 6
  38. 2024Theoretical Limitations of Ensembles in the Age of Overparameterizationcited by 6

50 most cited of 59 All 59 (JSON)

Built on by

Not cited yet.