Riemannian Dueling Optimization

Este trabajo extiende la optimización de duelos a variedades Riemannianas proponiendo los algoritmos RDNGD y RDFW para resolver problemas geodésicamente suaves y convexos, estableciendo sus complejidades teóricas y validando su eficacia mediante experimentos numéricos.

Lo esencial

¡Claro que sí! Imagina que estás intentando encontrar el punto más bajo de un valle enorme y oscuro, pero tienes una regla muy extraña: no puedes ver el terreno, ni puedes medir la altura, ni puedes sentir la pendiente.

Lo único que puedes hacer es preguntar a un "oráculo" (un guía misterioso) una pregunta muy simple: "¿Es más bajo el punto A o el punto B?".

El artículo que me has pasado, titulado "Optimización de Duelo Riemanniano", trata sobre cómo resolver este problema cuando el "terreno" no es plano como una mesa de billar (lo que llamamos espacio euclidiano), sino que es una superficie curva, compleja y retorcida, como la superficie de una esfera, un globo terráqueo o incluso un espacio hiperbólico (como un embudo infinito).

Aquí tienes la explicación sencilla, con analogías de la vida real:

1. El Problema: Navegar en la oscuridad con un mapa curvo

En la vida real, muchas decisiones no ocurren en líneas rectas.

• En robótica: Un brazo robótico se mueve en círculos y giros (como girar una llave).
• En inteligencia artificial: Las recomendaciones de Netflix o Spotify a veces funcionan mejor en espacios curvos (hiperbólicos) que en planos.

El problema es que, en estos mundos curvos, los algoritmos tradicionales fallan porque asumen que el mundo es plano. Además, en muchos casos (como cuando un humano evalúa dos imágenes o dos trayectorias), no tenemos números exactos, solo tenemos comparaciones: "Esta foto se ve más recta que la otra" o "Este robot se mueve mejor que aquel".

2. La Solución: El "Duelo" (Dueling Optimization)

Los autores proponen un método para navegar por estas superficies curvas usando solo comparaciones. Imagina que eres un ciego en una montaña curva. No puedes medir la altura, pero puedes preguntar: "¿Si doy un paso hacia el norte, es mejor que si doy un paso hacia el sur?".

El algoritmo funciona así:

1. Elige dos puntos cercanos en la curva.
2. Pregunta al oráculo: "¿Cuál es mejor?".
3. Usa esa respuesta para dar un paso en la dirección correcta.

3. Los Dos Nuevos Algoritmos (Los "Guías")

Los autores crearon dos herramientas nuevas para este viaje:

A. RDNGD: El Explorador con Brújula (Descenso de Gradiente Normalizado)

Imagina que tienes una brújula que no te dice "Norte", sino que te dice "¿Hacia dónde debo caminar para bajar?".

• Cómo funciona: El algoritmo toma un pequeño paso aleatorio en dos direcciones opuestas, pregunta al oráculo cuál es mejor, y deduce la dirección general de la bajada.
• La magia: Funciona incluso en superficies curvas (como rodar una pelota sobre un globo).
• Cuándo usarlo: Cuando puedes proyectar tu posición de vuelta al terreno (como si pudieras "pegarte" a la superficie si te caes). Es rápido y eficiente.

B. RDFW: El Navegante sin Proyección (Frank-Wolfe Riemanniano)

A veces, en problemas muy complejos, "proyectar" o corregir tu posición es computacionalmente imposible (como intentar enderezar un nudo de cuerda muy complicado).

• Cómo funciona: En lugar de corregir tu posición, el algoritmo busca un "punto de referencia" en el terreno que sea prometedor y camina directamente hacia él a lo largo de la curva.
• La analogía: Imagina que estás en una colina y no puedes caminar en línea recta porque hay un muro. En lugar de chocar contra el muro, miras hacia un árbol lejano que sabes que está en la dirección correcta y caminas hacia él siguiendo la curva del terreno.
• Ventaja: Es ideal para problemas donde los cálculos de corrección son demasiado pesados.

4. ¿Por qué es importante? (Ejemplos del mundo real)

Los autores probaron sus métodos en situaciones muy prácticas:

• Atacar Redes Neuronales (Hacking ético): Imagina que quieres engañar a una IA para que reconozca un gato como un perro. No tienes acceso al código interno de la IA (no sabes sus "números"), solo puedes mostrarle dos imágenes modificadas y ver cuál la confunde más. El algoritmo encuentra la perturbación perfecta usando solo esas comparaciones.
• Nivelar el Horizonte en Fotos: Si tomas una foto de un paisaje y está torcida, el algoritmo puede rotar la imagen (en un espacio de rotaciones, no en un plano) preguntando: "¿Esta versión se ve más recta que la anterior?" hasta que la línea del horizonte esté perfecta.

5. El Resultado Final

Lo que hacen estos autores es unir dos mundos:

1. La Optimización Riemanniana (navegar en superficies curvas).
2. La Optimización por Duelo (aprender solo con comparaciones).

Antes, si tenías un problema en una superficie curva y solo podías comparar cosas, no tenías buenas herramientas. Ahora, tienen un mapa y una brújula que funcionan perfectamente en esos mundos extraños.

En resumen: Han creado un método para encontrar el "mejor camino" en terrenos curvos y complejos, usando solo la información más básica posible: "¿Esto es mejor que aquello?". Es como aprender a conducir un coche en una montaña nevada y oscura, solo mirando si el camino a la izquierda o a la derecha parece más seguro, sin poder ver el mapa completo.

Resumen técnico

A continuación presento un resumen técnico detallado del artículo "Riemannian Dueling Optimization" (Optimización de Duelo Riemanniano) en español.

1. Problema y Motivación

El artículo aborda un problema fundamental en el aprendizaje automático y la optimización: la optimización de duelos (dueling optimization) en espacios no euclidianos.

• Contexto: En muchas aplicaciones modernas (sistemas de recomendación, robótica, aprendizaje de representaciones), no se tienen acceso a los valores de la función objetivo ni a sus gradientes. La única retroalimentación disponible proviene de un oráculo de comparación (o "duelo"), que indica cuál de dos puntos $x$ e $y$ tiene un valor de función menor (es decir, $Q_f(x, y) = 1$ si $f(x) > f(y)$, y $-1$ en caso contrario).
• Limitación Actual: La literatura existente sobre optimización de duelos se ha centrado casi exclusivamente en espacios euclidianos sin restricciones.
• El Desafío Riemanniano: Muchos problemas reales ocurren naturalmente en variedades Riemannianas (espacios curvos). Ejemplos incluyen:
  • Embeddings hiperbólicos en recomendaciones.
  • Optimización de trayectorias en el grupo ortogonal especial $SO(3)$ en robótica.
  • Matrices de proyección en el variedad de Stiefel.
  • Ataques adversarios a redes neuronales donde las perturbaciones están restringidas a una esfera.
• Objetivo: Desarrollar un marco teórico y algoritmos para resolver problemas de minimización $\min_{x \in X \subseteq M} f(x)$ donde $M$ es una variedad Riemanniana, utilizando únicamente un oráculo de comparación.

2. Metodología

Los autores proponen dos algoritmos principales adaptados al entorno Riemanniano, basados en la estimación de la dirección del gradiente a partir de comparaciones.

A. Estimación del Gradiente en Variedades

Dado que no se conoce el gradiente, se utiliza un estimador basado en perturbaciones aleatorias. Para un punto $x$, se muestrea una dirección aleatoria $u$ en el espacio tangente $T_xM$ y se evalúa la comparación entre los puntos perturbados $Exp_x(\nu u)$ y $Exp_x(-\nu u)$.
El estimador se define como:
$$h_\nu(x) = Q_f(Exp_x(\nu u), Exp_x(-\nu u)) \cdot u$$
El artículo demuestra teóricamente que este estimador, aunque sesgado, está alineado con la dirección del gradiente normalizado con alta probabilidad, aprovechando la suavidad geodésica de la función.

B. Algoritmo 1: Descenso de Gradiente Normalizado de Duelo Riemanniano (RDNGD)

Este algoritmo es una extensión Riemanniana del método de descenso de gradiente normalizado (NGD).

• Mecanismo: En cada iteración, calcula el estimador $h_\nu(x_k)$, actualiza el punto mediante el mapa exponencial en la dirección opuesta y, si es necesario, proyecta de vuelta al conjunto factible $X$.
• Variantes: Se analizan dos estrategias de paso (learning rate): constante y annealing coseno.
• Aplicabilidad: Funciona tanto para problemas no acotados como para problemas convexos acotados donde la proyección es computacionalmente viable.

C. Algoritmo 2: Método de Frank-Wolfe de Duelo Riemanniano (RDFW)

