Data-Driven Distributed Optimization via Aggregative Tracking and Deep-Learning

Resumen Técnico: Optimización Distribuida Basada en Datos mediante Seguimiento Agregativo y Aprendizaje Profundo (DELTA)

Formulación del Problema
El artículo aborda el desafío de la optimización distribuida en un marco agregativo donde una red de $N$ agentes minimiza cooperativamente la suma de sus funciones de costo locales. A diferencia de la optimización distribuida estándar, el costo local $f_i$ de cada agente depende no solo de su propia variable de decisión $x_i$, sino también de una variable agregativa global $\sigma(x)$, definida como el promedio de las contribuciones locales $\phi_i(x_i)$.

El escenario específico considerado es basado en datos y desconocido:

1. Las funciones $f_i$ son completamente desconocidas para los agentes.
2. Los agentes solo pueden obtener una única muestra de retroalimentación de su costo local por iteración (una evaluación de "1 punto") en un punto elegido $(u_{x,i}, u_{\sigma,i})$.
3. Las cantidades globales (la variable agregativa $\sigma(x)$ y la derivada del costo global con respecto a esta) no están disponibles localmente.

Esta configuración está motivada por aplicaciones en robótica cooperativa y optimización personalizada, donde las funciones de costo pueden representar la insatisfacción del usuario o restricciones físicas que son difíciles de modelar analíticamente, pero que pueden muestrearse mediante sensores o la retroalimentación de un usuario.

Metodología: El Algoritmo DELTA
Los autores proponen DELTA (DEep-Learning aggregative TrAcking), un algoritmo distribuido que opera en una única escala de tiempo e integra tres componentes concurrentes:

1. Módulo Orientado al Aprendizaje:

   • Cada agente $i$ emplea una red neuronal (NN) local $\hat{f}_i(\cdot, \theta_i)$ para aproximar la función de costo desconocida $f_i$ y sus gradientes.
   • En lugar de entrenar la red hasta la convergencia entre los pasos de optimización (lo cual es computacionalmente costoso y requiere múltiples muestras), la NN se actualiza mediante un descenso de gradiente de un solo paso utilizando la muestra de costo única obtenida en cada iteración.
   • Para asegurar la excitación persistente para el aprendizaje, el algoritmo inyecta señales de dither ($d_{x,i}, d_{\sigma,i}$) en los puntos de muestreo.
   • La NN aproxima la dirección de descenso, reemplazando efectivamente la necesidad de conocimiento explícito del gradiente.

2. Rutina Orientada a la Optimización:

   • Los agentes realizan una actualización de tipo gradiente distribuido utilizando los gradientes aproximados proporcionados por sus NNs locales.
   • La regla de actualización combina el estimador del gradiente local $\nabla_1 \hat{f}_i$ con un término que involucra la derivada de la función de agregación $\nabla \phi_i$ y el componente del gradiente global estimado.

3. Mecanismo Orientado al Seguimiento:

   • Dado que las cantidades globales $\sigma(x)$ y la suma de las derivadas de los gradientes locales no están disponibles, los agentes mantienen variables auxiliares ($w_i$ y $z_i$).
   • Estas variables se actualizan mediante una dinámica de consenso perturbada (usando una matriz de adyacencia doblemente estocástica) para reconstruir localmente la variable agregativa global faltante y el componente del gradiente global.

Análisis Teórico y Resultados
La estabilidad y convergencia de DELTA se analizan utilizando herramientas de la teoría de sistemas, específicamente la separación de escalas temporales y la teoría de promedios en tiempo discreto. El análisis trata al algoritmo como un sistema de dos escalas temporales variables, separando la dinámica rápida (seguimiento y aprendizaje) de la dinámica lenta (optimización).

• Garantía de Convergencia: Bajo supuestos de fuerte convexidad para el costo global y continuidad de Lipschitz para las funciones y sus aproximaciones, los autores demuestran que el algoritmo converge linealmente a un entorno de la solución óptima $x^*$.
• Cota de Error: El radio de este entorno depende explícitamente del parámetro $\epsilon$, que representa el error máximo de reconstrucción de las redes neuronales (es decir, la precisión de la aproximación de la NN en la convergencia).
• Caso Ideal: En el límite teórico donde las redes neuronales logran una estimación perfecta ($\epsilon = 0$), el algoritmo converge exactamente a la solución óptima.
• Robustez: El diseño permite que el algoritmo se adapte a funciones de costo variables en el tiempo o perturbaciones sin requerir un reinicio completo de los procesos de entrenamiento o seguimiento.

Contribuciones Clave

1. Integración Novedosa: El artículo introduce un esquema novedoso que combina el aprendizaje por redes neuronales con la optimación agregativa distribuida y el seguimiento de gradiente, diseñado específicamente para escenarios con solo evaluaciones de costo de un único punto.
2. Superación de las Limitaciones de 1 Punto: Los métodos estándar de orden cero de 1 punto suelen sufrir de tasas de convergencia deficientes o alta varianza. DELTA aborda esto mediante la implementación de una estrategia de aprendizaje dinámica (NNs) que aprende la dirección de descenso a lo largo del tiempo sin aumentar el número de evaluaciones de costo por iteración.
3. Prueba de Convergencia Rigurosa: Los autores proporcionan una prueba formal de convergencia lineal en un entorno del óptimo, caracterizando explícitamente el compromiso entre la precisión de la aproximación de la red neuronal y el error de optimización final.
4. Gestión de Entornos Desconocidos: El marco está diseñado para funciones de costo completamente desconocidas, distinguiéndose de trabajos previos donde partes de la función de costo eran conocidas o donde se requerían múltiples muestras por iteración.

Significado y Reivindicaciones
El artículo afirma que DELTA ofrece una solución práctica para la optimización personalizada y el control cooperativo en entornos desconocidos o no estacionarios (por ejemplo, la colaboración humano-robot). Al aprovechar la sinergia entre el aprendizaje, la optimización y el seguimiento, el algoritmo se adapta a los cambios en las funciones de costo de forma dinámica.

Los autores señalan que, si bien existía una versión preliminar de este trabajo para entornos de tiempo variable con múltiples muestras y entrenamiento completo de NN, la contribución actual es técnicamente más exigente: opera con muestras únicas por iteración y entrenamiento de NN de un solo paso, lo que requiere una integración más compleja del análisis de la dinámica de aprendizaje con la optimización y la dinámica de consenso. Simulaciones numéricas en una red de 20 agentes validan los resultados teóricos, demostando la convergencia al entorno óptimo y la robustez ante cambios repentinos en las funciones de costo locales.