Duality for the Adversarial Total Variation

Résumé Technique : Dualité pour la Variation Totale Adversariale

1. Problématique et Contexte

L'article s'attaque au problème mathématique fondamental de l'entraînement adversaire (adversarial training) pour les classificateurs binaires. Ce processus vise à améliorer la robustesse des modèles d'apprentissage automatique face à de petites perturbations malveillantes des données d'entrée.

Mathématiquement, ce problème est formulé comme une minimisation de risque robuste :
$$\inf_{u \in H} \mathbb{E}_{(x,y)\sim\mu} \left[ \sup_{\tilde{x} \in B_\varepsilon(x)} \ell(u(\tilde{x}), y) \right]$$
où $B_\varepsilon(x)$ est une boule de rayon $\varepsilon$ (le budget adversaire) autour de l'entrée $x$.

Il a été démontré précédemment (notamment dans [8]) que, dans le cadre de la classification binaire non paramétrique, ce problème peut être reformulé comme une minimisation de risque régularisée impliquant une variation totale non locale ($\nu\text{-}TV_\varepsilon$). Cependant, la compréhension mathématique de cette fonctionnelle, en particulier la caractérisation de son sous-différentiel (nécessaire pour les conditions d'optimalité et les algorithmes), reste complexe en raison de la présence du supremum et de la non-linéarité.

L'objectif principal de cet article est d'établir des formules de dualité pour cette variation totale adversariale et de caractériser son sous-différentiel en utilisant des techniques d'analyse convexe non lisse et de théorie de la mesure.

2. Méthodologie

Les auteurs abordent le problème sous deux angles distincts, selon l'espace fonctionnel de base considéré, en s'appuyant sur la dualité et l'analyse convexe :

A. Cadre des fonctions continues ($C_0(X)$)

• Espace : $C_0(X)$, l'espace des fonctions continues sur un espace métrique propre $X$ s'annulant à l'infini.
• Approche : Les auteurs reformulent le supremum et l'infimum locaux (sur les boules $B_\varepsilon(x)$) comme des maximisations sur des ensembles de mesures de probabilité.
• Outils clés :
  • Utilisation du théorème du maximum mesurable pour extraire des sélecteurs mesurables.
  • Introduction de la notion de marche aléatoire (random walk) sur l'espace métrique, définie comme une famille de mesures de probabilité dépendant mesurablement du point de départ.
  • Définition d'un gradient non local ($\text{grad}_\varepsilon$) et d'une divergence non local ($\text{div}_\varepsilon$) agissant sur ces marches aléatoires.
  • Démonstration d'une formule d'intégration par parties reliant ces opérateurs.

B. Cadre des fonctions essentiellement bornées ($L^\infty(\Omega)$)

• Espace : $L^\infty(\Omega)$ où $\Omega \subset \mathbb{R}^N$ est un domaine convexe, avec des distributions conditionnelles absolument continues par rapport à la mesure de Lebesgue.
• Défi : L'espace $L^\infty$ n'est pas séparable, et son dual est l'espace des mesures finiment additives ($ba$), ce qui complique la caractérisation explicite des sous-gradients. De plus, le supremum essentiel ne se comporte pas aussi bien que le maximum continu.
• Approche :
  • Dualisation du supremum et de l'infimum essentiels via des fonctions tests dans $L^1$.
  • Construction de fonctions tests jointement mesurables (via des approximations par régularisation et "écrasement" des supports) pour garantir la validité des intégrales doubles.
  • Définition d'une divergence non local agissant sur des fonctions de $L^1(\Omega \times \Omega)$.
  • Caractérisation du sous-différentiel via la fermeture faible-* de l'ensemble des divergences, nécessitant l'utilisation de filtres (nets) plutôt que de suites simples.

3. Résultats Clés

1. Formules de Dualité
Les auteurs établissent que la variation totale adversariale $TV_\varepsilon(u)$ admet une représentation duale sous forme de problème de maximisation :

• Cas $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)$$
  où $\mathcal{M}$ est l'ensemble des marches aléatoires admissibles et $\text{div}_\varepsilon^\varrho$ est une divergence pondérée.
• Cas $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)$$
  où $\mathcal{P}$ est un ensemble de fonctions de densité dans $L^1(\Omega \times \Omega)$.

2. Caractérisation du Sous-Différentiel

• Pour $C_0(X)$ : Le sous-différentiel $\partial TV_\varepsilon(u)$ est caractérisé de manière explicite. Un élément $u^*$ appartient à $\partial TV_\varepsilon(u)$ si et seulement si $u^* = -\text{div}_\varepsilon^\varrho[m]$ pour une marche aléatoire $m$ qui atteint le maximum dans la formule de dualité, et satisfait une condition d'égalité d'énergie.
• Pour $L^\infty(\Omega)$ : En raison du manque de compacité, le supremum n'est pas toujours atteint. Le sous-différentiel est caractérisé comme l'adhérence faible-* (dans le dual de $L^\infty$) de l'ensemble des divergences non locales. Les auteurs fournissent une caractérisation limite utilisant des nets de fonctions tests.

3. Cohérence avec les Opérateurs Locaux
Les auteurs montrent que leurs opérateurs non locaux (gradient et divergence) convergent vers les opérateurs différentiels classiques (gradient et divergence de la variation totale locale) lorsque le paramètre $\varepsilon \to 0$, sous des hypothèses de régularité appropriées. Cela valide la terminologie "variation totale" pour ce fonctionnel non local.

4. Contributions Majeures

• Cadre Unifié : Développement d'une théorie de dualité cohérente pour la variation totale adversariale dans deux contextes fondamentaux (fonctions continues et fonctions bornées).
• Nouveaux Opérateurs : Introduction rigoureuse de gradients et divergences non locaux adaptés aux structures de marches aléatoires et aux espaces $L^p$.
• Outils Analytiques : Adaptation et généralisation du théorème du maximum mesurable pour traiter les correspondances à valeurs fermées dans des espaces non compacts, et utilisation de la théorie des nets pour l'analyse dans $L^\infty$.
• Lien Théorique : Établissement d'un pont clair entre l'entraînement adversaire, la régularisation par variation totale et l'analyse convexe non lisse.

5. Signification et Perspectives

Ce travail est une avancée significative pour la théorie de l'apprentissage automatique robuste :

• Algorithmique : La caractérisation du sous-différentiel ouvre la voie à la conception d'algorithmes d'optimisation primal-dual (similaires à ceux utilisés pour le débruitage ROF ou la variation totale classique) pour résoudre directement les problèmes d'entraînement adversaire, évitant ainsi les approximations par descente de gradient sur le supremum.
• Analytique : Cela fournit des conditions d'optimalité rigoureuses pour les solutions de l'entraînement adversaire, permettant une meilleure compréhension de la géométrie des frontières de décision robustes.
• Généralisation : Les résultats préparent le terrain pour l'extension à des mesures de référence générales et à des cas multi-classes, ainsi que pour le développement de versions non locales des couplages d'Anzellotti.

En résumé, cet article transforme un problème d'optimisation non lisse et non convexe en apparence, en un problème de régularisation convexe bien posé, en fournissant les outils mathématiques nécessaires (dualité et sous-différentiels) pour son analyse et sa résolution numérique.