Geometry-Aware Decentralized Sinkhorn for Wasserstein Barycenters

Resumo Técnico: Sinkhorn Descentralizado Consciente de Geometria para Baricentros de Wasserstein

1. Declaração do Problema

Sistemas distribuídos frequentemente enfrentam o desafio de fundir distribuições de probabilidade locais heterogêneas em um resumo global sobre redes de comunicação esparsas e não confiáveis. Algoritmos de consenso tradicionais tipicamente tratam distribuições como vetores euclidianos e calculam médias aritméticas. Os autores argumentam que essa abordagem ignora a estrutura geométrica inerente dos espaços de probabilidade, potencialmente levando a resultados enganosos (por exemplo, a média de duas distribuições com suporte em locais opostos produz um ponto médio que pode ser um local impossível).

Enquanto baricentros de Wasserstein oferecem uma alternativa consciente de geometria ao minimizar custos de transporte ótimo, seu cálculo padrão via o algoritmo Sinkhorn depende de uma etapa de média geométrica centralizada. Abordagens descentralizadas existentes ou mantêm um coordenador, trocam informações duais densas através de rotinas de otimização gerais, ou falham em descentralizar diretamente a etapa específica de média geométrica do Sinkhorn. O artigo aborda a necessidade de um método totalmente descentralizado e eficiente em largura de banda que preserve as propriedades geométricas do baricentro sem um coordenador central.

2. Metodologia

A solução proposta é um algoritmo Sinkhorn totalmente descentralizado que reformula a média geométrica centralizada como uma média aritmética no domínio logarítmico. A metodologia procede através de três mecanismos centrais:

• Reformulação no Domínio Logarítmico: A atualização padrão do Sinkhorn para o vetor de escala compartilhado $v$ envolve uma média geométrica de termos locais $K^\top u_i$. Ao definir uma mensagem logarítmica $s_i = \log(K^\top u_i)$, a média geométrica torna-se uma média aritmética: $\log v = \frac{1}{N} \sum s_i$. Essa transformação permite que a etapa de agregação global seja substituída por uma média local.
• Fofoca Descentralizada (Gossip): Agentes aproximam a média aritmética global de mensagens logarítmicas através de protocolos de fofoca ponderados. Cada agente mantém uma estimativa local $z_i$ e atualiza-a usando os pacotes mais recentes dos vizinhos. Isso intercala atualizações de escala local (calculando $u_i$) com fases de consenso para imitar as iterações centralizadas.
• Otimização de Largura de Banda: Para abordar restrições de comunicação, o algoritmo integra:
  • Transmissão Acionada por Evento: Agentes transmitem mensagens apenas quando a mudança em sua mensagem logarítmica excede um limiar $\delta$ ($\|s_i - s_{i, last}\|_\infty > \delta$).
  • Quantização e Recorte: Mensagens são recortadas para um intervalo finito $[s_{min}, s_{max}]$ e quantizadas para $b$ bits antes da transmissão. Cálculos locais mantêm precisão total, enquanto apenas os pacotes transmitidos são quantizados.
  • Assincronia e Perda de Pacotes: O protocolo é projetado para acomodar atualizações assíncronas e perda de pacotes, reutilizando pacotes em cache até que novos cheguem.

3. Contribuições Principais

O artigo reivindica três contribuições primárias:

1. Algorítmica: Um algoritmo Sinkhorn totalmente descentralizado que elimina a coordenação central reformulando médias geométricas como consenso aritmético distribuído no espaço logarítmico.
2. Comunicação: O desenho de protocolos acionados por evento e quantizados que reduzem o uso de largura de banda em ordens de magnitude enquanto preservam garantias de convergência.
3. Teórica: Uma prova de convergência para uma vizinhança do baricentro entrópico centralizado. A análise estabelece que o viés (erro) é linearmente dependente da tolerância de consenso ($\tau$), do limiar de acionamento ($\delta$) e do erro de quantização ($\Delta_q$). A taxa de convergência é mostrada como linear (geométrica) com um fator dependente do parâmetro de regularização entrópica $\varepsilon$.

4. Resultados

Os autores avaliaram o algoritmo em uma rede de grade 4x4 ($N=16$) com um tamanho de suporte de $d=64$.

• Precisão: Simulações demonstram que as iterações descentralizadas permanecem em uma pequena vizinhança $\ell_1$ da solução centralizada. O baricentro descentralizado é visualmente indistinguível do centralizado sobre modos dominantes.
• Comportamento de Convergência: O consenso do loop interno exibe o perfil de dente de serra esperado (contração rápida seguida por pequenos saltos em atualizações externas). O acionamento por evento introduz perturbações limitadas, mas não altera o regime de contração.
• Complexidade: A contagem total de mensagens escala quase linearmente ($O(N)$) com o tamanho da rede em grafos de grade, superando significativamente as bases de escala quadrática ($O(N^2)$). O tempo de execução aumenta monotonicamente com o tamanho da rede, conforme previsto pela análise de custo por iteração.
• Compensações: Os resultados confirmam que o algoritmo alcança precisão quase centralizada com significativamente menos mensagens através de várias topologias e condições.

5. Significado e Reivindicações

O artigo posiciona seu trabalho como uma solução para a limitação fundamental da média euclidiana na fusão de probabilidade distribuída. Ao aproveitar a identidade do domínio logarítmico, os autores reivindicam ter implementado com sucesso a etapa de média geométrica do Sinkhorn como uma média logarítmica ponto a ponto, uma capacidade não alcançada anteriormente em configurações descentralizadas sem um coordenador.

O significado reside no controle explícito de compensações: o método fornece parâmetros ajustáveis (limiares de acionamento, bits de quantização) para equilibrar precisão contra custos de comunicação, tornando-o adequado para redes com links esparsos e não confiáveis. Garantias teóricas asseguram que o desvio da solução centralizada ótima é limitado e previsível com base nos parâmetros do sistema. Os autores concluem que essa abordagem permite a média consciente de geometria em sistemas distribuídos (como robôs autônomos ou redes de sensores) sem a necessidade de compartilhamento de dados brutos ou infraestrutura central, mantendo robustez à assincronia e perda de pacotes.