mlsanityData to 7 Oct 2026

Robust Empirical Risk Minimization with Tolerance

arXiv 2210.00635 ↗First posted 2 Oct 2022cs.LG stat.MLcited by 6

Not on the map. Why?

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.

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

Builds on

20 of 29 references.

References · 20

  1. 2013Intriguing properties of neural networkscited by 5,114
  2. 2016Towards Evaluating the Robustness of Neural Networkscited by 2,976
  3. 2015The Limitations of Deep Learning in Adversarial Settingscited by 784
  4. 2015Distillation as a Defense to Adversarial Perturbations against Deep Neural Networkscited by 675
  5. 2016Delving into Transferable Adversarial Examples and Black-box Attackscited by 530
  6. 2017Certifying Some Distributional Robustness with Principled Adversarial Trainingcited by 333
  7. 2018Certified Defenses against Adversarial Examplescited by 305
  8. 2017Formal Guarantees on the Robustness of a Classifier against Adversarial Manipulationcited by 182
  9. 2018Rademacher Complexity for Adversarially Robust Generalizationcited by 132
  10. 2019VC Classes are Adversarially Robustly Learnable, but Only Improperlycited by 83
  11. 2017Analyzing the Robustness of Nearest Neighbors to Adversarial Examplescited by 36
  12. 2017Towards Proving the Adversarial Robustness of Deep Neural Networkscited by 26
8 more
  1. 2021On the Existence of the Adversarial Bayes Classifier (Extended Version)cited by 25
  2. 2020When are Non-Parametric Methods Robust?cited by 15
  3. 2020The Complexity of Adversarially Robust Proper Learning of Halfspaces with Agnostic Noisecited by 15
  4. 2020Black-box Certification and Learning under Adversarial Perturbationscited by 13
  5. 2018Adversarial Risk Bounds via Function Transformationcited by 12
  6. 2021Transductive Robust Learning Guaranteescited by 10
  7. 2022Adversarially Robust Learning with Tolerancecited by 9
  8. 2021Consistent Non-Parametric Methods for Maximizing Robustnesscited by 7

Built on by

Cited by year (2026 to 7 Oct)

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

6 papers.

  1. 2024On the Computability of Robust PAC Learningcited by 6
  2. 2022On Proper Learnability between Average- and Worst-case Robustnesscited by 5
  3. 2024Engineering Trustworthy AI: A Developer Guide for Empirical Risk Minimizationcited by 3
  4. 2023Adversarial Attacks to Latent Representations of Distributed Neural Networks in Split Computingcited by 1
  5. 2026Bagging Robustly Learns VC Classes with Linear Sample Complexitycited by 1
  6. 2026Adversarially Robust PAC Learning with Optimal VC Ratescited by 0