Online Convex Optimization with Sublinear Noisy Probes

Resumen Técnico: Optimización Convexa en Línea con Sondas Ruidosas Sublineales

Formulación del Problema
Este artículo investiga la Optimización Convexa en Línea (OCO, por sus siglas en inglés) sobre un conjunto convexo $K \subseteq \mathbb{R}^d$. En el entorno estándar, un aprendiz selecciona una decisión $x_t \in K$ en cada ronda $t$, incurre en una pérdida convexa $f_t(x_t)$ elegida de forma adversaria, y recibe retroalimentación completa (la función $f_t$ o sus subgradientes). El objetivo es minimizar el arrepentimiento (regret) frente a la mejor decisión fija conocida a posteriori.

Los autores introducen un modelo de sondeo (probing) unificado que generaliza dos líneas de trabajo recientes: las consultas de mejor experto sublineales en el entorno de expertos [Russo et al., 2024] y la retroalimentación de comparación por pares en OCO [Bhaskara et al., 2023b]. En este marco, el aprendiz cuenta con un presupuesto de $k \le T$ sondeos por pares. En una ronda de sondeo, antes de seleccionar $x_t$, el aprendiz puede consultar dos puntos $\{y_{t,1}, y_{t,2}\} \subseteq K$ y recibir una indicación de qué punto incurre en la menor pérdida. Crucialmente, estos sondeos son ruidosos: con una probabilidad $\delta$, el oráculo devuelve el punto con la pérdida mayor (la respuesta "incorrecta"), y con una probabilidad $1-\delta$, devuelve el minimizador correcto. El parámetro de ruido $\delta \in [0, 1]$ es desconocido para el aprendiz.

El protocolo asume un adversario de tipo olvidadizo (oblivious adversary) que se compromete previamente con la secuencia de funciones de pérdida $\{f_t\}_{t=1}^T$ antes de que el aprendiz decida si realizar un sondeo en una ronda específica. Esta restricción es vital; si el adversario pudiera adaptarse a la decisión de sondeo (por ejemplo, estableciendo las pérdidas en 0 en las rondas de sondeo), el sondeo podría quedar inútful, degradando el límite de arrepentimiento a $\Theta(\sqrt{T-k})$.

Metodología
El algoritmo propuesto es una versión adaptativa y aumentada por sondeos de los Pesos Exponenciales Continuos (CEW). La idea técnica central se basa en un efecto de reducción de la varianza combinado con un análisis de segundo orden (basado en la varianza) del algoritmo CEW.

1. Reducción de la Varianza mediante Sondeo:
   En una ronda de sondeo, el algoritmo muestrea dos puntos de forma independiente de la distribución de densidad actual $p_t$. Al jugar el punto con la menor pérdida observada (o el sugerido por el sondeo), la pérdida esperada disminuye en una cantidad proporcional a la varianza de la función de pérdida bajo $p_t$, denotada como $v_t = \text{Var}_{x \sim p_t}[f_t(x)]$. Específicamente, para sondeos sin ruido, la pérdida esperada se reduce por $v_t$.

2. Manejo de Sondeos Ruidosos (Meta-Aprendiz):
   Dado que $\delta$ es desconocido, el algoritmo emplea un Meta-Aprendiz ligero (específicamente AdaHedge) para decidir si debe "seguir" la sugerencia del sondeo o "invertirla". El Meta-Aprendiz opera sobre dos acciones: $F$ (seguir) e $I$ (invertir). Actualiza sus pesos basándose en las pérdidas incurridas por estas dos acciones hipotéticas en las rondas de sondeo. Esto permite que el algoritmo confíe adaptativamente en el sondeo cuando es informativo ($\delta$ alejado de $1/2$) e lo ignore cuando no lo es.

3. Descomposición del Arrepentimiento:
   El análisis del arrepentimiento descompone la pérdida total en dos componentes:

   • Rondas sin sondeo: El algoritmo sigue la actualización estándar de CEW. El arrepentimiento se acota utilizando un análisis de segundo orden (siguiendo a de Rooij et al., 2014) que relaciona el arrepentimiento base con la varianza acumulada $V_T = \sum v_t$.
   • Rondas de sondeo: La pérdida se acota por la pérdida de la mejor de las dos acciones del Meta-Aprendiz ($F$ o $I$), más un término de arrepentimiento para el propio Meta-Aprendiz. El análisis muestra que la "mejor" acción logra una reducción de pérdida proporcional a $|1-2\delta|v_t$.

Resultados Clave
El artículo establece que un presupuesto sublineal de sondeos por pares ruidosos puede mejorar demostrablemente el arrepentimiento en el peor de los casos en el régimen de retroalimentación completa de OCO.

• Pérdidas Convexas Generales: Para pérdidas convexas generales acotadas en $[0, 1]$ sobre un conjunto convexo $K$, el arrepentimiento esperado es:
  $$\text{Reg}_T \le O\left( \min\left\{ \sqrt{dT \ln T}, \frac{dT \ln T}{k |1 - 2\delta|} \right\} \right)$$
  Este límite es ajustado (salvo por factores logarítmicos en $T$) con respecto al horizonte $T$, el presupuesto de sondeo $k$ y el parámetro de ruido $\delta$. El arrepentimiento se degrada suavemente a medida que $\delta \to 1/2$ (lanzamiento de moneda).

• Predicción con Expertos: En el caso especial del entorno de expertos (pérdidas lineales sobre los vértices del simplex $\Delta^{d-1}$), el límite mejora a:
  $$\text{Reg}_T \le O\left( \min\left\{ \sqrt{T \ln d}, \frac{T \ln d}{k |1 - 2\delta|} \right\} \right)$$
  Estas tasas son completamente ajustadas en todos los parámetros, incluyendo la dimensión $d$.

Significancia y Contribuciones
Los autores afirman varias contribuciones significativas:

1. Unificación: El trabajo unifica el modelo discreto de sondeo de "mejor experto" y el modelo continuo de "comparación por pares", demostrando que los sondeos por pares son tan informativos como los sondeos de mejor experto para lograr tasas de arrepentimiento óptimas.
2. Robustez al Ruido: A diferencia de trabajos anteriores que a menudo asumen modelos de ruido sin ruido o específicos, este marco maneja niveles de ruido desconocidos $\delta$ y logra una dependencia óptima en $|1-2\delta|$.
3. Novedad Técnica: El análisis evita la maquinaria de privacidad diferencial y las suposiciones sobre las normas de los gradientes o la curvatura (que eran requeridas en trabajos previos como Bhaskara et al., 2023b). En su lugar, aprovecha un argumento de reducción basado en la varianza.
4. Optimalidad: El artículo proporciona límites inferiores coincidentes (en el Apéndice A) que muestran que las tasas derivadas son ajustadas para el entorno de expertos y ajustadas en $T, k, \delta$ para conjuntos convexos generales.

Los autores señalan que, si bien las garantías teóricas son sólidas, el algoritmo principal requiere calcular integrales sobre conjuntos convexos, lo cual puede ser computacionalmente difícil en general. Identifican el desarrollo de algoritmos eficientes que alcancen garantías comparables como una dirección abierta de investigación.