Duality for the Adversarial Total Variation

1. Problemstellung und Motivation

Das Paper adressiert die mathematische Analyse des adversarialen Trainings für binäre Klassifikatoren. Adversarial Training zielt darauf ab, die Robustheit von Machine-Learning-Modellen gegenüber kleinen, gezielten Eingabestörungen (Adversarial Attacks) zu erhöhen.

Mathematisch wird dies als ein Robust-Optimierungsproblem formuliert:
$$\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]$$
wobei $B_\varepsilon(x)$ eine $\varepsilon$-Umgebung um den Datenpunkt $x$ ist und $\ell$ eine Verlustfunktion ist.

Ein zentrales Ergebnis früherer Arbeiten (insbesondere [8]) zeigt, dass dieses Problem im nicht-parametrischen binären Setting äquivalent zu einem Regularisierungsproblem mit einem nicht-lokalen Total-Variation-Funktional ($\nu\text{-}TV_\varepsilon$) ist:
$$\inf_{u} \mathbb{E}[\ell(u(x), y)] + \varepsilon \cdot \nu\text{-}TV_\varepsilon(u)$$
Das Funktional $\nu\text{-}TV_\varepsilon$ misst die „Länge" der Entscheidungsgrenze unter Berücksichtigung von Nachbarschaften im Raum.

Das Kernproblem: Die direkte Analyse und numerische Lösung dieses Problems ist schwierig, da das Supremum über die Störung die Differenzierbarkeit der Zielfunktion zerstört. Um effiziente Algorithmen (wie Primal-Dual-Methoden) und tiefere analytische Einsichten zu gewinnen, ist eine duale Formulierung des Total-Variation-Funktionals sowie eine Charakterisierung seines Subdifferentials notwendig. Bisher fehlten solche dualen Darstellungen für den adversarialen, nicht-lokalen Fall in allgemeinen Räumen.

2. Methodik

Die Autoren wenden Techniken der konvexen Analysis und der Dualitätstheorie an, um das nicht-lokale Funktional zu dualisieren. Sie untersuchen zwei verschiedene mathematische Settings, die sich in der Wahl des Basisraums und der zugrundeliegenden Topologie unterscheiden:

1. Raum der stetigen Funktionen ($C_0(X)$):

   • Basisraum: $C_0(X)$, der Raum stetiger Funktionen auf einem metrischen Raum $X$, die im Unendlichen verschwinden (auf kompakten Räumen $C(X)$).
   • Dualraum: Der Raum der endlichen signierten Radon-Maße.
   • Hauptwerkzeug: Der messbare Maximum-Satz (Measurable Maximum Theorem). Dies ermöglicht es, für jeden Punkt $x$ ein maximierendes Maß (eine Dirac-Masse am Maximum) zu finden und diese Auswahl messbar über den gesamten Raum zu machen.

2. Raum der wesentlich beschränkten Funktionen ($L^\infty(\Omega)$):

   • Basisraum: $L^\infty(\Omega)$ auf einem euklidischen Gebiet $\Omega \subset \mathbb{R}^N$.
   • Herausforderung: Da $L^\infty$ nicht separabel ist, ist der Dualraum komplexer (Raum der endlich additiven Maße). Zudem fehlt die Kompaktheit, die im stetigen Fall durch den Satz von Prokhorov gegeben war.
   • Hauptwerkzeug: Eine angepasste Version des messbaren Maximum-Satzes für abgeschlossene Korrespondenzen (siehe Anhang A), um messbare Selektoren zu konstruieren. Die Autoren nutzen die euklidische Struktur, um gemeinsame Messbarkeit (joint measurability) der Testfunktionen zu gewährleisten.

In beiden Fällen definieren die Autoren nicht-lokale Operatoren:

• Nicht-lokaler Gradient: $\text{grad}_\varepsilon[u](x, y) = \frac{u(y) - u(x)}{\varepsilon}$.
• Nicht-lokale Divergenz: Ein adjungierter Operator, der auf Wahrscheinlichkeitsmaßen (bzw. Dichten) wirkt.

3. Wichtige Beiträge und Ergebnisse

A. Duale Formulierung für $C_0(X)$

Für stetige Funktionen auf einem metrischen Raum wird gezeigt, dass das Total-Variation-Funktional als Maximum über eine Menge von zufälligen Spaziergängen (Random Walks) dargestellt werden kann.

