Duality for the Adversarial Total Variation

这篇论文《对抗全变差的对偶性》（Duality for the Adversarial Total Variation）由 Leon Bungert 和 Lucas Schmitt 撰写，旨在为对抗训练（Adversarial Training）中的非局部全变差（Nonlocal Total Variation）泛函建立严格的对偶表述，并刻画其次微分（Subdifferential）。

以下是对该论文的详细技术总结：

1. 研究背景与问题定义

• 对抗训练的挑战：对抗训练旨在通过最小化最坏情况下的风险来提高机器学习模型（特别是深度神经网络）的鲁棒性。其数学形式通常是一个极小极大问题（Min-Max Problem）：
  $$\inf_{u} \mathbb{E}_{(x,y)\sim\mu} \left[ \sup_{\tilde{x} \in B_\varepsilon(x)} \ell(u(\tilde{x}), y) \right]$$
  其中 $B_\varepsilon(x)$ 是以 $x$ 为中心、半径为 $\varepsilon$ 的球。由于目标函数中包含上确界（supremum），该问题通常不可微，且存在性证明困难。
• 非局部全变差视角：在二分类设置下，文献 [8] 指出对抗训练等价于一个带有非局部全变差（Nonlocal TV）正则化的凸优化问题：
  $$\inf_{u} \mathbb{E}[|u(x)-y|] + \varepsilon \cdot \nu\text{-}TV_\varepsilon(u)$$
  其中 $\nu\text{-}TV_\varepsilon(u)$ 涉及函数在 $\varepsilon$-邻域内的最大值与最小值之差。
• 核心问题：为了设计高效的优化算法（如原始 - 对偶算法）并深入理解解的性质，需要像经典全变差（TV）那样，为这个非局部泛函建立对偶公式（Dualization），并明确其次微分的结构。然而，由于非局部算子的特殊性以及函数空间（连续函数 vs $L^\infty$）的不同，直接应用经典理论存在困难。

2. 方法论

论文在两个不同的函数空间设置下分别推导了对偶公式：

设置一：连续函数空间 $C_0(X)$

• 空间定义：$X$ 为适当的度量空间（Proper Metric Space），$C_0(X)$ 为在无穷远处消失的连续函数空间。
• 核心工具：
  • 随机游走（Random Walks）：将邻域内的最大值/最小值问题转化为在概率测度族上的优化问题。
  • 可测最大值定理（Measurable Maximum Theorem）：用于从逐点的优化问题中提取一个可测的“随机游走”选择器（Selector），从而定义全局的测试函数族。
  • 非局部算子：定义非局部梯度 $\text{grad}_\varepsilon[u](x,y) = \frac{u(y)-u(x)}{\varepsilon}$ 和非局部散度 $\text{div}_\varepsilon$。
• 对偶形式：将 $TV_\varepsilon(u)$ 表示为关于随机游走测度的线性泛函的最大值。

设置二：本质有界函数空间 $L^\infty(\Omega)$

• 空间定义：$\Omega \subset \mathbb{R}^N$ 为有界凸域，函数 $u \in L^\infty(\Omega)$。这是对抗训练解自然存在的空间。
• 核心挑战：$L^\infty$ 不可分，且其双对偶空间复杂；本质确界（Essential Supremum）的处理比连续函数的最大值更困难。
• 核心工具：
  • 本质确界的对偶化：利用 $L^1$ 空间中的概率密度函数来表征本质确界。
  • 磨光与挤压（Mollification and Squeezing）：为了构造联合可测的测试函数，作者先将测试函数限制为连续函数，通过“挤压”支持集和“磨光”操作，证明连续测试函数族在 $L^1$ 意义下可以逼近一般的 $L^1$ 测试函数。
  • 广义可测最大值定理：由于 $L^\infty$ 对偶空间缺乏紧性，经典定理不再适用，作者在附录中推广了该定理，利用网（Nets）而非序列来处理弱*-拓扑下的闭包问题。
