Duality for the Adversarial Total Variation

1. Il Problema: Addestramento Adversariale e Variazione Totale Non Locale

Il lavoro si concentra sulla formulazione matematica rigorosa dell'addestramento adversariale per classificatori binari. L'obiettivo è minimizzare il rischio su un dataset soggetto a perturbazioni controllate (attacchi adversariali).
Matematicamente, il problema è formulato come:
$$\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]$$
dove $B_\varepsilon(x)$ è una sfera di raggio $\varepsilon$ (budget adversariale) attorno al punto di input $x$.

Il paper si basa sull'insight fondamentale che, nel caso di classificazione binaria non parametrica, questo problema di ottimizzazione robusta può essere riformulato come un problema di minimizzazione di un rischio regolarizzato:
$$\inf_{u} \mathbb{E}[\ell(u(x), y)] + \varepsilon \cdot \nu\text{-}TV_\varepsilon(u)$$
dove $\nu\text{-}TV_\varepsilon(u)$ è una Variazione Totale (TV) non locale e avversariale. La sfida principale risiede nella natura non differenziabile del termine di variazione totale non locale e nella difficoltà di caratterizzare il suo sottodifferenziale, necessario per lo sviluppo di algoritmi di ottimizzazione (come i metodi primal-dual) e per l'analisi teorica.

2. Metodologia: Analisi Convessa e Dualità

Gli autori utilizzano tecniche di analisi convessa non liscia e teoria della dualità per caratterizzare il sottodifferenziale della variazione totale avversariale. L'approccio si articola in due scenari principali, a seconda dello spazio funzionale considerato per la funzione di classificazione $u$:

1. Spazio delle funzioni continue ($C_0(X)$): Su spazi metrici propri (dove le sottoinsiemi chiusi e limitati sono compatti).
2. Spazio delle funzioni essenzialmente limitate ($L^\infty(\Omega)$): Su domini euclidei $\Omega \subset \mathbb{R}^N$, che è lo spazio naturale per i minimizzatori del problema di addestramento adversariale.

La strategia chiave consiste nel:

• Derivare una rappresentazione duale della variazione totale non locale.
• Introdurre operatori di gradiente e divergenza non locali.
• Stabilire una formula di integrazione per parti che colleghi questi operatori.
• Caratterizzare il sottodifferenziale come l'insieme delle divergenze non locali che massimizzano il funzionale duale.

3. Risultati Chiave e Contributi

A. Caso delle Funzioni Continue ($C_0(X)$)

In questo setting, gli autori dimostrano che la variazione totale può essere scritta come un problema di massimizzazione su un insieme di camminate aleatorie (random walks).

• Riformulazione Duale: La TV è espressa come il massimo su una famiglia di misure di probabilità $m$ (camminate aleatorie) che rappresentano il "movimento" dei dati all'interno della sfera $\varepsilon$.
  $$TV_\varepsilon(u) = \max_{m \in \mathcal{M}} \left( - \int_X u \, d(\text{div}_\varepsilon^\varrho[m]) \right)$$
• Operatori Non Locali: Viene definito un gradiente non locale $\text{grad}_\varepsilon[u](x,y) = \frac{u(y)-u(x)}{\varepsilon}$ e una divergenza pesata $\text{div}_\varepsilon^\varrho[m]$.
• Caratterizzazione del Sottodifferenziale: Il sottodifferenziale $\partial TV_\varepsilon(u)$ è caratterizzato esattamente come l'insieme delle divergenze non locali delle camminate aleatorie ottimali che raggiungono il massimo nella formula duale. Questo risultato è esplicito e costruttivo grazie alla compattezza garantita dal teorema di Prokhorov.

B. Caso delle Funzioni Limitate ($L^\infty(\Omega)$)

Questo caso è più complesso perché lo spazio $L^\infty$ non è separabile e l'insieme delle funzioni test non è compatto nella topologia debole-*.

• Rappresentazione Duale: Gli autori estendono la dualità a funzioni misurabili limitate, utilizzando il supremo essenziale. La rappresentazione duale coinvolge funzioni test $\Psi \in L^1(\Omega \times \Omega)$ (anziché misure generiche).
• Sfida della Compattezza: A differenza del caso continuo, il massimo nella formula duale non è sempre raggiunto da una singola funzione test. Il supremo è raggiunto solo nella chiusura debole-* dell'insieme delle divergenze.
• Caratterizzazione del Sottodifferenziale: Il sottodifferenziale è caratterizzato come l'insieme delle divergenze non locali che appartengono alla chiusura debole-* dell'insieme delle funzioni test ammissibili. Gli autori utilizzano la teoria delle reti (nets) invece delle successioni per gestire la topologia debole-* non sequenziale di $L^\infty(\Omega)^*$.
• Consistenza: Viene dimostrato che, quando $\varepsilon \to 0$, questi operatori non locali convergono agli operatori differenziali locali classici (gradiente e divergenza ponderata), giustificando il nome "variazione totale".

4. Significato e Implicazioni

1. Fondamenti Teorici Rigorosi: Il lavoro fornisce la prima caratterizzazione completa del sottodifferenziale per la variazione totale avversariale, un passo cruciale per comprendere la struttura delle soluzioni del problema di addestramento adversariale.
2. Ponte verso l'Ottimizzazione Numerica: La formulazione duale e la caratterizzazione del sottodifferenziale sono essenziali per progettare algoritmi efficienti. In particolare, aprono la strada all'applicazione di algoritmi primal-dual (simili a quelli usati nel modello ROF per il denoising delle immagini) al problema dell'addestramento adversariale. Attualmente, l'addestramento adversariale si basa spesso su metodi di discesa del gradiente approssimati; una formulazione duale precisa permetterebbe metodi di ottimizzazione non liscia più robusti e convergenti.
3. Generalizzazione: Il paper tratta sia spazi metrici generali che domini euclidei, fornendo un quadro unificato che collega la teoria delle camminate aleatorie, l'analisi non locale e l'apprendimento automatico.
4. Nuove Direzioni di Ricerca: Gli autori suggeriscono che questi risultati potrebbero portare a:
   • Generalizzazioni per misure di riferimento più ampie.
   • Caratterizzazioni puntuali dei sottogradienti tramite accoppiamenti di Anzellotti non locali.
   • Sviluppo di nuovi algoritmi di ottimizzazione per il deep learning robusto.

In sintesi, Bungert e Schmitt trasformano un problema di ottimizzazione non liscia e non convessa apparentemente intrattabile in una struttura duale ben definita, fornendo gli strumenti analitici necessari per lo sviluppo di metodi di addestramento adversariale più robusti e teoricamente fondati.