Solving the Offline and Online Min-Max Problem of Non-smooth Submodular-Concave Functions: A Zeroth-Order Approach

Resumen Técnico: Resolución del Problema Min-Max Offline y Online de Funciones Submodulares-Cóncavas No Suaves

Formulación del Problema
Este trabajo aborda problemas de optimización min-max y max-min de enteros mixtos de la forma:
$$\max_{y \in Y} \min_{S \subset Q} f(S, y) \quad \text{y} \quad \min_{S \subset Q} \max_{y \in Y} f(S, y)$$
donde $Q = [n]$ es un conjunto base de $n$ elementos, $2^Q$ denota el conjunto potencia, y $Y \subset \mathbb{R}^m$ es un conjunto convexo compacto. Se asume que la función objetivo $f: 2^Q \times \mathbb{R}^m \to \mathbb{R}$ es submodular con respecto a la variable de conjunto $S$ y cóncava con respecto a la variable continua $y$. Crucialmente, se permite que la función sea no suave (no diferenciable) con respecto a ambas variables. Los autores buscan calcular un punto de silla $\epsilon$, definido como un par $(\bar{S}, \bar{y})$ tal que la brecha de dualidad esté acotada por $\epsilon$.

Metodología
El enfoque propuesto utiliza un marco de Orden Cero (ZO) basado en el método de extragradiante. La metodología se basa en dos técnicas principales para manejar la no suavidad y la estructura de variables mixtas:

1. Extensión de Lovász para Submodularidad: Para manejar el componente submodular discreto, los autores utilizan la extensión de Lovász $f^L$, que mapea la función de conjunto submodular a una función continua y convexa sobre el hipercubo $[0, 1]^n$. El subgradiente de $f^L$ con respecto a la variable de conjunto puede calcularse utilizando únicamente evaluaciones de la función (mediante una cadena maximal de subconjuntos), evitando la necesidad de información de orden superior.
2. Suavizado Gaussiano para Concavidad: Para la variable cóncava continua $y$, donde la función puede ser no suave, los autores emplean suavizado gaussiano. Definen un oráculo aleatorio utilizando un estimador de dos puntos para aproximar el gradiente de la función suavizada. Esto permite actualizaciones basadas en gradientes sin acceso explícito a derivadas.

El algoritmo resultante (Algoritmo 1, ZO-EG) opera en un bucle iterativo:

• Paso Adelante: Estimar el operador en la iteración actual $z_k = (x_k, y_k)$ muestreando direcciones gaussianas para calcular el oráculo aleatorio para $y$ y calculando el subgradiente para $x$.
• Paso de Extrapolación: Realizar un paso de descenso hacia un punto de visión anticipada $\hat{z}_k$.
• Paso de Actualización: Re-estimar el operador en $\hat{z}_k$ y realizar un segundo paso de descenso para actualizar $z_{k+1}$.

El método requiere únicamente consultas de valores de función (información de orden cero) y no asume acceso directo a gradientes o subgradientes.

Contribuciones Clave y Resultados Teóricos
El artículo proporciona garantías de convergencia para ambos entornos offline y online:

• Convergencia Offline: Los autores demuestran que el algoritmo converge, en expectativa, a un punto de silla $\epsilon$. Se muestra que la complejidad total de muestras es $O(nm^2\epsilon^{-2})$, donde $n$ es el tamaño del conjunto base y $m$ es la dimensión de la variable continua. La dependencia de $n$ surge del costo por iteración de calcular subgradientes de la extensión de Lovász, mientras que el número de iteraciones depende de $m$.
• Convergencia Online: En el entorno online, donde la función de costo $f_k$ cambia con el tiempo, el algoritmo logra una brecha de dualidad online esperada de $O(\sqrt{N \bar{P}_N})$. Aquí, $N$ es el número de iteraciones y $\bar{P}_N$ es la longitud de la trayectoria de la secuencia de decisiones óptimas. Este resultado se alinea con los límites de arrepentimiento dinámico establecidos en la optimización online.
• Existencia de Soluciones: El artículo discute las condiciones bajo las cuales existen puntos de silla para el problema discreto original relacionándolos con las soluciones del problema de extensión de Lovász continuo, específicamente cuando el minimizador de la extensión se encuentra en un vértice del hipercubo.

Resultados Numéricos y Aplicaciones
Los hallazgos teóricos se ilustran mediante ejemplos numéricos, centrándose específicamente en la segmentación de imágenes adversarial y el agrupamiento semi-supervisado:

• Segmentación Adversarial Offline: El método se aplica a un problema min-max donde un adversario perturba los pesos de confianza de los píxeles semilla. El algoritmo recupera con éxito una segmentación que coincide con la verdad fundamental, demostrando robustez frente a perturbaciones adversarias.
• Segmentación Adversarial Online: El algoritmo se prueba en un flujo de video donde las formas y los grupos se mueven y rotan, haciendo que la función de costo cambie en cada cuadro. El método realiza segmentación en tiempo real (aprox. 80 fps en CPU) sin pre-entrenamiento.
• Comparación con Aprendizaje Profundo: En el entorno adversarial online, el método ZO propuesto supera a los modelos U-Net entrenados de forma supervisada y semi-supervisada en términos de Intersección sobre Unión (IoU), precisión y recuperación. Cabe destacar que el método ZO no requiere pre-entrenamiento, tiene una huella de memoria significativamente menor (~0.05 MB frente a ~8 MB para U-Net) y opera eficazmente en entornos no vistos sin acceso a grandes conjuntos de datos.

Significado y Afirmaciones
Los autores afirman que este es el primer estudio dedicado a resolver problemas de optimización min-max con funciones de costo submodulares-cóncavas no suaves. La importancia del trabajo radica en:

1. Cerrar una Brecha: Aborda una clase de problemas min-max combinatorios que previamente eran difíciles de resolver debido a la falta de suavidad y la naturaleza mixta discreta-continua.
2. Eficiencia de Orden Cero: Demuestra que los métodos de orden cero, tradicionalmente utilizados para problemas continuos no suaves, pueden adaptarse eficazmente a la optimización submodular mediante la extensión de Lovász.
3. Robustez y Eficiencia: Los resultados numéricos sugieren que este enfoque ofrece una alternativa viable al aprendizaje profundo para entornos en tiempo real, con recursos limitados y adversarios, particularmente donde el pre-entrenamiento es inviable o el entorno es no estacionario.

El artículo concluye señalando que el trabajo futuro podría explorar la relación entre estas soluciones y los equilibrios de Nash de estrategias mixtas, extender los resultados a funciones de costo submodular-submodular e investigar conjuntos de restricciones no acotados.