Lower Bounds on Adversarial Robustness from Optimal Transport
This work addresses a foundational problem in AI security by providing theoretical lower bounds on adversarial robustness, which is crucial for researchers and practitioners developing robust models, though it is incremental in extending known results through a new framework.
The paper tackles the problem of understanding the fundamental limits of adversarial robustness in machine learning classifiers by using optimal transport to characterize the minimum possible loss in adversarial classification scenarios, deriving explicit bounds for Gaussian data and analyzing the gap between optimal and current performance on datasets like MNIST, Fashion MNIST, and CIFAR-10.
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.