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

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

## Key facts

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

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

- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [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)
- [Certified Adversarial Robustness via Randomized Smoothing](https://mlsanity.com/paper/1902.02918/) (2019)
- [Obfuscated Gradients Give a False Sense of Security: Circumventing Defenses to Adversarial Examples](https://mlsanity.com/paper/1802.00420/) (2018)
- [Robustness May Be at Odds with Accuracy](https://mlsanity.com/paper/1805.12152/) (2018)
- [Evasion Attacks against Machine Learning at Test Time](https://mlsanity.com/paper/1708.06131/) (2017)
- [Provable defenses against adversarial examples via the convex outer adversarial polytope](https://mlsanity.com/paper/1711.00851/) (2017)
- [Efficient Neural Network Robustness Certification with General Activation Functions](https://mlsanity.com/paper/1811.00866/) (2018)
- [Adversarially Robust Generalization Requires More Data](https://mlsanity.com/paper/1804.11285/) (2018)
- [Towards Fast Computation of Certified Robustness for ReLU Networks](https://mlsanity.com/paper/1804.09699/) (2018)
- [Semidefinite relaxations for certifying robustness to adversarial examples](https://mlsanity.com/paper/1811.01057/) (2018)
- [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)
- [Adversarial examples from computational constraints](https://mlsanity.com/paper/1805.10204/) (2018)
- [Lower Bounds on Adversarial Robustness from Optimal Transport](https://mlsanity.com/paper/1909.12272/) (2019)
- [Adversarial Learning Guarantees for Linear Hypotheses and Neural Networks](https://mlsanity.com/paper/2004.13617/) (2020)
- [Calibration and Consistency of Adversarial Surrogate Losses](https://mlsanity.com/paper/2104.09658/) (2021)
- [Adversarial Robustness May Be at Odds With Simplicity](https://mlsanity.com/paper/1901.00532/) (2019)
- [Adversarial Risk via Optimal Transport and Optimal Couplings](https://mlsanity.com/paper/1912.02794/) (2019)
- [Calibrated Surrogate Losses for Adversarially Robust Classification](https://mlsanity.com/paper/2005.13748/) (2020)
- [Adversarial Risk and Robustness: General Definitions and Implications for the Uniform Distribution](https://mlsanity.com/paper/1810.12272/) (2018)
- [Adversarial Examples in Multi-Layer Random ReLU Networks](https://mlsanity.com/paper/2106.12611/) (2021)
- [PAC-learning in the presence of evasion adversaries](https://mlsanity.com/paper/1806.01471/) (2018)
- [When are Non-Parametric Methods Robust?](https://mlsanity.com/paper/2003.06121/) (2020)
- [Robustness for Non-Parametric Classification: A Generic Attack and Defense](https://mlsanity.com/paper/1906.03310/) (2019)
- [Adversarial Examples from Cryptographic Pseudo-Random Generators](https://mlsanity.com/paper/1811.06418/) (2018)
- [Computational Limitations in Robust Classification and Win-Win Results](https://mlsanity.com/paper/1902.01086/) (2019)

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

- [Cross-Entropy Loss Functions: Theoretical Analysis and Applications](https://mlsanity.com/paper/2304.07288/) (2023)
- [Predictor-Rejector Multi-Class Abstention: Theoretical Analysis and Algorithms](https://mlsanity.com/paper/2310.14772/) (2023)
- [The Multimarginal Optimal Transport Formulation of Adversarial Multiclass Classification](https://mlsanity.com/paper/2204.12676/) (2022)
- [Existence and Minimax Theorems for Adversarial Surrogate Risks in Binary Classification](https://mlsanity.com/paper/2206.09098/) (2022)
- [A Characterization of Semi-Supervised Adversarially-Robust PAC Learnability](https://mlsanity.com/paper/2202.05420/) (2022)
- [Towards Consistency in Adversarial Classification](https://mlsanity.com/paper/2205.10022/) (2022)
- [Gamma-convergence of a nonlocal perimeter arising in adversarial machine learning](https://mlsanity.com/paper/2211.15223/) (2022)
- [On the existence of solutions to adversarial training in multiclass classification](https://mlsanity.com/paper/2305.00075/) (2023)
- [Adversarially Robust PAC Learnability of Real-Valued Functions](https://mlsanity.com/paper/2206.12977/) (2022)
- [Robust Empirical Risk Minimization with Tolerance](https://mlsanity.com/paper/2210.00635/) (2022)
- [The Adversarial Consistency of Surrogate Risks for Binary Classification](https://mlsanity.com/paper/2305.09956/) (2023)
- [On adversarial robustness and the use of Wasserstein ascent-descent dynamics to enforce it](https://mlsanity.com/paper/2301.03662/) (2023)
- [On the Role of Randomization in Adversarially Robust Classification](https://mlsanity.com/paper/2302.07221/) (2023)
- [The Consistency of Adversarial Training for Binary Classification](https://mlsanity.com/paper/2206.09099/) (2022)
- [It begins with a boundary: A geometric view on probabilistically robust learning](https://mlsanity.com/paper/2305.18779/) (2023)
- [A Notion of Uniqueness for the Adversarial Bayes Classifier](https://mlsanity.com/paper/2404.16956/) (2024)
- [Non-Asymptotic Bounds for Adversarial Excess Risk under Misspecified Models](https://mlsanity.com/paper/2309.00771/) (2023)
- [Adversarial Consistency and the Uniqueness of the Adversarial Bayes Classifier](https://mlsanity.com/paper/2404.17358/) (2024)
- [Consensus-based optimization for closed-box adversarial attacks and a connection to evolution strategies](https://mlsanity.com/paper/2506.24048/) (2025)
- [On Achieving Optimal Adversarial Test Error](https://mlsanity.com/paper/2306.07544/) (2023)
- [Uniform Convergence of Adversarially Robust Classifiers](https://mlsanity.com/paper/2406.14682/) (2024)
- [Adversarial Surrogate Risk Bounds for Binary Classification](https://mlsanity.com/paper/2506.09348/) (2025)
- [Lower Bounds on Adversarial Robustness for Multiclass Classification with General Loss Functions](https://mlsanity.com/paper/2510.01969/) (2025)
- [Duality for the Adversarial Total Variation](https://mlsanity.com/paper/2604.18540/) (2026)
- [Statistical Inference for Adversarial Training: Central Limit Theorems via Optimal Transport](https://mlsanity.com/paper/2609.22240/) (2026)

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