Un Algoritmo Adaptativo para Optimización Bilevel en Variedades Riemannianas

Información Básica

• ID del Artículo: 2504.06042
• Título: An Adaptive Algorithm for Bilevel Optimization on Riemannian Manifolds
• Autores: Xu Shi, Rufeng Xiao, Rujun Jiang (Facultad de Ciencias de Datos, Universidad de Fudan)
• Clasificación: math.OC (Optimización y Control)
• Conferencia de Publicación: NeurIPS 2025 (39ª Conferencia de Sistemas de Procesamiento de Información Neural)
• Enlace del Artículo: https://arxiv.org/abs/2504.06042

Resumen

Los métodos existentes para resolver problemas de optimización bilevel riemanniana (RBO) requieren conocer previamente información de primer y segundo orden del problema, así como parámetros de curvatura de la variedad riemanniana para determinar tamaños de paso, lo que impone limitaciones prácticas cuando estos parámetros son desconocidos o computacionalmente inviables. Este artículo propone el algoritmo de descenso de hipergradiente riemanniano adaptativo (AdaRHD) para resolver problemas RBO. Según nuestro conocimiento, AdaRHD es el primer método que adopta una estrategia de tamaño de paso completamente adaptativa en RBO, eliminando la necesidad de parámetros específicos del problema. Demostramos que AdaRHD alcanza una complejidad de iteración O(1/ε) para encontrar puntos ε-estacionarios, coincidiendo con la complejidad de métodos no adaptativos existentes. Además, probamos que reemplazar la aplicación exponencial con una aplicación de contracción mantiene el mismo límite de complejidad. Los experimentos demuestran que AdaRHD logra un rendimiento comparable a los métodos no adaptativos existentes mientras exhibe una robustez significativamente mayor.

Antecedentes y Motivación de la Investigación

Contexto del Problema

Los problemas de optimización bilevel tienen aplicaciones generalizadas en aprendizaje automático, incluyendo aprendizaje por refuerzo, meta-aprendizaje, optimización de hiperparámetros y aprendizaje adversarial. La optimización bilevel riemanniana (RBO) es una extensión de la optimización bilevel en variedades riemannianas, cuya forma general es:

$\min_{x \in \mathcal{M}_x} F(x) := f(x, y^*(x))$$\text{s.t. } y^*(x) = \arg\min_{y \in \mathcal{M}_y} g(x,y)$

donde $\mathcal{M}_x, \mathcal{M}_y$ son variedades riemannianas, $f,g$ son funciones suaves, y $g(x,y)$ es geodésicamente fuertemente convexa respecto a $y$.

Limitaciones de Métodos Existentes

1. Dependencia de Parámetros: Los métodos RBO existentes (como RHGD, RieBO, etc.) requieren conocer previamente parámetros de convexidad fuerte, constantes de Lipschitz y parámetros de curvatura para determinar tamaños de paso
2. Restricciones Prácticas: Estos parámetros son frecuentemente difíciles de estimar o tienen costos computacionales prohibitivos en aplicaciones reales
3. Robustez Insuficiente: Las estrategias de tamaño de paso fijo son sensibles a la inicialización y condiciones del problema

Motivación de la Investigación

La motivación central de este artículo es diseñar un algoritmo RBO completamente adaptativo que pueda:

• Funcionar sin conocimiento previo de parámetros específicos del problema
• Ajustar automáticamente tamaños de paso para adaptarse a características del problema
• Mantener complejidad teórica comparable a métodos no adaptativos
• Proporcionar robustez práctica mejorada

Contribuciones Principales

1. Primer Algoritmo RBO Adaptativo: Se propone AdaRHD, el primer algoritmo de optimización bilevel riemanniana que adopta una estrategia de tamaño de paso completamente adaptativa, eliminando la dependencia de convexidad fuerte, constantes de Lipschitz y parámetros de curvatura
2. Coincidencia de Complejidad Teórica: Se demuestra que AdaRHD alcanza complejidad de iteración O(1/ε) para encontrar puntos ε-estacionarios, coincidiendo con la complejidad de métodos no adaptativos existentes
3. Extensión de Aplicación de Contracción: Se prueba que reemplazar la aplicación exponencial con una aplicación de contracción computacionalmente más eficiente mantiene las mismas garantías de complejidad
4. Verificación Experimental: Se valida la efectividad y robustez del algoritmo en múltiples problemas RBO, incluyendo aprendizaje de representación hiperbólica riemanniana y problemas de optimización robusta

Explicación Detallada del Método

Definición de la Tarea

Consideramos el problema de optimización bilevel riemanniana:

• Problema de Nivel Superior: Minimizar $F(x) = f(x, y^*(x))$ en la variedad $\mathcal{M}_x$
• Problema de Nivel Inferior: Para $x$ dado, resolver $y^*(x) = \arg\min_y g(x,y)$ en la variedad $\mathcal{M}_y$
• Restricciones: $g(x,y)$ es geodésicamente fuertemente convexa respecto a $y$, $f$ no requiere convexidad

