Communication-Efficient Federated Online Decision-Making with Stateful Costs

Resumen Técnico: Toma de Decisiones en Línea Federada Eficiente en Comunicación con Costos con Estado

Formulación del Problema
Este artículo aborda el desafío de la toma de decisiones en línea federada en sistemas donde las decisiones impulsan un estado operativo en evolución, y se incurren costos basados en la trayectoria resultante del estado. A diferencia del aprendizaje federado estándar, que optimiza objetivos puntuales, o del control en línea tradicional, que asume información completa, este escenario involucra un servidor central y $N$ clientes operando bajo sincronización dispersa basada en bloques y participación parcial de clientes.

La dificultad central surge de la interacción entre las restricciones de comunicación y la dinámica del sistema:

1. Costos con Estado: El costo en el tiempo $t$, $c_t(\chi_t, u_t)$, depende del estado del sistema $\chi_t$, que evoluciona según dinámicas lineales $\chi_{t+1} = A\chi_t + Bu_t + Ed_t$.
2. Comunicación Dispersa: Las decisiones se actualizan solo en los límites de los bloques (cada $K$ rondas). Dentro de un bloque, la decisión $u_t$ se mantiene fija ($u_t = \bar{u}_b$).
3. Discrepancia de Trayectoria: Dado que el sistema operativo evoluciona continuamente mientras la decisión permanece estática dentro de un bloque, una decisión obsoleta impulsa al sistema a lo largo de una trayectoria de estado diferente a la que seguiría una decisión óptima por ronda. Esto altera el costo acumulado incurrido.
4. Arrepentimiento Dinámico: El rendimiento se mide frente a una secuencia de comparadores acotada por la longitud del camino $u^\star_{1:T}$ que puede variar en cada ronda (dentro de un presupuesto de variación total $V_T$) pero no está restringida por el protocolo de comunicación dispersa.

El artículo define el arrepentimiento dinámico como la diferencia entre el costo acumulado incurrido por la trayectoria realizada del algoritmo en línea y el costo acumulado mínimo alcanzable por cualquier secuencia de comparadores admisible a posteriori.

Metodología: BLADE
Los autores proponen BLADE (Aproximación Local por Bloques para Ejecución Dinámica), un método de toma de decisiones en línea federada proyectado por bloques. El algoritmo opera de la siguiente manera:

• Actualizaciones Basadas en Bloques: El horizonte se divide en bloques de longitud $K$. El servidor mantiene una iteración de bloque $\bar{u}_b$ desplegada para todas las rondas en el bloque.
• Surrogados de Memoria Finita: Para manejar la naturaleza con estado de los costos sin requerir el historial completo, BLADE utiliza una aproximación de memoria finita del estado. Define un "estado surrogado diagonal" $\bar{\chi}_t(u)$ donde todas las acciones dentro de una ventana de memoria $H$ se asumen iguales a la decisión candidata actual $u$.
• Descomposición Local: Se asume que el costo surrogado diagonal admite una forma localmente descomponible, $c_t(\bar{\chi}_t(u), u) = \frac{1}{N}\sum c_{i,t}(u)$, lo que permite a los clientes calcular gradientes locales.
• Participación Parcial: Al final de cada bloque, se muestrea un subconjunto de $m$ clientes para calcular y devolver la suma de los gradientes sobre el bloque. El servidor actualiza la siguiente iteración de bloque mediante un paso de gradiente proyectado:
  $$\bar{u}_{b+1} = \Pi_Z \left( \bar{u}_b - \eta_B \frac{1}{m} \sum_{i \in S_b} \sum_{t \in I_b} \nabla c_{i,t}(\bar{u}_b) \right)$$

Contribuciones Clave

1. Formulación del Problema: El artículo formula un nuevo problema de toma de decisiones en línea federada donde la comunicación dispersa afecta no solo al error de optimización, sino a la trayectoria de estado realizada y a los costos incurridos resultantes.
2. Diseño del Algoritmo: Introduce BLADE, que integra la sincronización por bloques, la aproximación de estado de memoria finita y la participación parcial de clientes en un marco unificado para costos con estado.
3. Análisis Teórico: Los autores derivan un límite de arrepentimiento dinámico para el costo incurrido (no solo una pérdida surrogada). El límite separa explícitamente las fuentes de error:
   • Error de optimización por descenso en línea proyectado.
   • Error de muestreo por participación parcial.
   • Error de discrepancia de trayectoria por mantener las decisiones fijas dentro de los bloques.
   • Error de truncamiento de memoria finita.
4. Garantías de Arrepentimiento: Bajo el ajuste $K = \lceil \sqrt{T} \rceil$, el artículo demuestra que el arrepentimiento dinámico esperado es sublineal en $T$, siempre que la variación del comparador $V_T = o(T^{1/4})$. Se muestra que la complejidad de comunicación es $O(\sqrt{T})$.

Resultados y Validación
Los límites teóricos se validan mediante experimentos en un sistema lineal estable sintético controlado. Los experimentos aíslan los mecanismos predichos por la teoría:

• Compensación Comunicación-Arrepentimiento: Aumentar la longitud del bloque $K$ reduce los escalares de comunicación pero aumenta el arrepentimiento dinámico, confirmando la compensación teórica.
• Longitud de Memoria: Aumentar la ventana de memoria $H$ reduce el arrepentimiento hasta que el error de truncamiento se vuelve despreciable, consistente con la descomposición geométrica de las dinámicas del sistema.
• Participación Parcial: Las ratios de participación más bajas ($m/N$) aumentan el arrepentimiento debido al mayor ruido de muestreo.
• Variación de Perturbaciones: Una mayor variación en las perturbaciones externas conduce a un mayor arrepentimiento incurrido, como se espera para un punto de referencia dinámico.
• Escalado del Horizonte: El costo de comunicación escala como $O(\sqrt{T})$ cuando $K = \lceil \sqrt{T} \rceil$, coincidiendo con la predicción teórica.

Significado y Afirmaciones
El artículo afirma que el trabajo existente en aprendizaje federado eficiente en comunicación se centra típicamente en objetivos puntuales, mientras que la literatura sobre arrepentimiento dinámico a menudo ignora las restricciones de comunicación o la generación de costos con estado. BLADE aborda la brecha donde la comunicación dispersa altera fundamentalmente la trayectoria de estado del sistema.

Los autores enfatizan que la dificultad no es meramente una combinación de problemas existentes; la decisión "mantenida en bloque" crea una distorsión de costos a nivel de trayectoria y una brecha de alineación de bloques frente al comparador dinámico. Al aislar estos efectos, BLADE proporciona un proxy tratable (el surrogado diagonal) para controlar el arrepentimiento dinámico a nivel de sistema. El trabajo demuestra que el arrepentimiento dinámico sublineal es alcanzable incluso cuando el aprendiz en línea está restringido por comunicación dispersa y debe actuar sobre un sistema con memoria, siempre que la deriva del entorno ($V_T$) no sea demasiado rápida.