Communication-Efficient Federated Online Decision-Making with Stateful Costs

Resumo Técnico: Tomada de Decisão Online Federada Eficiente em Comunicação com Custos Estatais

Formulação do Problema
Este artigo aborda o desafio da tomada de decisão online federada em sistemas onde as decisões impulsionam um estado operacional em evolução, e custos são incorridos com base na trajetória de estado resultante. Diferentemente do aprendizado federado padrão, que otimiza objetivos pontuais, ou do controle online tradicional, que assume informação completa, este cenário envolve um servidor central e $N$ clientes operando sob sincronização esparsa baseada em blocos e participação parcial de clientes.

A dificuldade central surge da interação entre restrições de comunicação e dinâmicas do sistema:

1. Custos Estatais: O custo no tempo $t$, $c_t(\chi_t, u_t)$, depende do estado do sistema $\chi_t$, que evolui de acordo com dinâmicas lineares $\chi_{t+1} = A\chi_t + Bu_t + Ed_t$.
2. Comunicação Esparsa: As decisões são atualizadas apenas nas fronteiras dos blocos (a cada $K$ rodadas). Dentro de um bloco, a decisão $u_t$ é mantida fixa ($u_t = \bar{u}_b$).
3. Incompatibilidade de Trajetória: Como o sistema operacional evolui continuamente enquanto a decisão permanece estática dentro de um bloco, uma decisão desatualizada impulsiona o sistema ao longo de uma trajetória de estado diferente daquela que uma decisão ótima por rodada produziria. Isso altera o custo acumulado incorrido.
4. Arrependimento Dinâmico: O desempenho é medido contra uma sequência comparadora limitada pelo comprimento do caminho $u^\star_{1:T}$ que pode variar a cada rodada (dentro de um orçamento de variação total $V_T$), mas não é restringida pelo protocolo de comunicação esparsa.

O artigo define o arrependimento dinâmico como a diferença entre o custo acumulado incorrido pela trajetória realizada pelo algoritmo online e o custo acumulado mínimo alcançável por qualquer sequência comparadora admissível em retrospecto.

Metodologia: BLADE
Os autores propõem o BLADE (Aproximação Local em Blocos para Execução Dinâmica), um método projetado de tomada de decisão online federada em blocos. O algoritmo opera da seguinte forma:

• Atualizações Baseadas em Blocos: O horizonte é dividido em blocos de comprimento $K$. O servidor mantém uma iteração de bloco $\bar{u}_b$ implantada para todas as rodadas no bloco.
• Surrogados de Memória Finita: Para lidar com a natureza estatal dos custos sem exigir histórico completo, o BLADE utiliza uma aproximação de memória finita do estado. Ele define um "estado surrogado diagonal" $\bar{\chi}_t(u)$ onde todas as ações dentro de uma janela de memória $H$ são assumidas como sendo a decisão candidata atual $u$.
• Decomposição Local: O custo do surrogado diagonal é assumido como admitindo uma forma localmente decomponível, $c_t(\bar{\chi}_t(u), u) = \frac{1}{N}\sum c_{i,t}(u)$, permitindo que os clientes computem gradientes locais.
• Participação Parcial: No final de cada bloco, um subconjunto de $m$ clientes é amostrado para computar e retornar a soma dos gradientes sobre o bloco. O servidor atualiza a próxima iteração de bloco via um passo de gradiente projetado:
  $$\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)$$

Principais Contribuições

1. Formulação do Problema: O artigo formula um novo problema de decisão online federada onde a comunicação esparsa afeta não apenas o erro de otimização, mas a trajetória de estado realizada e os custos incorridos resultantes.
2. Design do Algoritmo: Introduz o BLADE, que integra sincronização em blocos, aproximação de estado de memória finita e participação parcial de clientes em um framework unificado para custos estatais.
3. Análise Teórica: Os autores derivam um limite de arrependimento dinâmico para o custo incorrido (não apenas uma perda surrogada). O limite separa explicitamente as fontes de erro:
   • Erro de otimização a partir do descenso online projetado.
   • Erro de amostragem a partir da participação parcial.
   • Erro de incompatibilidade de trajetória a partir da manutenção de decisões fixas dentro dos blocos.
   • Erro de truncamento de memória finita.
4. Garantias de Arrependimento: Sob o cenário $K = \lceil \sqrt{T} \rceil$, o artigo prova que o arrependimento dinâmico esperado é sublinear em $T$, desde que a variação da comparadora $V_T = o(T^{1/4})$. A complexidade de comunicação é mostrada como $O(\sqrt{T})$.

Resultados e Validação
Os limites teóricos são validados através de experimentos em um sistema linear estável sintético controlado. Os experimentos isolam os mecanismos previstos pela teoria:

• Compensação Comunicação-Arrependimento: O aumento do comprimento do bloco $K$ reduz os escalares de comunicação, mas aumenta o arrependimento dinâmico, confirmando a compensação teórica.
• Comprimento da Memória: O aumento da janela de memória $H$ reduz o arrependimento até que o erro de truncamento se torne negligenciável, consistente com o decaimento geométrico das dinâmicas do sistema.
• Participação Parcial: Razões de participação mais baixas ($m/N$) aumentam o arrependimento devido a maior ruído de amostragem.
• Variação de Perturbação: Maior variação em perturbações externas leva a um arrependimento incorrido maior, conforme esperado para uma referência dinâmica.
• Escala do Horizonte: O custo de comunicação escala como $O(\sqrt{T})$ quando $K = \lceil \sqrt{T} \rceil$, correspondendo à previsão teórica.

Significado e Alegações
O artigo alega que o trabalho existente em aprendizado federado eficiente em comunicação tipicamente foca em objetivos pontuais, enquanto a literatura de arrependimento dinâmico frequentemente ignora restrições de comunicação ou geração de custos estatais. O BLADE aborda a lacuna onde a comunicação esparsa altera fundamentalmente a trajetória de estado do sistema.

Os autores enfatizam que a dificuldade não é meramente uma combinação de questões existentes; a decisão "mantida em bloco" cria uma distorção de custo ao nível da trajetória e uma lacuna de alinhamento de bloco contra a comparadora dinâmica. Ao isolar esses efeitos, o BLADE fornece um proxy tratável (o surrogado diagonal) para controlar o arrependimento dinâmico ao nível do sistema. O trabalho demonstra que o arrependimento dinâmico sublinear é alcançável mesmo quando o aprendiz online é restringido por comunicação esparsa e deve agir em um sistema com memória, desde que a deriva do ambiente ($V_T$) não seja muito rápida.