High-probability zeroth-order online convex optimisation beyond Euclidean geometry

Resumen Técnico: Optimización convexa en línea de orden cero de alta probabilidad más allá de la geometría euclidiana

Configuración del Problema
Este trabajo aborda el problema de la optimización convexa en línea (OCO) en un entorno de orden cero donde el aprendiz solo tiene acceso a evaluaciones de funciones, no a gradientes. La configuración específica implica una secuencia de pérdidas aleatorias Lipschitz $f_t$ extraídas de una distribución $\mu$. Si bien las realizaciones $f_t$ no necesitan ser convexas, se asume que su función media $F_\mu(x) = \mathbb{E}_{f \sim \mu}[f(x)]$ es convexa. El aprendiz opera sobre un conjunto compacto y convexo $\Theta \subset \mathbb{R}^d$ y busca minimizar el pseudo-arrepentimiento:
$$R_n^\mu = \sup_{u \in \Theta} \sum_{t=1}^n \left( F_\mu(x_t) - F_\mu(u) \right)$$
El modelo de retroalimentación permite al aprendiz consultar la función en dos puntos por ronda, $x_t \pm h_t \zeta_t$, donde la dirección $\zeta_t$ se muestrea desde la frontera de una bola $\ell_r$ según la medida de cono. Se asume que las pérdidas son $L$-Lipschitz con respecto a una norma $\ell_q$, y el algoritmo emplea un regularizador fuertemente convexo $\ell_p$ dentro de un marco de Seguir al Líder Regularizado (FTRL).

Metodología
El artículo propone un algoritmo adaptativo y de tiempo arbitrario (SOLO FTRL) que utiliza estimadores de gradiente de diferencias finitas aleatorizadas de dos puntos. Las innovaciones metodológicas centrales residen en la generalización geométrica y el análisis probabilístico:

1. Estimación de Gradiente Generalizada: El estimador de gradiente se construye utilizando direcciones muestreadas desde la medida de cono en la frontera de una bola $\ell_r$ ($\zeta \sim \partial B_d^r$). El estimador se define como:
   $$g_t = \frac{d}{2h_t} \left( f_t(x_t + h_t \zeta_t) - f_t(x_t - h_t \zeta_t) \right) n_r(\zeta_t)$$
   donde $n_r(\zeta)$ es el normal unitario a la esfera $\ell_r$ en $\zeta$. Esto generaliza los estimadores esféricos clásicos ($r=2$) y permite geometrías de muestreo $\ell_1$ o $\ell_\infty$.

2. Análisis de Momentos y Concentración: A diferencia de trabajos anteriores que se basan en cotas en esperanza (típicamente utilizando momentos de segundo orden), este análisis establece cotas de todos los momentos para el estimador de gradiente en la norma dual $\ell_{p^*}$. Al demostrar que la secuencia de errores al cuadrado de la norma dual satisface una condición de momento de Bernstein secuencial (SBM), los autores derivan desigualdades de concentración de alta probabilidad uniformes en el tiempo. Esto implica controlar el comportamiento de la cola del estimador de gradiente utilizando resultados de concentración de medida para funciones Lipschitz en esferas $\ell_r$.

3. Algoritmo Adaptativo: El algoritmo es completamente impulsado por datos y no requiere conocimiento del horizonte temporal $n$ ni de constantes del peor caso derivadas del análisis de momentos. Solo requiere la especificación de los parámetros geométricos ($p, r$), el regularizador y una cota superior del tamaño del dominio.

Contribuciones Clave

1. Cotas Unificadas de Alta Probabilidad: El artículo proporciona las primeras cotas unificadas de arrepentimiento de alta probabilidad para OCO de orden cero en todas las combinaciones de geometría $p, q, r \in [1, \infty]$. Estas cotas se cumplen para pérdidas Lipschitz aleatorias con una media convexa, fortaleciendo las garantías anteriores en esperanza a declaraciones de alta probabilidad uniformes en el tiempo.
2. Cotas de Momentos del Estimador de Gradiente: Los autores demuestran cotas de momentos novedosas para estimadores de gradiente aleatorizados de dos puntos $\ell_r$ en la norma dual $\ell_{p^*}$. Estos resultados rastrean la dependencia de la geometría de muestreo ($r$) y la norma Lipschitz ($q$), estableciendo que las normas duales acumuladas al cuadrado se comportan como un proceso subgamma.
3. Cotas Inferiores Independientes del Algoritmo: El artículo establece cotas inferiores de probabilidad constante para la misma clase de problemas. Estas cotas mejoran los resultados anteriores en esperanza (específicamente para $p=q=1$ al eliminar un factor $\sqrt{\log d}$) y cubren el rango completo de $p, q \in [1, \infty]$ con una única construcción.
4. Identificación de una Brecha para $q > 2$: El análisis revela una discrepancia entre las cotas superior e inferior cuando $q > 2$. Los autores argumentan que esto no es un artefacto de la prueba, sino que indica una suboptimalidad intrínseca de los estimadores de gradiente aleatorizados de dos puntos estándar en este régimen, ya que no logran explotar la dispersión inherente a las funciones Lipschitz de alto $q$.

Resultados Principales
El resultado teórico principal (Teorema 2.3) establece que con probabilidad al menos $1-\delta$, el arrepentimiento satisface:
$$R_n^\mu \leq 22R\sqrt{\nu_r} \left( \sqrt{n \Lambda_n^*(\delta)} + 11 d^{\gamma_r} \log(32n/\delta)^{3/2} \right)$$
donde $\nu_r$ es una varianza proxy que depende de $L, d, p, q, r$, y $\gamma_r = (1/p - 1/r)_+$. El término $\sqrt{\log \log n}$ surge de la naturaleza de tiempo arbitrario de la cota.

La cota inferior (Teorema 2.4) muestra que para cualquier algoritmo de dos puntos, existe una instancia del problema donde el arrepentimiento es al menos del orden $d^{(1/2 + 1/q - 1/p)_+} LR\sqrt{n}$ con probabilidad constante.

Significado y Afirmaciones
El artículo afirma proporcionar el primer tratamiento unificado de la optimización convexa en línea de orden cero más allá del entorno euclidiano ($p=q=r=2$). Al pasar del análisis en esperanza al de alta probabilidad, los resultados ofrecen garantías más fuertes y uniformes en el tiempo, adecuadas para entornos adaptativos y de tiempo arbitrario.

El trabajo destaca una limitación específica en la metodología actual: para $q > 2$, los estimadores de gradiente aleatorizados estándar parecen ser subóptimos en comparación con la cota inferior teórica. Los autores sugieren que la brecha surge porque estos estimadores carecen de un mecanismo para explotar la dispersión de las instancias "difíciles" en el régimen $q > 2$, una propiedad que la construcción de la cota inferior utiliza explícitamente. Este hallazgo sugiere que las mejoras futuras en este régimen podrían requerir estructuras de estimadores fundamentalmente diferentes en lugar de simplemente un análisis refinado de los métodos de diferencias finitas existentes.