# Existence and Minimax Theorems for Adversarial Surrogate Risks in Binary Classification

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 68 references that are in the map.
- First posted on arXiv 18 Jun 2022.

## Builds on (most cited first, 30 of 31)

- [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)
- [BadNets: Identifying Vulnerabilities in the Machine Learning Model Supply Chain](https://mlsanity.com/paper/1708.06733/) (2017)
- [Adversarial Machine Learning at Scale](https://mlsanity.com/paper/1611.01236/) (2016)
- [Fast is better than free: Revisiting adversarial training](https://mlsanity.com/paper/2001.03994/) (2020)
- [Evasion Attacks against Machine Learning at Test Time](https://mlsanity.com/paper/1708.06131/) (2017)
- [Adversarial Training for Free!](https://mlsanity.com/paper/1904.12843/) (2019)
- [Feature Denoising for Improving Adversarial Robustness](https://mlsanity.com/paper/1812.03411/) (2018)
- [Improving the Adversarial Robustness and Interpretability of Deep Neural Networks by Regularizing their Input Gradients](https://mlsanity.com/paper/1711.09404/) (2017)
- [Adversarial Logit Pairing](https://mlsanity.com/paper/1803.06373/) (2018)
- [Robustness via curvature regularization, and vice versa](https://mlsanity.com/paper/1811.09716/) (2018)
- [The Space of Transferable Adversarial Examples](https://mlsanity.com/paper/1704.03453/) (2017)
- [A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approach](https://mlsanity.com/paper/1901.08511/) (2019)
- [On the Convergence and Robustness of Adversarial Training](https://mlsanity.com/paper/2112.08304/) (2021)
- [Wasserstein Adversarial Examples via Projected Sinkhorn Iterations](https://mlsanity.com/paper/1902.07906/) (2019)
- [Improving DNN Robustness to Adversarial Attacks using Jacobian Regularization](https://mlsanity.com/paper/1803.08680/) (2018)
- [Lower Bounds on Adversarial Robustness from Optimal Transport](https://mlsanity.com/paper/1909.12272/) (2019)
- [Calibration and Consistency of Adversarial Surrogate Losses](https://mlsanity.com/paper/2104.09658/) (2021)
- [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)
- [The Many Faces of Adversarial Risk](https://mlsanity.com/paper/2201.08956/) (2022)
- [Stronger and Faster Wasserstein Adversarial Attacks](https://mlsanity.com/paper/2008.02883/) (2020)
- [On the Existence of the Adversarial Bayes Classifier (Extended Version)](https://mlsanity.com/paper/2112.01694/) (2021)
- [The Multimarginal Optimal Transport Formulation of Adversarial Multiclass Classification](https://mlsanity.com/paper/2204.12676/) (2022)
- [The Geometry of Adversarial Training in Binary Classification](https://mlsanity.com/paper/2111.13613/) (2021)
- [Adversarial Classification: Necessary conditions and geometric flows](https://mlsanity.com/paper/2011.10797/) (2020)
- [Robustness for Non-Parametric Classification: A Generic Attack and Defense](https://mlsanity.com/paper/1906.03310/) (2019)
- [Towards Consistency in Adversarial Classification](https://mlsanity.com/paper/2205.10022/) (2022)
- [Are Accuracy and Robustness Correlated?](https://mlsanity.com/paper/1610.04563/) (2016)

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

- [On the existence of solutions to adversarial training in multiclass classification](https://mlsanity.com/paper/2305.00075/) (2023)
- [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)
- [A minimax optimal control approach for robust neural ODEs](https://mlsanity.com/paper/2310.17584/) (2023)
- [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)
- [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)
- [Distributionally and Adversarially Robust Logistic Regression via Intersecting Wasserstein Balls](https://mlsanity.com/paper/2407.13625/) (2024)
- [Unveiling the Role of Randomization in Multiclass Adversarial Classification: Insights from Graph Theory](https://mlsanity.com/paper/2503.14299/) (2025)
- [Statistical Inference for Adversarial Training: Central Limit Theorems via Optimal Transport](https://mlsanity.com/paper/2609.22240/) (2026)

## Abstract (arXiv)

Adversarial training is one of the most popular methods for training methods robust to adversarial attacks, however, it is not well-understood from a theoretical perspective. We prove and existence, regularity, and minimax theorems for adversarial surrogate risks. Our results explain some empirical observations on adversarial robustness from prior work and suggest new directions in algorithm development. Furthermore, our results extend previously known existence and minimax theorems for the adversarial classification risk to surrogate risks.