mlsanityData to 7 Oct 2026

Adversarially Robust Learning with Tolerance

arXiv 2203.00849 ↗First posted 2 Mar 2022stat.ML cs.LGcited by 9

Not on the map. Why?

Abstract (arXiv)

We initiate the study of tolerant adversarial PAC-learning with respect to metric perturbation sets. In adversarial PAC-learning, an adversary is allowed to replace a test point x with an arbitrary point in a closed ball of radius r centered at x. In the tolerant version, the error of the learner is compared with the best achievable error with respect to a slightly larger perturbation radius (1+γ)r. This simple tweak helps us bridge the gap between theory and practice and obtain the first PAC-type guarantees for algorithmic techniques that are popular in practice. Our first result concerns the widely-used ``perturb-and-smooth'' approach for adversarial learning. For perturbation sets with doubling dimension d, we show that a variant of these approaches PAC-learns any hypothesis class H with VC-dimension v in the γ-tolerant adversarial setting with Oleft(fracv(1+1/γ)O(d)varepsilonright) samples. This is in contrast to the traditional (non-tolerant) setting in which, as we show, the perturb-and-smooth approach can provably fail. Our second result shows that one can PAC-learn the same class using widetildeOleft(fracd.vlog(1+1/γ)varepsilon2right) samples even in the agnostic setting. This result is based on a novel compression-based algorithm, and achieves a linear dependence on the doubling dimension as well as the VC-dimension. This is in contrast to the non-tolerant setting where there is no known sample complexity upper bound that depend polynomially on the VC-dimension.

Key facts. Cited by 9 papers in the map (data through 7 Oct 2026). Builds on 29 of its 54 references that are in the map. First posted on arXiv 2 Mar 2022.

Builds on

29 of 54 references.

References · 29

  1. 2013Intriguing properties of neural networkscited by 5,114
  2. 2019Certified Adversarial Robustness via Randomized Smoothingcited by 1,324
  3. 2019AugMix: A Simple Data Processing Method to Improve Robustness and Uncertaintycited by 897
  4. 2018Certified Robustness to Adversarial Examples with Differential Privacycited by 462
  5. 2019Provably Robust Deep Learning via Adversarially Trained Smoothed Classifierscited by 328
  6. 2018Spatially Transformed Adversarial Examplescited by 195
  7. 2018Certified Adversarial Robustness with Additive Noisecited by 178
  8. 2017Towards Robust Neural Networks via Random Self-ensemblecited by 158
  9. 2016Improving the Robustness of Deep Neural Networks via Stability Trainingcited by 156
  10. 2021A Universal Law of Robustness via Isoperimetrycited by 150
  11. 2020Randomized Smoothing of All Shapes and Sizescited by 146
  12. 2018Constructing Unrestricted Adversarial Examples with Generative Modelscited by 135
17 more
  1. 2018Semantic Adversarial Examplescited by 86
  2. 2019VC Classes are Adversarially Robustly Learnable, but Only Improperlycited by 83
  3. 2015The Optimal Sample Complexity of PAC Learningcited by 72
  4. 2019Robustness Certificates for Sparse Adversarial Attacks by Randomized Ablationcited by 59
  5. 2015Adversarial Manipulation of Deep Representationscited by 56
  6. 2017Mitigating Evasion Attacks to Deep Neural Networks via Region-based Classificationcited by 56
  7. 2015Sample compression schemes for VC classescited by 46
  8. 2017Geometric robustness of deep networks: analysis and improvementcited by 45
  9. 2020Beyond Perturbations: Learning Guarantees with Arbitrary Adversarial Test Examplescited by 44
  10. 2020Reducing Adversarially Robust Learning to Non-Robust PAC Learningcited by 28
  11. 2015Manitest: Are classifiers really invariant?cited by 27
  12. 2021Adversarially Robust Learning with Unknown Perturbation Setscited by 24
  13. 2020Efficiently Learning Adversarially Robust Halfspaces with Noisecited by 22
  14. 2019On Robustness to Adversarial Examples and Polynomial Optimizationcited by 14
  15. 2020Black-box Certification and Learning under Adversarial Perturbationscited by 13
  16. 2020Towards Feature Space Adversarial Attackcited by 11
  17. 2021Transductive Robust Learning Guaranteescited by 10

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 2; 2023: 1; 2024: 2; 2025: 2; 2026: 2.

9 papers.

  1. 2022Robust Empirical Risk Minimization with Tolerancecited by 6
  2. 2024On the Computability of Robust PAC Learningcited by 6
  3. 2025PAC Learning with Improvementscited by 6
  4. 2022On Proper Learnability between Average- and Worst-case Robustnesscited by 5
  5. 2025Beyond Worst-Case Online Classification: VC-Based Regret Bounds for Relaxed Benchmarkscited by 2
  6. 2023Adversarial Attacks to Latent Representations of Distributed Neural Networks in Split Computingcited by 1
  7. 2026Bagging Robustly Learns VC Classes with Linear Sample Complexitycited by 1
  8. 2024Robust optimization for adversarial learning with finite sample complexity guaranteescited by 0
  9. 2026Adversarially Robust PAC Learning with Optimal VC Ratescited by 0