  Modern machine learning algorithms perform poorly on adversarially
manipulated data. Adversarial risk quantifies the error of classifiers in
adversarial settings; adversarial classifiers minimize adversarial risk. In
this paper, we analyze adversarial risk and adversarial classifiers from an
optimal transport perspective. We show that the optimal adversarial risk for
binary classification with 0-1 loss is determined by an optimal transport cost
between the probability distributions of the two classes. We develop optimal
transport plans (probabilistic couplings) for univariate distributions such as
the normal, the uniform, and the triangular distribution. We also derive
optimal adversarial classifiers in these settings. Our analysis leads to
algorithm-independent fundamental limits on adversarial risk, which we
calculate for several real-world datasets. We extend our results to general
loss functions under convexity and smoothness assumptions.