• 对偶形式：将 $TV_\varepsilon(u)$ 表示为关于 $L^1(\Omega \times \Omega)$ 中特定测试函数族 $\Psi$ 的线性泛函的上确界。

3. 主要贡献与结果

A. 对偶公式的建立

论文成功推导了两种设置下的对偶公式：

1. $C_0(X)$ 情形：
   $$TV_\varepsilon(u) = \max_{m \in \mathcal{M} \times \mathcal{M}} \left( - \int_X u \, d\text{div}_\varepsilon^\varrho[m] \right)$$
   其中 $\mathcal{M}$ 是满足支持集条件的随机游走（Markov 核）集合，$\text{div}_\varepsilon^\varrho$ 是加权非局部散度。
2. $L^\infty(\Omega)$ 情形：
   $$TV_\varepsilon(u) = \sup_{\Psi \in \mathcal{P} \times \mathcal{P}} \left( - \int_\Omega u \, \text{div}_\varepsilon[\Psi; \varrho] \, dx \right)$$
   其中 $\mathcal{P}$ 是 $L^1(\Omega \times \Omega)$ 中满足特定支撑和归一化条件的函数集合。

B. 次微分（Subdifferential）的刻画

这是论文最核心的理论贡献：

• 在 $C_0(X)$ 中：次微分 $\partial TV_\varepsilon(u)$ 中的元素可以显式刻画为达到上述对偶最大值的随机游走的非局部散度。即 $\mu^* = -\text{div}_\varepsilon^\varrho[m]$，其中 $m$ 是使对偶公式取等的随机游走。
• 在 $L^\infty(\Omega)$ 中：由于 $L^\infty$ 对偶空间的复杂性（包含有限可加测度），次微分不能简单地表示为某个具体的函数。作者给出了极限刻画：次微分元素 $\mu^*$ 属于集合 $\{-\text{div}_\varepsilon[\Psi; \varrho] : \Psi \in \mathcal{P} \times \mathcal{P}\}$ 在 $L^\infty(\Omega)^*$ 弱*-拓扑下的闭包。这意味着 $\mu^*$ 可以通过一个测试函数网（Net）的极限来逼近。

C. 非局部算子的一致性

• 证明了定义的非局部梯度 $\text{grad}_\varepsilon$ 和散度 $\text{div}_\varepsilon$ 满足分部积分公式（Integration by Parts）。
• 证明了当 $\varepsilon \to 0$ 时，这些非局部算子在适当正则性假设下收敛于经典的局部微分算子（如 $\text{div}(\rho \nabla u)$），从而验证了“非局部全变差”命名的合理性及其与经典 BV 理论的联系。

4. 意义与影响

1. 理论突破：首次为对抗训练中的非局部全变差泛函建立了严格的对偶理论，填补了从经典局部 TV 到非局部对抗 TV 之间的理论空白。
2. 算法指导：对偶公式的获得为设计原始 - 对偶算法（Primal-Dual Algorithms，如 Chambolle-Pock 算法）解决对抗训练问题铺平了道路。类似于图像去噪中的 ROF 模型，利用对偶形式可以将非光滑优化问题转化为鞍点问题，从而利用投影梯度法高效求解。
3. 次微分理解：明确了次梯度的结构（非局部散度），这对于理解对抗训练解的几何性质（如决策边界的平滑性）至关重要。
4. 数学工具创新：在处理 $L^\infty$ 空间时，通过推广可测最大值定理和使用“网”的概念，解决了非紧性带来的技术难题，为处理非可分空间中的变分问题提供了范例。

5. 总结

该论文通过引入随机游走、非局部梯度/散度算子以及改进的可测选择理论，成功地将对抗训练问题转化为一个具有清晰对偶结构的凸优化问题。这不仅深化了对对抗鲁棒性数学本质的理解，也为开发更高效的对抗训练算法奠定了坚实的数学基础。未来的工作将集中在利用这些对偶结果设计具体的数值算法，以及进一步细化 $L^\infty$ 情形下的次微分表征。