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

Resumo Técnico: Otimização Distribuída Baseada em Dados via Rastreamento Agregativo e Aprendizagem Profunda (DELTA)

Formulação do Problema
O artigo aborda o desafio da otimização distribuída em um arcabouço agregativo onde uma rede de $N$ agentes minimiza cooperativamente a soma de suas funções de custo locais. Diferente da otimização distribuída padrão, o custo local de cada agente $f_i$ depende não apenas de sua própria variável de decisão $x_i$, mas também de uma variável agregativa global $\sigma(x)$, definida como a média das contribuições locais $\phi_i(x_i)$.

O cenário específico considerado é baseado em dados e desconhecido:

1. As funções $f_i$ são inteiramente desconhecidas para os agentes.
2. Os agentes podem obter apenas uma única amostra de feedback de seu custo local por iteração (uma avaliação de "1 ponto") em um ponto escolhido $(u_{x,i}, u_{\sigma,i})$.
3. Quantidades globais (a variável agregativa $\sigma(x)$ e a derivada do custo global em relação a ela) não estão disponíveis localmente.

Esta configuração é motivada por aplicações em robótica cooperativa e otimização personalizada, onde as funções de custo podem representar insatisfação do usuário ou restrições físicas que são difíceis de modelar analiticamente, mas que podem ser amostradas via sensores ou feedback do usuário.

Metodologia: O Algoritmo DELTA
Os autores propõem o DELTA (DEep-Learning aggregative TrAcking), um algoritmo distribuído que opera em uma única escala de tempo e integra três componentes simultâneos:

1. Módulo Orientado ao Aprendizado:

   • Cada agente $i$ emprega uma rede neural (NN) local $\hat{f}_i(\cdot, \theta_i)$ para aproximar a função de custo desconhecida $f_i$ e seus gradientes.
   • Em vez de treinar a rede até a convergência entre os passos de otimização (o que é computacionalmente caro e exige múltiplas amostras), a NN é atualizada via um único passo de descida de gradiente usando a amostra única de custo obtida em cada iteração.
   • Para garantir a excitação persistente para o aprendizado, o algoritmo injeta sinais de dither ($d_{x,i}, d_{\sigma,i}$) nos pontos de amostragem.
   • A NN aproxima a direção de descida, substituindo efetivamente a necessidade de conhecimento explícito do gradiente.

2. Rotina Orientada à Otimização:

   • Os agentes realizam uma atualização do tipo gradiente distribuído usando os gradientes aproximados fornecidos por suas NNs locais.
   • A regra de atualização combina o gradiente local estimado $\nabla_1 \hat{f}_i$ com um termo envolvendo a derivada da função de agregação $\nabla \phi_i$ e a componente de gradiente global estimada.

3. Mecanismo Orientado ao Rastreamento:

   • Como as quantidades globais $\sigma(x)$ e a soma das derivadas dos gradientes locais não estão disponíveis, os agentes mantêm variáveis auxiliares ($w_i$ e $z_i$).
   • Essas variáveis são atualizadas via dinâmica de consenso perturbada (usando uma matriz de adjacência duplamente estocástica) para reconstruir localmente a variável agregativa global ausente e a componente de gradiente global.

Análise Teórica e Resultados
A estabilidade e a convergência do DELTA são analisadas utilizando ferramentas da teoria de sistemas, especificamente separação de escalas de tempo e teoria de média em tempo discreto. A análise trata o algoritmo como um sistema de dois tempos-escala variáveis, separando as dinâmicas rápidas (rastreamento e aprendizado) das dinâmicas lentas (otimização).

• Garantia de Convergência: Sob suposições de convexidade forte para o custo global e continuidade Lipschitz para as funções e suas aproximações, os autores provam que o algoritmo converge linearmente para uma vizinhança da solução ótima $x^*$.
• Limite de Erro: O raio desta vizinhança é explicitamente dependente do parâmetro $\epsilon$, que representa o erro máximo de reconstrução das redes neurais (ou seja, a precisão da aproximação da NN na convergência).
• Caso Ideal: No limite teórico onde as redes neurais alcançam uma estimativa perfeita ($\epsilon = 0$), o algoritmo converge exatamente para a solução ótima.
• Robustez: O design permite que o algoritmo se adapte a funções de custo variantes no tempo ou perturbações sem exigir um reinício completo dos processos de treinamento ou rastreamento.

Principais Contribuições

1. Integração Inovadora: O artigo introduz um esquema inovador que combina aprendizado por redes neurais com otimização agregativa distribuída e rastreamento de gradiente, especificamente adaptado para cenários com apenas avaliações de custo de ponto único.
2. Superação das Limitações de 1 Ponto: Métodos de 1 ponto de ordem zero padrão frequentemente sofrem de taxas de convergência ruins ou alta variância. O DELTA aborda isso incorporando uma estratégia de aprendizado dinâmica (NNs) que aprende a direção de descida ao longo do tempo sem aumentar o número de avaliações de custo por iteração.
3. Prova de Convergência Rigorosa: Os autores fornecem uma prova formal de convergência linear em uma vizinhança do ótimo, caracterizando explicitamente o compromisso entre a precisão da aproximação da rede neural e o erro final de otimização.
4. Lidando com Ambientes Desconhecidos: O arcabouço é projetado para funções de custo completamente desconhecidas, distinguindo-se de trabalhos anteriores onde partes da função de custo eram conhecidas ou onde múltiplas amostras eram necessárias por iteração.

Significância e Alegações
O artigo afirma que o DELTA oferece uma solução prática para a otimização personalizada e o controle cooperativo em ambientes desconhecidos ou não estacionários (ex: colaboração humano-robô). Ao alavancar a sinergia entre aprendizado, otimização e rastreamento, o algoritmo se adapta a mudanças nas funções de custo dinamicamente.

Os autores observam que, embora uma versão preliminar deste trabalho existisse para configurações variantes no tempo com múltiplas amostras e treinamento total de NN, a contribuição atual é tecnicamente mais exigente: opera com amostras únicas por iteração e treinamento de NN de passo único, exigوindo uma integração mais complexa da análise de dinâmica de aprendizado com dinâmica de otimização e consenso. Simulações numéricas em uma rede de 20 agentes validam os resultados teóricos, demonstrando convergência para a vizinhança ótima e robustez a mudanças súbitas nas funções de custo locais.