Adversarial Risk via Optimal Transport and Optimal Couplings

Muni Sreenivas Pydi, Varun S. Jog

Abstract

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.

Introduction

Deep learning models are notoriously brittle. Tiny, imperceptible perturbations—known as adversarial examples—can trick state-of-the-art models into making confident, incorrect predictions. While the machine learning community has proposed a vast array of specific attacks and defenses, most of these are "algorithm-dependent," meaning they are tied to specific model architectures or training procedures.

This research takes a step back to address two fundamental, model-agnostic questions:

  1. What is the "fundamental speed limit" of adversarial robustness for a given dataset?
  2. What does an "optimally robust" classifier actually look like?

By reframing adversarial attacks through the lens of Optimal Transport (OT), this paper establishes that the fundamental limit of adversarial robustness is directly determined by the OT cost between the probability distributions of different classes.

The Optimal Transport Connection

The researchers bridge the gap between adversarial machine learning and OT theory by demonstrating that for binary classification with 0-1 loss, the optimal adversarial risk is determined by a specific transport cost, $D_\epsilon$, between two class distributions.

In this framework, an adversary is viewed as an agent attempting to "transport" mass from the distribution of Class A into the territory of Class B as efficiently as possible. By leveraging Strassen’s Theorem, the authors prove that the difficulty of classification under attack is equivalent to the difficulty of separating two probability measures that have been "spread out" by the adversary's budget ($\epsilon$). This equivalence means that an adversary who perturbs individual data points is mathematically identical to an adversary who perturbs the entire underlying data distribution in the $\infty$-Wasserstein sense.

Fundamental Limits and the "Breaking Point"

A key contribution of this work is the derivation of a clean expression for optimal robust risk:

$$R^*_\epsilon = \frac{1}{2}[1 - D_\epsilon(p_0, p_1)]$$

This formula links risk directly to the $D_\epsilon$ transport cost, providing an absolute floor for error that is independent of whether one uses a Neural Network, a Support Vector Machine, or a Decision Tree.

One of the most significant insights is the existence of a "Breaking Point." There is a clear threshold for the adversary's budget: if the $\infty$-Wasserstein distance between two classes is less than twice the adversary's budget ($2\epsilon$), the optimal adversarial risk becomes 0.5. At this point, the distributions have been sufficiently "mixed" by the adversary that no algorithm can perform better than a random guess.

Optimal Couplings and Classifier Behavior

For specific univariate distributions—including Gaussian, Uniform, and Triangular—the authors explicitly construct "optimal couplings." These are mathematical maps that show exactly how an adversary would move data to maximize confusion.

Their analysis reveals that optimal classifiers can change abruptly. For example, when observing two Gaussian distributions, as the adversary's budget $\epsilon$ increases, the optimal decision boundary remains a stable halfspace until it reaches a critical point. At this threshold, the boundary suddenly collapses, and the optimal strategy becomes a "constant classifier" that predicts the same label for every input.

Empirical Results on Real-World Datasets

To test these theoretical bounds, the authors evaluated four standard computer vision benchmarks: MNIST, CIFAR-10, Fashion-MNIST, and SVHN. To make the bounds non-trivial (as raw empirical data points are often perfectly separable), they calculated bounds for Gaussian Mixture Models based on these datasets, simulating the effects of data augmentation.

The results highlight the "impossibility" of perfect accuracy in certain regimes. For instance, on CIFAR-10 with an $\ell_2$ perturbation of $\epsilon = 3$, the research shows that the adversarial error rate cannot be lower than 0.25 when trained with standard Gaussian data augmentation.

Extensions and Future Work

While the most elegant results apply to binary classification with 0-1 loss, the paper extends the theory to continuous loss functions (such as those used in regression) using convexity and Lipschitz smoothness assumptions. However, the authors note that these bounds for general loss functions are not yet as tight as the 0-1 case.

Future research directions include:

  • Multi-class Settings: Extending the binary results to multi-class classification, which may require "multi-marginal" optimal transport theory.
  • Tightening Bounds: Developing stronger assumptions on loss function curvature to improve the tightness of continuous loss bounds.
  • OT-Regularized Training: Investigating whether these insights can lead to new training objectives that explicitly minimize the $D_\epsilon$ cost to reach these fundamental limits.

Summary updated

Abstract

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.
BibTeX
@inproceedings{pydi2020adversarial,
  author = {Muni Sreenivas Pydi and Varun S. Jog},
  title = {{Adversarial Risk via Optimal Transport and Optimal Couplings}},
  booktitle = {International Conference on Machine Learning},
  year = {2020},
  url = {https://openreview.net/forum?id=PDVuD9TrPUn},
}
Figure