# Lower Bounds on Adversarial Robustness from Optimal Transport

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

## Key facts

- Cited by 53 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Sep 2019.

## Built on by (most cited first, 30 of 53)

- [Improving Robustness using Generated Data](https://mlsanity.com/paper/2110.09468/) (2021)
- [Robust Learning Meets Generative Models: Can Proxy Distributions Improve Adversarial Robustness?](https://mlsanity.com/paper/2104.09425/) (2021)
- [Probabilistically Robust Learning: Balancing Average- and Worst-case Performance](https://mlsanity.com/paper/2202.01136/) (2022)
- [The Many Faces of Adversarial Risk](https://mlsanity.com/paper/2201.08956/) (2022)
- [On the Existence of the Adversarial Bayes Classifier (Extended Version)](https://mlsanity.com/paper/2112.01694/) (2021)
- [Why Robust Generalization in Deep Learning is Difficult: Perspective of Expressive Power](https://mlsanity.com/paper/2205.13863/) (2022)
- [Mixed Nash Equilibria in the Adversarial Examples Game](https://mlsanity.com/paper/2102.06905/) (2021)
- [Overparameterized Linear Regression under Adversarial Attacks](https://mlsanity.com/paper/2204.06274/) (2022)
- [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)
- [Existence and Minimax Theorems for Adversarial Surrogate Risks in Binary Classification](https://mlsanity.com/paper/2206.09098/) (2022)
- [Towards Consistency in Adversarial Classification](https://mlsanity.com/paper/2205.10022/) (2022)
- [Adversarial Examples Might be Avoidable: The Role of Data Concentration in Adversarial Robustness](https://mlsanity.com/paper/2309.16096/) (2023)
- [Understanding Generalization in Adversarial Training via the Bias-Variance Decomposition](https://mlsanity.com/paper/2103.09947/) (2021)
- [Gamma-convergence of a nonlocal perimeter arising in adversarial machine learning](https://mlsanity.com/paper/2211.15223/) (2022)
- [A Law of Robustness beyond Isoperimetry](https://mlsanity.com/paper/2202.11592/) (2022)
- [Understanding the Impact of Adversarial Robustness on Accuracy Disparity](https://mlsanity.com/paper/2211.15762/) (2022)
- [It Is All About Data: A Survey on the Effects of Data on Adversarial Robustness](https://mlsanity.com/paper/2303.09767/) (2023)
- [On the existence of solutions to adversarial training in multiclass classification](https://mlsanity.com/paper/2305.00075/) (2023)
- [A High Dimensional Statistical Model for Adversarial Training: Geometry and Trade-Offs](https://mlsanity.com/paper/2402.05674/) (2024)
- [Characterizing the Optimal 0-1 Loss for Multi-class Classification with a Test-time Attacker](https://mlsanity.com/paper/2302.10722/) (2023)
- [Understanding and Diagnosing Deep Reinforcement Learning](https://mlsanity.com/paper/2406.16979/) (2024)
- [Robust Classification Under ℓ0 Attack for the Gaussian Mixture Model](https://mlsanity.com/paper/2104.02189/) (2021)
- [An Optimal Transport Approach for Computing Adversarial Training Lower Bounds in Multiclass Classification](https://mlsanity.com/paper/2401.09191/) (2024)
- [Improved Estimation of Concentration Under ℓp-Norm Distance Metrics Using Half Spaces](https://mlsanity.com/paper/2103.12913/) (2021)
- [Sample Complexity Bounds for Robustly Learning Decision Lists against Evasion Attacks](https://mlsanity.com/paper/2205.06127/) (2022)
- [On adversarial robustness and the use of Wasserstein ascent-descent dynamics to enforce it](https://mlsanity.com/paper/2301.03662/) (2023)
- [Robust Linear Regression: Gradient-descent, Early-stopping, and Beyond](https://mlsanity.com/paper/2301.13486/) (2023)
- [On the Geometry of Regularization in Adversarial Training: High-Dimensional Asymptotics and Generalization Bounds](https://mlsanity.com/paper/2410.16073/) (2024)
- [Understanding Intrinsic Robustness Using Label Uncertainty](https://mlsanity.com/paper/2107.03250/) (2021)

## Abstract (arXiv)

While progress has been made in understanding the robustness of machine learning classifiers to test-time adversaries (evasion attacks), fundamental questions remain unresolved. In this paper, we use optimal transport to characterize the minimum possible loss in an adversarial classification scenario. In this setting, an adversary receives a random labeled example from one of two classes, perturbs the example subject to a neighborhood constraint, and presents the modified example to the classifier. We define an appropriate cost function such that the minimum transportation cost between the distributions of the two classes determines the minimum 0-1 loss for any classifier. When the classifier comes from a restricted hypothesis class, the optimal transportation cost provides a lower bound. We apply our framework to the case of Gaussian data with norm-bounded adversaries and explicitly show matching bounds for the classification and transport problems as well as the optimality of linear classifiers. We also characterize the sample complexity of learning in this setting, deriving and extending previously known results as a special case. Finally, we use our framework to study the gap between the optimal classification performance possible and that currently achieved by state-of-the-art robustly trained neural networks for datasets of interest, namely, MNIST, Fashion MNIST and CIFAR-10.