The Many Faces of Adversarial Risk
This work addresses foundational issues in adversarial machine learning for researchers, providing theoretical clarity and new mathematical tools, though it is incremental in building on existing connections.
The paper tackles the problem of inconsistent definitions of adversarial risk in machine learning by making them rigorous and examining their similarities and differences, resulting in generalizations of Strassen's theorem, equivalence proofs between adversarial robustness and robust hypothesis testing, and new connections to game theory and Choquet capacities.
Adversarial risk quantifies the performance of classifiers on adversarially perturbed data. Numerous definitions of adversarial risk -- not all mathematically rigorous and differing subtly in the details -- have appeared in the literature. In this paper, we revisit these definitions, make them rigorous, and critically examine their similarities and differences. Our technical tools derive from optimal transport, robust statistics, functional analysis, and game theory. Our contributions include the following: generalizing Strassen's theorem to the unbalanced optimal transport setting with applications to adversarial classification with unequal priors; showing an equivalence between adversarial robustness and robust hypothesis testing with $\infty$-Wasserstein uncertainty sets; proving the existence of a pure Nash equilibrium in the two-player game between the adversary and the algorithm; and characterizing adversarial risk by the minimum Bayes error between a pair of distributions belonging to the $\infty$-Wasserstein uncertainty sets. Our results generalize and deepen recently discovered connections between optimal transport and adversarial robustness and reveal new connections to Choquet capacities and game theory.