Resumen Técnico: Descenso de Coordenadas Coherente para Optimización de Orden Cero Ligera

Enunciado del Problema

La optimización de Orden Cero (ZO) es esencial para escenarios donde la retropropagación no está disponible o es computacionalmente prohibitiva, como el aprendizaje en dispositivos con restricciones de memoria, ataques adversarios de caja negra y aprendizaje por refuerzo basado en simulación. Sin embargo, los métodos ZO existentes enfrentan un compromiso fundamental entre la eficiencia de muestras y la varianza:

• Diferencias Finitas Estándar (FD): Proporcionan estimaciones de gradiente de baja varianza pero son ineficientes en muestras, requiriendo $O(d)$ evaluaciones de función por paso para $d$ parámetros.
• Métodos Aleatorizados (p. ej., Estrategias Evolutivas, SPSA, Subespacio Aleatorio): Reducen los costos de consultas por paso pero introducen una alta varianza, a menudo necesitando tasas de aprendizaje pequeñas o tamaños de lote grandes que obstaculizan la convergencia en tiempo real.

Los enfoques actuales suelen depender de descartar los gradientes "obsoletos" (calculados en iteraciones anteriores) como retrasos perjudiciales y asumen que los tamaños de paso de diferencias finitas ($\epsilon$) deben minimizarse para aproximar con precisión los gradientes verdaderos. Este trabajo desafía estas suposiciones.

Metodología: Descenso de Coordenadas Coherente (CoCD)

Los autores proponen el Descenso de Coordenadas Coherente (CoCD), un optimizador ZO determinista, eficiente en muestras y consciente del presupuesto. CoCD opera sobre dos ideas centrales:

1. Coherencia Temporal: Las trayectorias de optimización exhiben continuidad; los gradientes evolucionan suavemente en el tiempo, acotados por la suavidad Lipschitz de la función. Por lo tanto, los gradientes obsoletos no son meramente ruido, sino que pueden servir como aproximaciones sin costo de la geometría actual ("inicios en caliente").
2. Suavizado Implícito del Paisaje: Contra intuitivamente, tamaños de paso de diferencias finitas más grandes ($\epsilon$) pueden mejorar la estabilidad de la convergencia al suavizar implícitamente el paisaje de optimización, reduciendo la constante de suavidad efectiva ($L_\epsilon$).

Marco Algorítmico

CoCD utiliza un búfer Primero en Entrar, Primero en Salir (FIFO) para mantener una estimación global del gradiente $\hat{g} \in \mathbb{R}^n$.

• Actualizaciones Cíclicas: El algoritmo recorre las coordenadas cíclicamente. En cada paso, realiza $B$ consultas de función (presupuesto de cómputo) para actualizar coordenadas específicas utilizando estimaciones frescas de diferencias finitas.
• Momento y Decaimiento: Se aplica un factor de decaimiento de momento global $\gamma \in [0, 1]$ a todo el búfer antes de las actualizaciones.
  • $\gamma = 1.0$: Preserva todos los gradientes históricos hasta que se renuevan cíclicamente (memoria perfecta).
  • $\gamma = 0.0$: Limpia el búfer en cada paso, recuperando el Descenso de Coordenadas Cíclico por Bloques (BCCD) estándar.
  • $0 < \gamma < 1$: Proporciona una "memoria desvanecida", suprimiendo exponencialmente los gradientes muy antiguos mientras retiene la historia reciente.
• Regla de Actualización: La dirección de actualización se forma mediante la estimación híbrida de gradiente $\hat{g}_t$, escalada por la tasa de aprendizaje $\alpha$: $x_{t+1} = x_t - \alpha \cdot \hat{g}_t$.
• Implementación Eficiente: Para manejar tensores estructurados (p. ej., núcleos de CNN) sin una sobrecarga prohibitiva de copia de memoria, CoCD emplea un mecanismo de aplanamiento virtualizado utilizando un búfer de tensor 1D contiguo y operaciones in-place, manteniendo una huella de memoria estricta de una copia del modelo.

Contribuciones Teóricas

El trabajo proporciona una base teórica rigurosa para CoCD:

