Duality for the Adversarial Total Variation

1. Problem Statement

The paper addresses the mathematical foundations of adversarial training for binary classifiers. Adversarial training is formulated as a robust optimization problem where the goal is to minimize the worst-case loss over a perturbation ball $B_\varepsilon(x)$ around each data point:
$$\inf_{u \in \mathcal{H}} \mathbb{E}_{(x,y)\sim\mu} \left[ \sup_{\tilde{x} \in B_\varepsilon(x)} \ell(u(\tilde{x}), y) \right]$$
Previous work (specifically [8]) established that for binary classification with 0-1 loss, this problem is equivalent to minimizing a regularized risk involving a nonlocal adversarial total variation (TV) functional, denoted as $\nu\text{-}TV_\varepsilon(u)$.

The core mathematical challenge is that the presence of the supremum in the objective function destroys differentiability, making standard gradient-based optimization difficult. Furthermore, the nonlocal nature of the functional (involving essential suprema/infima over balls) complicates the derivation of optimality conditions (subgradients).

The authors aim to:

1. Derive dual representations of the nonlocal adversarial total variation.
2. Characterize the subdifferential of this functional to enable the development of rigorous optimality conditions and primal-dual algorithms.
3. Establish these results in two distinct functional settings: continuous functions ($C_0(X)$) and essentially bounded functions ($L^\infty(\Omega)$).

2. Methodology

The authors employ techniques from convex analysis, measure theory, and duality theory. The methodology is split into two main parts based on the underlying function space.

A. Setting 1: Continuous Functions ($C_0(X)$)

• Space: $X$ is a proper metric space; functions are continuous and vanish at infinity ($C_0(X)$).
• Dualization Strategy:
  • The authors first dualize the pointwise maximum and minimum over the ball $B_\varepsilon(x)$ using probability measures.
  • They utilize the Measurable Maximum Theorem to extract a measurable selector, defining a family of probability measures $\{m_x\}_{x \in X}$ known as a random walk (or Markov kernel).
  • They define a nonlocal gradient $\text{grad}_\varepsilon[u](x,y) = \frac{u(y)-u(x)}{\varepsilon}$ and a corresponding nonlocal weighted divergence $\text{div}^\varrho_\varepsilon[m]$.
  • An integration-by-parts formula is established: $\int u \, d(\text{div}^\varrho_\varepsilon[m]) = -\iint \text{grad}_\varepsilon[u] \, dm \, d\varrho$.
• Subdifferential Characterization: The subdifferential is shown to be the set of nonlocal divergences of random walks that attain the maximum in the dual formulation. Due to the compactness of the space of probability measures (Prokhorov's theorem), the supremum is attained, and the subdifferential consists of actual measures.

B. Setting 2: Essentially Bounded Functions ($L^\infty(\Omega)$)

• Space: $\Omega \subset \mathbb{R}^N$ is a bounded convex domain; functions are in $L^\infty(\Omega)$. This is the natural space for minimizers of the adversarial training problem.
• Dualization Strategy:
  • The authors first dualize the essential supremum and infimum using test functions from $L^1(\Omega)$.
  • To handle the lack of compactness in $L^1$ and ensure joint measurability for double integration, they restrict test functions to continuous $L^1$ functions initially, using a "squeezing and mollification" argument to approximate general $L^1$ functions.
  • They define a set of test functions $\Psi \in L^1(\Omega \times \Omega)$ representing joint densities.
  • A nonlocal divergence operator $\text{div}_\varepsilon$ is defined acting on these joint densities.
• Subdifferential Characterization:
  • Unlike the $C_0(X)$ case, the set of nonlocal divergences is not closed in the weak-* topology of $(L^\infty)^*$.
  • The subdifferential is characterized as the weak- closure* of the set of nonlocal divergences.
  • Because $L^\infty$ is not separable, sequential convergence is insufficient; the authors characterize the subdifferential using nets (generalized sequences) converging in the weak-* topology. The dual space is identified as the space of finitely additive measures ($ba$).

3. Key Contributions

1. Dual Representation of Adversarial TV:
   The paper provides explicit dual formulas for the adversarial total variation in two settings:

   • $C_0(X)$: $\text{TV}_\varepsilon(u) = \max_{m \in \mathcal{M}} \left( -\int u \, d(\text{div}^\varrho_\varepsilon[m]) \right)$, where $m$ represents random walks.
   • $L^\infty(\Omega)$: $\text{TV}_\varepsilon(u) = \sup_{\Psi \in \mathcal{P} \times \mathcal{P}} \left( -\int u \, \text{div}_\varepsilon[\Psi; \varrho] \, dx \right)$, where $\Psi$ are joint densities.

2. Nonlocal Operators:
   The authors rigorously define nonlocal gradient and divergence operators that satisfy an integration-by-parts identity analogous to the classical local case. They prove that as $\varepsilon \to 0$, these operators converge to classical local differential operators (gradient and divergence) under appropriate regularity.

3. Subdifferential Characterization:

   • For $C_0(X)$, the subdifferential is explicitly characterized as the set of nonlocal divergences of random walks that maximize the dual functional.
   • For $L^\infty(\Omega)$, the subdifferential is characterized as the weak-* closure of such divergences, requiring the use of nets due to the lack of sequential compactness in the dual of $L^\infty$.

4. Adapted Measurable Maximum Theorem:
   The paper includes a proof (in the Appendix) of an adapted Measurable Maximum Theorem for closed-valued correspondences, which is crucial for establishing the existence of measurable selectors in the $L^\infty$ setting where standard compactness arguments fail.

4. Key Results

• Theorem 2 (Dual Reformulation for $C_0$): Establishes that the adversarial TV is the maximum of the negative integral of $u$ against the nonlocal divergence of a random walk.
• Theorem 4 (Dual Reformulation for $L^\infty$): Establishes the dual representation using joint densities $\Psi$ and the nonlocal divergence $\text{div}_\varepsilon$.
• Proposition 2.18 & 3.20: Provide the necessary and sufficient conditions for a functional to be a subgradient of the adversarial TV in both settings.
• Proposition 3.17: Demonstrates the consistency of the nonlocal operators with classical local operators via Taylor expansion, showing $\text{div}_\varepsilon[\varrho \cdot \text{grad}_\varepsilon[u]] \to \text{div}(\varrho \nabla u)$ as $\varepsilon \to 0$.

5. Significance and Future Directions

• Algorithmic Implications: The dual formulation is the cornerstone for Primal-Dual algorithms (like the Chambolle-Pock algorithm). By reformulating the adversarial training problem as a saddle-point problem involving the nonlocal divergence, the authors pave the way for efficient, provably convergent numerical solvers for adversarial training, moving beyond heuristic gradient ascent methods.
• Theoretical Rigor: The work provides a rigorous convex-analytic framework for adversarial training, clarifying the structure of the solution space and the nature of optimality conditions, which were previously ill-defined due to non-smoothness and non-locality.
• Future Research: The authors suggest extending these results to general reference measures (without densities), refining the subdifferential characterization via Anzellotti pairings (to get pointwise conditions), and developing specific primal-dual algorithms based on these dual formulations.

In summary, this paper bridges the gap between the theoretical understanding of adversarial robustness and practical algorithmic implementation by providing a robust duality framework for the nonlocal total variation functional.