Este algoritmo está diseñado para situaciones donde la proyección es prohibitiva (demasiado costosa computacionalmente).

• Mecanismo: En lugar de proyectar, utiliza un Oráculo de Minimización Lineal (LMO). Resuelve un subproblema lineal en el espacio tangente para encontrar un punto candidato $z_k$ y se mueve a lo largo de la geodésica hacia él.
• Reducción de Varianza: Dado que el subproblema de Frank-Wolfe es muy sensible al ruido en la estimación del gradiente, el algoritmo utiliza un estimador por lotes (batch) promediando múltiples direcciones aleatorias en cada iteración para reducir la varianza.

D. Algoritmo 3: RRDNGD (Versión Recurrente)

Para funciones fuertemente convexas geodésicamente, proponen una versión recurrente que ejecuta RDNGD en fases, reduciendo el sub-óptimo en cada fase para lograr una tasa de convergencia lineal.

3. Contribuciones Clave

1. Primer Marco Teórico: Establecen la primera teoría de optimización de duelos en variedades Riemannianas, llenando una brecha significativa entre la optimización basada en preferencias y la optimización Riemanniana.
2. Algoritmos Propuestos:
   • RDNGD: El primer método de descenso de gradiente normalizado para duelos en variedades.
   • RDFW: El primer algoritmo libre de proyección (projection-free) para optimización de duelos en variedades.
3. Análisis de Complejidad: Establecen límites rigurosos de complejidad de iteraciones y consultas al oráculo (oracle complexity) para diferentes condiciones de la función objetivo:
   • Suavidad geodésica $L$ (no convexa).
   • Convexidad geodésica.
   • Convexidad fuerte geodésica.
4. Mejoras sobre Resultados Euclidianos: Sus análisis refinados superan a los resultados existentes en espacios euclidianos (como los de Saha et al., 2021) al ofrecer constantes más ajustadas y eliminar factores logarítmicos innecesarios en la dependencia de la dimensión.
5. Robustez Geométrica: Sus límites de error son adaptativos a la estructura intrínseca de la variedad (curvatura), en lugar de depender solo de la dimensión del espacio ambiente.

4. Resultados Experimentales

Los autores validan sus algoritmos mediante experimentos numéricos en datos sintéticos y aplicaciones reales:

• Problemas Sintéticos:
  • Maximización del Cociente de Rayleigh: RDNGD logra un rendimiento comparable al descenso de gradiente de orden cero (ZO-RGD) que sí tiene acceso a valores de función, a pesar de usar solo comparaciones.
  • Media de Karcher: Resolución de la media geométrica de matrices definidas positivas (SPD). RDNGD converge con precisión similar a ZO-RGD.
  • Karcher con Restricciones: RDFW demuestra convergencia en problemas con restricciones de intervalo en matrices SPD, un caso donde la proyección es costosa.
• Aplicaciones Reales:
  • Ataque a Redes Neuronales (DNN): En un escenario de caja negra, RDNGD genera ejemplos adversarios en imágenes CIFAR-10. Logra una mayor pérdida adversaria en menos iteraciones y tiempo de CPU que ZO-RGD, demostrando una eficiencia superior en la consulta al oráculo.
  • Nivelación del Horizonte: En visión por computadora, el algoritmo corrige la inclinación de imágenes utilizando comparaciones humanas (o simuladas) sobre matrices de rotación $SO(2)$, logrando alta precisión en pocas iteraciones sin conocer la función de pérdida explícita.

5. Significado e Impacto

Este trabajo es significativo por varias razones:

• Unificación: Unifica la optimización basada en preferencias (común en RL humano y sistemas de recomendación) con la geometría Riemanniana (esencial para datos de alta dimensión y estructuras complejas).
• Viabilidad Práctica: Demuestra que es posible optimizar problemas complejos en variedades curvas incluso cuando solo se dispone de retroalimentación binaria (gana/pierde), lo cual es crucial en escenarios donde los valores de pérdida son inaccesibles o poco fiables.
• Eficiencia: Los algoritmos propuestos, especialmente RDFW, ofrecen soluciones viables para problemas donde las operaciones de proyección son computacionalmente inviables, abriendo la puerta a nuevas aplicaciones en robótica y aprendizaje profundo.

En resumen, el paper establece un nuevo paradigma para la optimización en entornos restringidos y curvos bajo información limitada, proporcionando tanto fundamentos teóricos sólidos como algoritmos prácticos y eficientes.