# Adversarially Robust Learning with Tolerance

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

## Key facts

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

## Builds on (most cited first, 29 of 29)

- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Certified Adversarial Robustness via Randomized Smoothing](https://mlsanity.com/paper/1902.02918/) (2019)
- [AugMix: A Simple Data Processing Method to Improve Robustness and Uncertainty](https://mlsanity.com/paper/1912.02781/) (2019)
- [Certified Robustness to Adversarial Examples with Differential Privacy](https://mlsanity.com/paper/1802.03471/) (2018)
- [Provably Robust Deep Learning via Adversarially Trained Smoothed Classifiers](https://mlsanity.com/paper/1906.04584/) (2019)
- [Spatially Transformed Adversarial Examples](https://mlsanity.com/paper/1801.02612/) (2018)
- [Certified Adversarial Robustness with Additive Noise](https://mlsanity.com/paper/1809.03113/) (2018)
- [Towards Robust Neural Networks via Random Self-ensemble](https://mlsanity.com/paper/1712.00673/) (2017)
- [Improving the Robustness of Deep Neural Networks via Stability Training](https://mlsanity.com/paper/1604.04326/) (2016)
- [A Universal Law of Robustness via Isoperimetry](https://mlsanity.com/paper/2105.12806/) (2021)
- [Randomized Smoothing of All Shapes and Sizes](https://mlsanity.com/paper/2002.08118/) (2020)
- [Constructing Unrestricted Adversarial Examples with Generative Models](https://mlsanity.com/paper/1805.07894/) (2018)
- [Semantic Adversarial Examples](https://mlsanity.com/paper/1804.00499/) (2018)
- [VC Classes are Adversarially Robustly Learnable, but Only Improperly](https://mlsanity.com/paper/1902.04217/) (2019)
- [The Optimal Sample Complexity of PAC Learning](https://mlsanity.com/paper/1507.00473/) (2015)
- [Robustness Certificates for Sparse Adversarial Attacks by Randomized Ablation](https://mlsanity.com/paper/1911.09272/) (2019)
- [Adversarial Manipulation of Deep Representations](https://mlsanity.com/paper/1511.05122/) (2015)
- [Mitigating Evasion Attacks to Deep Neural Networks via Region-based Classification](https://mlsanity.com/paper/1709.05583/) (2017)
- [Sample compression schemes for VC classes](https://mlsanity.com/paper/1503.06960/) (2015)
- [Geometric robustness of deep networks: analysis and improvement](https://mlsanity.com/paper/1711.09115/) (2017)
- [Beyond Perturbations: Learning Guarantees with Arbitrary Adversarial Test Examples](https://mlsanity.com/paper/2007.05145/) (2020)
- [Reducing Adversarially Robust Learning to Non-Robust PAC Learning](https://mlsanity.com/paper/2010.12039/) (2020)
- [Manitest: Are classifiers really invariant?](https://mlsanity.com/paper/1507.06535/) (2015)
- [Adversarially Robust Learning with Unknown Perturbation Sets](https://mlsanity.com/paper/2102.02145/) (2021)
- [Efficiently Learning Adversarially Robust Halfspaces with Noise](https://mlsanity.com/paper/2005.07652/) (2020)
- [On Robustness to Adversarial Examples and Polynomial Optimization](https://mlsanity.com/paper/1911.04681/) (2019)
- [Black-box Certification and Learning under Adversarial Perturbations](https://mlsanity.com/paper/2006.16520/) (2020)
- [Towards Feature Space Adversarial Attack](https://mlsanity.com/paper/2004.12385/) (2020)
- [Transductive Robust Learning Guarantees](https://mlsanity.com/paper/2110.10602/) (2021)

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

- [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)
- [PAC Learning with Improvements](https://mlsanity.com/paper/2503.03184/) (2025)
- [On Proper Learnability between Average- and Worst-case Robustness](https://mlsanity.com/paper/2211.05656/) (2022)
- [Adversarial Attacks to Latent Representations of Distributed Neural Networks in Split Computing](https://mlsanity.com/paper/2309.17401/) (2023)
- [Beyond Worst-Case Online Classification: VC-Based Regret Bounds for Relaxed Benchmarks](https://mlsanity.com/paper/2504.10598/) (2025)
- [Bagging Robustly Learns VC Classes with Linear Sample Complexity](https://mlsanity.com/paper/2608.13514/) (2026)
- [Robust optimization for adversarial learning with finite sample complexity guarantees](https://mlsanity.com/paper/2403.15207/) (2024)
- [Adversarially Robust PAC Learning with Optimal VC Rates](https://mlsanity.com/paper/2609.24260/) (2026)

## 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.