1. Equivalencia con BCCD con Inicios en Caliente: Los autores demuestran que CoCD es matemáticamente equivalente al Descenso de Coordenadas Cíclico por Bloques (BCCD) equipado con inicios en caliente de gradientes obsoletos. Esto permite un análisis formal de convergencia.
2. Límites de Error de Aproximación: El trabajo deriva límites de error que muestran que el error de aproximación depende del producto de la constante de suavidad efectiva ($L_\epsilon$) y el tamaño de paso ($\delta$). Crucialmente, demuestra que un $\epsilon$ más grande reduce $L_\epsilon$, suavizando efectivamente el paisaje y permitiendo tamaños de paso más grandes y historias de gradiente más largas sin sacrificar la estabilidad.
3. Garantías de Convergencia: Bajo la condición de Polyak-Łojasiewicz (PŁ) y suposiciones leves, CoCD logra una convergencia lineal comparable a los métodos de primer orden, incluso cuando opera sobre estimaciones de gradientes obsoletos. El análisis muestra que en el caso de presupuesto completo ($B=n$), CoCD recupera la tasa de convergencia del descenso de gradiente estándar.
4. Análisis de Estabilidad: El análisis teórico revela que el momento ($\gamma$) suprime exponencialmente el peso de los gradientes más antiguos, estabilizando el descenso en paisajes no convexos.

Resultados Empíricos

Se realizaron experimentos en arquitecturas MLP, CNN y ResNet (hasta 270k parámetros) en tareas de regresión (SARCOS) y clasificación (MNIST, CIFAR-10).

• Rendimiento vs. BCCD: CoCD supera significativamente al BCCD estándar ($\gamma=0$) tanto en eficiencia de muestras como en precisión final.
  • En CIFAR-10, BCCD no logró escapar del régimen de adivinanza aleatoria (10.13% de precisión), mientras que CoCD alcanzó un 45.08% de precisión.
  • En SARCOS, CoCD redujo la pérdida final de 188.73 (BCCD) a 31.18.
• Estabilidad vs. Métodos Aleatorizados: En comparación con líneas base ZO aleatorizadas como SPSA y ZO-SGD, CoCD exhibió una estabilidad superior. Mientras que los métodos aleatorizados divergieron en la tarea de regresión SARCOS, CoCD se estabilizó.
• Eficiencia: CoCD demostró una velocidad superior en tiempo real, ejecutándose aproximadamente 2 veces más rápido que ZO-SGD (8.1s vs. 15.7s por episodio) al evitar la sobrecarga del muestreo gaussiano denso.
• Sensibilidad a Hiperparámetros:
  • Radio de Suavizado ($\epsilon$): Valores más grandes de $\epsilon$ (p. ej., $\epsilon=1.0$) mejoraron la estabilidad y el rendimiento, validando la hipótesis de suavizado implícito.
  • Momento ($\gamma$): Valores más altos de $\gamma$ aceleraron consistentemente la convergencia y fueron esenciales para la coherencia en configuraciones de alta dimensión.

Significado y Afirmaciones

El trabajo afirma que las actualizaciones deterministas y conscientes de la estructura ofrecen una alternativa superior a la aleatorización para la optimización ZO ligera. Al reformular los gradientes obsoletos como un activo computacional en lugar de una liability, CoCD cierra la brecha entre la eficiencia heurística y el rigor teórico.

Las afirmaciones clave incluyen:

• Eficiencia de Recursos: CoCD logra una complejidad de consultas baja ($O(1)$ por paso) sin la alta varianza inherente a los estimadores aleatorizados, haciéndolo adecuado para dispositivos periféricos con restricciones de memoria.
• Perspectiva Teórica: El trabajo proporciona una justificación teórica contra intuitiva para el uso de tamaños de paso de diferencias finitas más grandes para inducir un suavizado implícito, mejorando la convergencia en paisajes no convexos.
• Impacto Práctico: El método ofrece un camino viable para entrenar modelos en el dispositivo o en escenarios de caja negra donde los gradientes son inaccesibles, superando a los métodos ZO existentes más avanzados en estabilidad y velocidad de convergencia.

Los autores señalan que CoCD es actualmente más efectivo para modelos de escala pequeña a mediana y que el trabajo futuro se centrará en estrategias de escalado (p. ej., paralelización por bloques) para sistemas más grandes.