# Robust Empirical Risk Minimization with Tolerance

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

## Key facts

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

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

- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Towards Evaluating the Robustness of Neural Networks](https://mlsanity.com/paper/1608.04644/) (2016)
- [The Limitations of Deep Learning in Adversarial Settings](https://mlsanity.com/paper/1511.07528/) (2015)
- [Distillation as a Defense to Adversarial Perturbations against Deep Neural Networks](https://mlsanity.com/paper/1511.04508/) (2015)
- [Delving into Transferable Adversarial Examples and Black-box Attacks](https://mlsanity.com/paper/1611.02770/) (2016)
- [Certifying Some Distributional Robustness with Principled Adversarial Training](https://mlsanity.com/paper/1710.10571/) (2017)
- [Certified Defenses against Adversarial Examples](https://mlsanity.com/paper/1801.09344/) (2018)
- [Formal Guarantees on the Robustness of a Classifier against Adversarial Manipulation](https://mlsanity.com/paper/1705.08475/) (2017)
- [Rademacher Complexity for Adversarially Robust Generalization](https://mlsanity.com/paper/1810.11914/) (2018)
- [VC Classes are Adversarially Robustly Learnable, but Only Improperly](https://mlsanity.com/paper/1902.04217/) (2019)
- [Analyzing the Robustness of Nearest Neighbors to Adversarial Examples](https://mlsanity.com/paper/1706.03922/) (2017)
- [Towards Proving the Adversarial Robustness of Deep Neural Networks](https://mlsanity.com/paper/1709.02802/) (2017)
- [On the Existence of the Adversarial Bayes Classifier (Extended Version)](https://mlsanity.com/paper/2112.01694/) (2021)
- [When are Non-Parametric Methods Robust?](https://mlsanity.com/paper/2003.06121/) (2020)
- [The Complexity of Adversarially Robust Proper Learning of Halfspaces with Agnostic Noise](https://mlsanity.com/paper/2007.15220/) (2020)
- [Black-box Certification and Learning under Adversarial Perturbations](https://mlsanity.com/paper/2006.16520/) (2020)
- [Adversarial Risk Bounds via Function Transformation](https://mlsanity.com/paper/1810.09519/) (2018)
- [Transductive Robust Learning Guarantees](https://mlsanity.com/paper/2110.10602/) (2021)
- [Adversarially Robust Learning with Tolerance](https://mlsanity.com/paper/2203.00849/) (2022)
- [Consistent Non-Parametric Methods for Maximizing Robustness](https://mlsanity.com/paper/2102.09086/) (2021)

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

- [On the Computability of Robust PAC Learning](https://mlsanity.com/paper/2406.10161/) (2024)
- [On Proper Learnability between Average- and Worst-case Robustness](https://mlsanity.com/paper/2211.05656/) (2022)
- [Engineering Trustworthy AI: A Developer Guide for Empirical Risk Minimization](https://mlsanity.com/paper/2410.19361/) (2024)
- [Adversarial Attacks to Latent Representations of Distributed Neural Networks in Split Computing](https://mlsanity.com/paper/2309.17401/) (2023)
- [Bagging Robustly Learns VC Classes with Linear Sample Complexity](https://mlsanity.com/paper/2608.13514/) (2026)
- [Adversarially Robust PAC Learning with Optimal VC Rates](https://mlsanity.com/paper/2609.24260/) (2026)

## Abstract (arXiv)

Developing simple, sample-efficient learning algorithms for robust classification is a pressing issue in today's tech-dominated world, and current theoretical techniques requiring exponential sample complexity and complicated improper learning rules fall far from answering the need. In this work we study the fundamental paradigm of (robust) textitempirical risk minimization (RERM), a simple process in which the learner outputs any hypothesis minimizing its training error. RERM famously fails to robustly learn VC classes (Montasser et al., 2019a), a bound we show extends even to `nice' settings such as (bounded) halfspaces. As such, we study a recent relaxation of the robust model called textittolerant robust learning (Ashtiani et al., 2022) where the output classifier is compared to the best achievable error over slightly larger perturbation sets. We show that under geometric niceness conditions, a natural tolerant variant of RERM is indeed sufficient for γ-tolerant robust learning VC classes over ℝd, and requires only tildeOleft( fracVC(H)dlog fracDγδε2right) samples for robustness regions of (maximum) diameter D.