• Testfunktionen: Eine Familie von Wahrscheinlichkeitsmaßen $m = \{m_x\}_{x \in X}$, wobei $\text{supp}(m_x) \subset B_\varepsilon(x)$. Dies entspricht einem Markov-Kernel.
• Dualität:
  $$TV_\varepsilon(u) = \max_{m \in \mathcal{M} \times \mathcal{M}} \left( - \int_X u \, d(\text{div}_\varepsilon^\varrho[m]) \right)$$
  wobei $\text{div}_\varepsilon^\varrho[m]$ eine gewichtete nicht-lokale Divergenz ist.
• Subdifferential: Das Subdifferential $\partial TV_\varepsilon(u)$ besteht genau aus den nicht-lokalen Divergenzen jener Random Walks, die das Maximum in der dualen Formulierung annehmen. Da der Raum der Maße kompakt ist (im schwach-* Topologie), wird das Maximum immer angenommen.

B. Duale Formulierung für $L^\infty(\Omega)$

Für wesentlich beschränkte Funktionen auf euklidischen Gebieten wird eine ähnliche, aber technisch anspruchsvollere Dualität hergeleitet.

• Testfunktionen: Hier sind die Testfunktionen Paare von Dichten $\Psi = (\Psi_0, \Psi_1) \in L^1(\Omega \times \Omega)$ mit $\Psi_i \geq 0$, $\int \Psi_i(x, y) dy = 1$ und $\text{ess supp}(\Psi_i(x, \cdot)) \subset B_\varepsilon(x)$.
• Dualität:
  $$TV_\varepsilon(u) = \sup_{\Psi \in \mathcal{P} \times \mathcal{P}} \left( - \int_\Omega u(y) \, \text{div}_\varepsilon[\Psi; \varrho](y) \, dy \right)$$
• Unterschied zum stetigen Fall: Aufgrund des Fehlens von Kompaktheit in $L^1$ bezüglich der schwach-* Topologie von $L^\infty$ wird das Supremum im Allgemeinen nicht durch ein Element aus der Menge der Testfunktionen angenommen.
• Charakterisierung des Subdifferentials: Das Subdifferential wird als Abschluss (im Sinne der schwach-* Topologie) der Menge der nicht-lokalen Divergenzen charakterisiert. Die Autoren verwenden das Konzept von Netzen (statt Sequenzen), um die Konvergenz in diesem nicht-separablen Raum zu beschreiben.

C. Konsistenz und Grenzwerte

• Die Autoren zeigen, dass die definierten nicht-lokalen Gradienten und Divergenzen konsistent mit ihren klassischen lokalen Gegenstücken sind. Für glatte Funktionen $u$ und $\varepsilon \to 0$ konvergieren die nicht-lokalen Operatoren gegen den klassischen Gradienten und die Divergenz (bis auf einen Skalierungsfaktor).
• Im Spezialfall, wo die Maxima/Minima eindeutig sind (z.B. bei $C^2$-Funktionen mit strikt positivem Gradienten), stimmen die dualen Darstellungen mit den in der Literatur bekannten expliziten Subgradienten überein.

4. Signifikanz und Implikationen

Die Arbeit leistet einen wesentlichen Beitrag zur mathematischen Fundierung des adversarialen Trainings:

1. Analytische Klarheit: Durch die duale Formulierung wird das nicht-differenzierbare Problem in ein Sattelpunktproblem umgewandelt. Dies erlaubt die Anwendung mächtiger Werkzeuge der konvexen Analysis.
2. Charakterisierung des Subdifferentials: Die explizite Beschreibung der Subgradienten als (Grenzwerte von) nicht-lokalen Divergenzen ist entscheidend für das Verständnis der Optimalitätsbedingungen. Dies ist analog zur Rolle der Anzellotti-Paarungen bei der klassischen Total-Variation.
3. Algorithmische Perspektive: Die duale Struktur (Primal-Dual-Formulierung) legt den Grundstein für die Entwicklung neuer, effizienter Algorithmen. Ähnlich wie beim ROF-Modell (Bildentrauschung) könnten Primal-Dual-Gradientenmethoden (wie in [22]) auf das adversarialen Trainingsproblem übertragen werden, um die Minimierung des nicht-glatten Zielfunktionals zu beschleunigen.
4. Verallgemeinerung: Die Unterscheidung zwischen dem separablen Fall ($C_0$) und dem nicht-separablen Fall ($L^\infty$) zeigt die Grenzen und Möglichkeiten der Dualitätstheorie in verschiedenen Maßtheorie-Kontexten auf und liefert eine robuste Basis für zukünftige Erweiterungen (z.B. auf allgemeine Referenzmaße).

Zusammenfassend bietet das Paper eine rigorose mathematische Brücke zwischen adversarialer Robustheit und nicht-lokaler Variationsrechnung, die sowohl theoretische Einsichten als auch praktische algorithmische Ansätze für robustes Deep Learning eröffnet.