mlsanityData to 7 Oct 2026

On the Existence of the Adversarial Bayes Classifier (Extended Version)

arXiv 2112.01694 ↗First posted 3 Dec 2021cs.LG stat.MLcited by 25

Not on the map. Why?

Abstract (arXiv)

Adversarial robustness is a critical property in a variety of modern machine learning applications. While it has been the subject of several recent theoretical studies, many important questions related to adversarial robustness are still open. In this work, we study a fundamental question regarding Bayes optimality for adversarial robustness. We provide general sufficient conditions under which the existence of a Bayes optimal classifier can be guaranteed for adversarial robustness. Our results can provide a useful tool for a subsequent study of surrogate losses in adversarial robustness and their consistency properties. This manuscript is the extended and corrected version of the paper On the Existence of the Adversarial Bayes Classifier published in NeurIPS 2021. There were two errors in theorem statements in the original paper -- one in the definition of pseudo-certifiable robustness and the other in the measurability of A^e for arbitrary metric spaces. In this version we correct the errors. Furthermore, the results of the original paper did not apply to some non-strictly convex norms and here we extend our results to all possible norms.

Key facts. Cited by 25 papers in the map (data through 7 Oct 2026). Builds on 29 of its 62 references that are in the map. First posted on arXiv 3 Dec 2021.

Builds on

29 of 62 references.

References · 29

  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. 2019Certified Adversarial Robustness via Randomized Smoothingcited by 1,324
  6. 2018Obfuscated Gradients Give a False Sense of Security: Circumventing Defenses to Adversarial Examplescited by 1,259
  7. 2018Robustness May Be at Odds with Accuracycited by 873
  8. 2017Evasion Attacks against Machine Learning at Test Timecited by 686
  9. 2017Provable defenses against adversarial examples via the convex outer adversarial polytopecited by 564
  10. 2018Efficient Neural Network Robustness Certification with General Activation Functionscited by 439
  11. 2018Adversarially Robust Generalization Requires More Datacited by 318
  12. 2018Towards Fast Computation of Certified Robustness for ReLU Networkscited by 254
17 more
  1. 2018Semidefinite relaxations for certifying robustness to adversarial examplescited by 178
  2. 2018Rademacher Complexity for Adversarially Robust Generalizationcited by 132
  3. 2019VC Classes are Adversarially Robustly Learnable, but Only Improperlycited by 83
  4. 2018Adversarial examples from computational constraintscited by 79
  5. 2019Lower Bounds on Adversarial Robustness from Optimal Transportcited by 52
  6. 2020Adversarial Learning Guarantees for Linear Hypotheses and Neural Networkscited by 47
  7. 2021Calibration and Consistency of Adversarial Surrogate Lossescited by 47
  8. 2019Adversarial Robustness May Be at Odds With Simplicitycited by 39
  9. 2019Adversarial Risk via Optimal Transport and Optimal Couplingscited by 36
  10. 2020Calibrated Surrogate Losses for Adversarially Robust Classificationcited by 36
  11. 2018Adversarial Risk and Robustness: General Definitions and Implications for the Uniform Distributioncited by 32
  12. 2021Adversarial Examples in Multi-Layer Random ReLU Networkscited by 26
  13. 2018PAC-learning in the presence of evasion adversariescited by 23
  14. 2020When are Non-Parametric Methods Robust?cited by 15
  15. 2019Robustness for Non-Parametric Classification: A Generic Attack and Defensecited by 12
  16. 2018Adversarial Examples from Cryptographic Pseudo-Random Generatorscited by 10
  17. 2019Computational Limitations in Robust Classification and Win-Win Resultscited by 10

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 8; 2023: 9; 2024: 3; 2025: 3; 2026: 2.

25 papers.

Sort:

  1. 2023Cross-Entropy Loss Functions: Theoretical Analysis and Applicationscited by 206
  2. 2023Predictor-Rejector Multi-Class Abstention: Theoretical Analysis and Algorithmscited by 36
  3. 2022The Multimarginal Optimal Transport Formulation of Adversarial Multiclass Classificationcited by 21
  4. 2022Existence and Minimax Theorems for Adversarial Surrogate Risks in Binary Classificationcited by 15
  5. 2022A Characterization of Semi-Supervised Adversarially-Robust PAC Learnabilitycited by 13
  6. 2022Towards Consistency in Adversarial Classificationcited by 12
  7. 2022Gamma-convergence of a nonlocal perimeter arising in adversarial machine learningcited by 10
  8. 2023On the existence of solutions to adversarial training in multiclass classificationcited by 9
  9. 2022Adversarially Robust PAC Learnability of Real-Valued Functionscited by 8
  10. 2022Robust Empirical Risk Minimization with Tolerancecited by 6
  11. 2023The Adversarial Consistency of Surrogate Risks for Binary Classificationcited by 6
  12. 2023On adversarial robustness and the use of Wasserstein ascent-descent dynamics to enforce itcited by 4
13 more
  1. 2023On the Role of Randomization in Adversarially Robust Classificationcited by 4
  2. 2022The Consistency of Adversarial Training for Binary Classificationcited by 3
  3. 2023It begins with a boundary: A geometric view on probabilistically robust learningcited by 3
  4. 2024A Notion of Uniqueness for the Adversarial Bayes Classifiercited by 3
  5. 2023Non-Asymptotic Bounds for Adversarial Excess Risk under Misspecified Modelscited by 2
  6. 2024Adversarial Consistency and the Uniqueness of the Adversarial Bayes Classifiercited by 2
  7. 2023On Achieving Optimal Adversarial Test Errorcited by 1
  8. 2024Uniform Convergence of Adversarially Robust Classifierscited by 1
  9. 2025Adversarial Surrogate Risk Bounds for Binary Classificationcited by 1
  10. 2025Consensus-based optimization for closed-box adversarial attacks and a connection to evolution strategiescited by 1
  11. 2025Lower Bounds on Adversarial Robustness for Multiclass Classification with General Loss Functionscited by 1
  12. 2026Duality for the Adversarial Total Variationcited by 0
  13. 2026Statistical Inference for Adversarial Training: Central Limit Theorems via Optimal Transportcited by 0