Introduction
Adversarial risk has become the primary metric for evaluating the robustness of machine learning models against malicious perturbations. Despite its widespread use, the mathematical foundations of adversarial risk have remained fragmented. Different research communities define the adversary's capabilities using varying frameworks—such as set expansions, transport maps, or Markov kernels—often without establishing formal links between them. Furthermore, many existing definitions overlook subtle measure-theoretic issues that can render the risk technically undefined.
This work provides a rigorous unification of adversarial risk definitions, resolving long-standing measurability problems and proving the existence of pure Nash equilibria in the adversarial game.
Resolving the Measurability Gap
A fundamental issue in adversarial machine learning is the "well-definedness" of the risk itself. In standard probability theory, the adversary's capability is often modeled by expanding a decision boundary by a radius $\epsilon$ (the Minkowski sum). However, the expansion of a Borel measurable set is not necessarily Borel measurable. If the resulting set is not measurable, its probability cannot be calculated, leaving the foundational equations of adversarial risk mathematically unsound.
The authors resolve this by moving beyond standard Borel $\sigma$-algebras. They demonstrate that by utilizing the universal completion of the Borel $\sigma$-algebra—or the Lebesgue $\sigma$-algebra in Euclidean spaces—adversarial risk becomes mathematically rigorous. This ensures that the probability of an adversarial event is always well-defined, providing a stable ground for further theoretical development.
A Unified Framework for Adversarial Risk
One of the paper's central contributions is the establishment of a "Rosetta Stone" for adversarial risk. The authors prove that several seemingly disparate definitions of risk are, in fact, equivalent under specific continuity conditions (specifically, upper semi-continuous loss functions). These include:
- Set Expansion ($R_{\oplus}$): Defining risk based on the Minkowski sum of the error set.
- $\infty$-Wasserstein Perturbations ($R_{\Gamma_\epsilon}$): Viewing the adversary as shifting the data distribution within a specific Wasserstein distance.
- Transport Maps ($R_{F_\epsilon}$): Modeling the adversary as a function that maps clean inputs to perturbed ones.
- Markov Kernels ($R_{K_\epsilon}$): A probabilistic approach to data perturbation.
By proving $R_{\oplus} = R_{\Gamma_\epsilon} = R_{F_\epsilon} = R_{K_\epsilon}$, the authors allow researchers to switch between these perspectives depending on which is most convenient for a given problem, without fear of changing the underlying metric.
Optimal Transport and Unequal Priors
The paper further connects adversarial risk to optimal transport theory by generalizing Strassen’s theorem. While previous research linked optimal adversarial risk to transport costs, those results were largely restricted to datasets with equal class proportions (50/50 priors).
The authors extend this to "unbalanced" optimal transport, accounting for datasets where class priors are unequal. They derive a generalized formula for optimal adversarial risk, showing it relates to a specific optimal transport cost $D_\epsilon$. This result provides a powerful tool for analyzing robust classification in real-world, imbalanced datasets.
The Existence of Nash Equilibria
In the zero-sum game between an adversary (trying to maximize error) and a classifier (trying to minimize it), the existence of a stable solution—a Nash equilibrium—is not always guaranteed. Previous literature suggested that pure Nash equilibria might not exist in this setting unless the adversary was artificially regularized.
However, this paper proves the existence of a pure Nash equilibrium in the standard formulation for binary classification in $\mathbb{R}^d$ and Polish spaces with a "midpoint property." This result guarantees that there is a worst-case pair of perturbed distributions and a corresponding optimal decision region for the classifier, solidifying the game-theoretic interpretation of robust machine learning.
Conclusion and Future Directions
By patching the foundational mathematics and unifying disparate definitions, this work provides a robust theoretical framework for adversarial machine learning. While the most advanced results regarding Nash equilibria and generalized Strassen's theorem are currently focused on binary classification with 0-1 loss, they lay the groundwork for future expansions. Open questions remain regarding whether these equivalences hold for other perturbation models (such as total variation) and how these results might scale to multi-class classification environments.
Summary updated