The Many Faces of Adversarial Risk
  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.