Técnica Central: Hipergradiente Riemanniano

El hipergradiente riemanniano se define como: $G_F(x) = G_x f(x, y^*(x)) - G^2_{xy}g(x, y^*(x))[H^{-1}_y g(x, y^*(x))[G_y f(x, y^*(x))]]$

Debido a la dificultad de cálculo exacto, se utiliza un hipergradiente riemanniano aproximado: $\hat{G}_F(x, \hat{y}, \hat{v}) = G_x f(x, \hat{y}) - G^2_{xy}g(x, \hat{y})[\hat{v}]$

donde $\hat{y}$ es una solución aproximada del problema de nivel inferior y $\hat{v}$ es una solución aproximada del sistema lineal.

Arquitectura del Algoritmo AdaRHD

Algoritmo 1: Pasos Principales de AdaRHD

1. Resolución del Problema de Nivel Inferior: Utilizando descenso de gradiente adaptativo
   • Actualización de tamaño de paso: $b^2_{k+1} = b^2_k + \|G_y g(x_t, y^k_t)\|^2$
   • Actualización iterativa: $y^{k+1}_t = \text{Exp}_{y^k_t}(-\frac{1}{b_{k+1}} G_y g(x_t, y^k_t))$
2. Resolución del Sistema Lineal: Dos estrategias
   • Descenso de Gradiente: Tamaño de paso adaptativo similar al problema de nivel inferior
   • Gradiente Conjugado: Utilizando método de gradiente conjugado en el espacio tangente
3. Actualización de Nivel Superior: Descenso de hipergradiente adaptativo
   • Actualización de tamaño de paso: $a^2_{t+1} = a^2_t + \|\hat{G}_F(x_t, y^{K_t}_t, v^{N_t}_t)\|^2$
   • Actualización iterativa: $x_{t+1} = \text{Exp}_{x_t}(-\frac{1}{a_{t+1}} \hat{G}_F(x_t, y^{K_t}_t, v^{N_t}_t))$

Puntos de Innovación Técnica

1. Estrategia de Norma de Gradiente Acumulada: Adopta "el recíproco de la norma de gradiente riemanniano acumulada" como tamaño de paso adaptativo, sin necesidad de conocer parámetros del problema
2. Adaptatividad Tricapa: Aplica tamaño de paso adaptativo al nivel superior, nivel inferior y sistema lineal, formando un marco completamente adaptativo
3. Optimización de Aplicación de Contracción: Proporciona una versión que utiliza aplicación de contracción en lugar de aplicación exponencial, reduciendo la complejidad computacional
4. Garantías Teóricas: Análisis de convergencia riguroso que maneja desafíos técnicos introducidos por la estructura geométrica de variedades riemannianas

Configuración Experimental

Conjuntos de Datos y Problemas

1. Problemas Simples de Similitud de Matrices: Optimización en variedades de Stiefel y SPD
   • Escala de datos: n=100 y n=1000
   • Configuración de parámetros: d=50, r=20, λ=0.01
2. Aprendizaje Profundo de Representación Hiperbólica: Conjunto de datos AFEW de reconocimiento de emociones
   • Arquitectura de red SPD de 3 capas
   • 7 categorías de emociones, 1747 muestras de entrenamiento
   • Distribución de clases desbalanceada
3. Problemas de Optimización Robusta:
   • Problema de media de Karcher robusta
   • Problema de estimación de máxima verosimilitud robusta

Métodos de Comparación

• RHGD-20/50: Descenso de hipergradiente riemanniano, con número máximo de iteraciones de nivel inferior de 20/50
• AdaRHD-GD: AdaRHD utilizando descenso de gradiente para resolver el sistema lineal
• AdaRHD-CG: AdaRHD utilizando gradiente conjugado para resolver el sistema lineal

Métricas de Evaluación

• Valor de función objetivo de nivel superior
• Error de estimación de hipergradiente
• Precisión de validación
• Tiempo de convergencia e iteraciones

Resultados Experimentales

Resultados Principales

Experimentos en Problemas Simples:

• AdaRHD exhibe velocidad de convergencia más rápida en ambas escalas de datos
• Error de estimación de hipergradiente más bajo, especialmente AdaRHD-CG
• Ventaja en tiempo computacional, particularmente en problemas a gran escala

Análisis de Robustez:

• AdaRHD exhibe robustez significativa bajo diferentes configuraciones de tamaño de paso inicial
• RHGD falla con tamaños de paso grandes (5, 1, 0.5), mientras que AdaRHD converge establemente
• AdaRHD-CG es el más rápido en alcanzar 85% de precisión de validación

Hallazgos Clave

1. Ventaja de Robustez: AdaRHD es insensible a la selección de tamaño de paso inicial, mientras que RHGD falla completamente con tamaños de paso inapropiados
2. Mejora de Eficiencia: Aunque AdaRHD requiere más iteraciones de nivel externo, la estrategia adaptativa mantiene competitividad en tiempo computacional total
3. Selección de Método: AdaRHD-CG supera a AdaRHD-GD en precisión y robustez, aunque este último converge más rápidamente en etapas iniciales

