Duality for the Adversarial Total Variation

Resumen Técnico: Dualidad para la Variación Total Adversarial

1. Planteamiento del Problema

El entrenamiento adversarial en aprendizaje automático, particularmente en clasificadores binarios, se formula como un problema de minimización de riesgo robusto. Dado un conjunto de datos con distribución $\mu$ sobre un espacio de características $X$ y etiquetas $Y$, el objetivo es encontrar una hipótesis $u$ que minimice el peor caso de pérdida dentro de una bola de radio $\varepsilon$ alrededor de cada punto de entrada:

$$\inf_{u \in H} \mathbb{E}_{(x,y)\sim\mu} \left[ \sup_{\tilde{x} \in B_\varepsilon(x)} \ell(u(\tilde{x}), y) \right]$$

Donde $\varepsilon$ es el "presupuesto adversarial".
En el contexto de clasificación binaria no paramétrica con pérdida 0-1, se ha demostrado que este problema es equivalente a una minimización de riesgo regularizado que involucra una Variación Total No Local (TV adversarial), denotada como $\nu\text{-}TV_\varepsilon(u)$.

El desafío matemático principal radica en la naturaleza no diferenciable del supremo en la función objetivo y la falta de una teoría dual robusta para esta variación total no local, lo cual es crucial para:

1. Caracterizar las condiciones de optimalidad (subgradientes).
2. Desarrollar algoritmos de optimización eficientes (como métodos primal-dual).

2. Metodología

Los autores abordan el problema utilizando técnicas de análisis convexo no suave y teoría de la dualidad. El enfoque central es reformular la variación total adversarial como un problema de optimización dual, identificando un conjunto de "funciones de prueba" (test functions) y operadores no locales análogos al gradiente y la divergencia.

El análisis se divide en dos escenarios fundamentales, dependiendo del espacio de funciones considerado:

• Escenario A: Funciones Continuas ($C_0(X)$)

  • Espacio: Funciones continuas que se anulan en el infinito sobre un espacio métrico propio $X$.
  • Herramientas: Se utiliza el Teorema del Máximo Medible (Measurable Maximum Theorem) para extraer selectores medibles.
  • Estructura: Las funciones de prueba se interpretan como caminos aleatorios (random walks) o kernels de Markov sobre el espacio métrico.

• Escenario B: Funciones Acotadas Esencialmente ($L^\infty(\Omega)$)

  • Espacio: Funciones en $L^\infty(\Omega)$ donde $\Omega \subset \mathbb{R}^N$ es un dominio convexo. Este es el espacio natural donde residen los minimizadores del problema original.
  • Herramientas: Se requiere una generalización del Teorema del Máximo Medible para correspondencias de valor cerrado (ya que el conjunto de funciones de prueba no es compacto en la topología débil-*).
  • Estructura: Las funciones de prueba son funciones en $L^1(\Omega \times \Omega)$ con soporte acotado, en lugar de medidas de probabilidad.

3. Contribuciones Clave y Resultados

A. Reformulación Dual y Operadores No Locales

El trabajo establece representaciones duales para la variación total adversarial $\nu\text{-}TV_\varepsilon(u)$ en ambos espacios.

1. Para $C_0(X)$:
   La TV se expresa como el máximo sobre un conjunto de caminos aleatorios $\mathcal{M}$:
   $$TV_\varepsilon(u) = \max_{m \in \mathcal{M}} \left( - \int_X u \, d(\text{div}_\varepsilon^\varrho[m]) \right)$$
   Donde $\text{div}_\varepsilon^\varrho[m]$ es una divergencia no local ponderada definida sobre medidas de Radon. El subgradiente se caracteriza explícitamente como la divergencia de un camino aleatorio que alcanza el máximo.

2. Para $L^\infty(\Omega)$:
   La TV se expresa como el supremo sobre un conjunto de funciones $\mathcal{P} \subset L^1(\Omega \times \Omega)$:
   $$TV_\varepsilon(u) = \sup_{\Psi \in \mathcal{P}} \left( - \int_\Omega u(x) \, \text{div}_\varepsilon[\Psi; \varrho](x) \, dx \right)$$
   Aquí, la divergencia no local $\text{div}_\varepsilon$ actúa sobre funciones $L^1$ y produce una función en $L^1$.

B. Definición de Gradiente y Divergencia No Locales

Los autores definen rigurosamente:

• Gradiente No Local: $\text{grad}_\varepsilon[u](x, y) = \frac{u(y) - u(x)}{\varepsilon}$.
• Divergencia No Local: Un operador adjunto que satisface una fórmula de integración por partes:
  $$\int \int \text{grad}_\varepsilon[u](x,y) \Psi(x,y) \, d\mu = - \int u(x) \text{div}_\varepsilon[\Psi] \, d\mu$$
  Se demuestra que, bajo condiciones de regularidad ($\varepsilon \to 0$), estos operadores convergen a los operadores diferenciales locales clásicos (gradiente y divergencia ponderada), justificando la nomenclatura.

C. Caracterización del Subdiferencial

El resultado más significativo es la caracterización del subdiferencial $\partial TV_\varepsilon(u)$:

• En $C_0(X)$: El subdiferencial es un conjunto cerrado y convexo de medidas de Radon. Un elemento $\mu^*$ pertenece al subdiferencial si y solo si existe un camino aleatorio $m$ tal que $\mu^* = -\text{div}_\varepsilon^\varrho[m]$ y se cumple la condición de alineación $\int u d\mu^* = TV_\varepsilon(u)$.
• En $L^\infty(\Omega)$: Debido a la falta de separabilidad de $L^\infty$, el subdiferencial no se puede caracterizar mediante una secuencia simple. Los autores demuestran que $\mu^* \in \partial TV_\varepsilon(u)$ si y solo si $\mu^*$ pertenece a la clausura débil-* del conjunto de divergencias no locales. Esto requiere el uso de redes (nets) en lugar de secuencias para la convergencia, y los subgradientes se identifican como medidas finitamente aditivas absolutamente continuas respecto a la medida de Lebesgue.

4. Significado e Impacto

1. Fundamentación Teórica: El trabajo proporciona la primera caracterización rigurosa y dual de la variación total adversarial, llenando un vacío en la comprensión matemática del entrenamiento adversarial no paramétrico.
2. Puente hacia la Optimización: Al dualizar el problema, se habilita el uso de algoritmos Primal-Dual (como el algoritmo de Chambolle-Pock), que son altamente eficientes para problemas de variación total. Esto ofrece una ruta prometedora para resolver el problema de entrenamiento adversarial de manera más eficiente que los métodos de gradiente ascendente proyectado actuales.
3. Generalidad: La distinción entre el espacio de funciones continuas (donde se obtienen resultados explícitos con caminos aleatorios) y el espacio $L^\infty$ (donde se obtienen resultados de límite) ofrece una visión completa de la estructura del problema, abarcando desde la teoría de espacios métricos generales hasta aplicaciones en dominios euclídeos.
4. Conexión con Geometría: La convergencia de los operadores no locales a sus contrapartes locales conecta el entrenamiento adversarial con flujos de curvatura media y teoría de funciones de variación acotada (BV), unificando conceptos de análisis geométrico y aprendizaje automático.

En conclusión, Bungert y Schmitt establecen las bases analíticas necesarias para tratar el entrenamiento adversarial como un problema de optimización convexa no suave bien definido, abriendo la puerta a nuevos algoritmos y una comprensión más profunda de la robustez en redes neuronales.