TL;DR
This paper provides a rigorous mathematical foundation for "adversarial risk," proving that several popular but seemingly different definitions—based on set expansions, transport maps, and distribution shifts—are actually equivalent. By leveraging optimal transport and game theory, the authors generalize key results to cases with unequal class priors and prove the existence of stable Nash equilibria in the "cat-and-mouse" game between adversaries and classifiers.
The Definitions Problem in Adversarial Risk
In the world of machine learning, "adversarial risk" is the standard metric for how well a model stands up to malicious perturbations. However, the field has historically suffered from a "definitions problem." Depending on the literature, adversarial risk might be defined using:
- Set Expansions: How much the decision boundary "stretches" to include perturbed points.
- Transport Maps: Explicitly moving data points to maximize loss.
- Distributional Robustness: Shifting the entire data distribution within a certain "uncertainty set" (often defined by Wasserstein distance).
Because these definitions were not always mathematically reconciled, theoretical proofs were sometimes shaky or limited to specific cases (like binary classes with equal 50/50 priors). Furthermore, some definitions faced "measurability" issues—mathematical edge cases where the risk might not even be well-defined in certain abstract spaces. This paper aims to clean up the mess and provide a unified, rigorous framework.
Methodological Toolkit
To bridge these theoretical gaps, the authors employ a heavy-duty mathematical toolkit:
- Optimal Transport: They use the $\infty$-Wasserstein metric to describe how an adversary moves probability mass.
- Generalized Strassen’s Theorem: They extend a classical result from probability theory to "unbalanced" settings, allowing them to analyze scenarios where one class is much more common than the other.
- Choquet Capacities: A tool from functional analysis used to handle the measurability of set expansions in Euclidean space ($\mathbb{R}^d$).
- Game Theory: They model the interaction between the classifier and the adversary as a two-player zero-sum game to find "Nash equilibria"—points where neither side can unilaterally improve their position.
Key Insights and Ideas
- The Equivalence "Aha!": The authors prove that for a wide class of problems, defining risk by moving individual points (transport maps) is exactly the same as defining it by shifting the entire distribution ($\infty$-Wasserstein robustness). This unifies the "local" and "global" views of adversarial attacks.
- Measurability Matters: They point out a subtle flaw in previous literature: the "Minkowski expansion" of a Borel set isn't always a Borel set. They solve this by showing that using the "universal completion" of the Borel $\sigma$-algebra (or Lebesgue measure in $\mathbb{R}^d$) makes the math bulletproof.
- Unequal Priors: Most previous theory assumed classes were equally likely. By generalizing Strassen's theorem, the authors show that optimal adversarial risk is characterized by an "unbalanced" optimal transport cost, providing a formula for the best possible robust error rate regardless of class balance.
- Pure Nash Equilibria: They prove that in many common spaces, there exists a "pure" Nash equilibrium. This means there is a specific, non-randomized strategy for both the adversary and the defender that represents a stable state of the game.
Key Results
- Unification Table: The paper provides a clear mapping showing exactly when different risk formulations ($R_\oplus, R_\epsilon, R_{F_\epsilon}, R_{\Gamma_\epsilon}$) are mathematically equal under specific conditions.
- Optimal Risk Formula: They derive a closed-form expression for the minimum possible adversarial risk based on the transport cost between class distributions.
- Minimax Theorem: They establish that the "order of play" doesn't matter for the value of the game (zero duality gap). Whether the defender picks a classifier first or the adversary picks a perturbation first, the resulting risk is the same under optimal play.
Limitations and Future Work
While theoretically comprehensive, the paper notes several boundaries to its current scope:
- Binary and 0-1 Loss: The current work is primarily focused on binary classification (two classes) and the 0-1 loss function (correct vs. incorrect). Real-world deep learning often involves multi-class problems and continuous loss functions (like cross-entropy).
- Specific Perturbations: The results are tailored to $\infty$-Wasserstein perturbations (where every point is moved by at most $\epsilon$). Extending this to other types of attacks (like sparse $L_0$ attacks or semantic rotations) remains an open challenge.
- Computational Complexity: While the paper proves these values exist and are equivalent, it doesn't provide new algorithms for calculating them efficiently in high-dimensional neural networks, which is often the bottleneck in practice.
Summary updated