Análisis Teórico

Resultados de Complejidad

Teorema 3.1: Bajo supuestos estándar, AdaRHD satisface: $\frac{1}{T}\sum_{t=0}^{T-1} \|G_F(x_t)\|^2_{x_t} \leq \frac{C}{T} = O\left(\frac{1}{T}\right)$

Corolario 3.1: Complejidad para alcanzar un punto ε-estacionario:

• Número total de iteraciones: T = O(1/ε)
• Complejidad de gradiente: $G_f = O(1/ε)$, $G_g = O(1/ε^2)$
• Complejidad de producto Hessiano-vector: O(1/ε²) para AdaRHD-GD, Õ(1/ε) para AdaRHD-CG

Desafíos Técnicos

1. Estructura Geométrica: La curvatura de la variedad riemanniana introduce complejidad analítica adicional
2. Desigualdad Triangular Riemanniana: Requiere utilizar desigualdades triangulares específicas de variedades riemannianas en lugar de sus contrapartes euclidianas
3. Análisis de Tamaño de Paso Adaptativo: Las estrategias adaptativas pueden causar comportamiento divergente en etapas iniciales, requiriendo tratamiento teórico riguroso

Trabajo Relacionado

Optimización Bilevel

• Optimización bilevel euclidiana: Métodos AID, ITD, serie de Neumann, gradiente conjugado, etc.
• Métodos adaptativos recientes: D-TFBO, etc.

Optimización Riemanniana

• Métodos clásicos: Descenso de gradiente riemanniano, gradiente conjugado no lineal, gradiente estocástico con varianza reducida, etc.
• Métodos adaptativos: RASA, RAMSGrad, SAM Riemanniano, etc.

Optimización Bilevel Riemanniana

• RieBO/RieSBO: Optimización bilevel riemanniana determinista y estocástica
• RHGD: Marco de descenso de hipergradiente riemanniano
• RF2SA: Método completamente aleatorio de primer orden

Conclusiones y Discusión

Conclusiones Principales

1. AdaRHD es el primer algoritmo de optimización bilevel riemanniana completamente adaptativo, eliminando la dependencia de parámetros específicos del problema
2. Teóricamente alcanza complejidad O(1/ε) idéntica a métodos no adaptativos
3. Los experimentos validan la efectividad del algoritmo y ventajas significativas de robustez

Limitaciones

1. Brecha de Complejidad: Complejidad de gradiente y producto Hessiano-vector superior en 1/ε en comparación con métodos no adaptativos
2. Condiciones de Supuesto: Aún requiere convexidad geodésica fuerte del problema de nivel inferior
3. Bucle Único vs. Bucle Doble: Actualmente solo considera algoritmos de bucle doble

Direcciones Futuras

1. Algoritmos de Bucle Único: Diseñar algoritmos adaptativos de optimización bilevel riemanniana de bucle único
2. Configuración Estocástica: Extender a optimización bilevel riemanniana estocástica
3. Convexidad Débil: Manejar objetivos de nivel inferior geodésicamente convexos (no fuertemente convexos)
4. Optimización de Complejidad: Explorar estrategias adaptativas para eliminar la brecha de 1/ε

Evaluación Profunda

Fortalezas

1. Innovación Teórica: Primera implementación de adaptatividad completa en RBO con análisis teórico riguroso
2. Valor Práctico: Mejora significativa en robustez y facilidad de uso del algoritmo
3. Profundidad Técnica: Manejo exitoso de desafíos técnicos introducidos por geometría riemanniana
4. Experimentación Completa: Verificación exhaustiva en múltiples escenarios de aplicación

Deficiencias

1. Costo de Complejidad: La adaptatividad conlleva costo de complejidad computacional adicional
2. Restricciones de Supuestos: Aún requiere condiciones de supuesto relativamente fuertes
3. Alcance de Aplicación: Principalmente concentrado en variedades riemannianas específicas

Impacto

• Contribución Académica: Proporciona progreso importante en el campo de intersección de optimización riemanniana y optimización bilevel
• Valor Práctico: Proporciona herramientas más robustas para optimización bilevel riemanniana en aplicaciones reales
• Investigación Posterior: Sienta las bases para investigación adicional en optimización riemanniana adaptativa

Escenarios Aplicables

• Meta-aprendizaje riemanniano y búsqueda de arquitectura neural
• Segmentación de imágenes y adaptación de bajo rango
• Estadística robusta y aprendizaje automático geométrico
• Cualquier aplicación que requiera optimización bilevel bajo restricciones de variedad

Este artículo realiza contribuciones importantes en el campo de optimización bilevel riemanniana, implementando por primera vez diseño de algoritmo completamente adaptativo que, mientras mantiene complejidad teórica, mejora significativamente la practicidad y robustez. A pesar de cierto costo de complejidad, su innovación teórica y valor práctico lo convierten en un progreso importante en el campo.