Stable and Budget-Feasible Coalition Formation for Clustered Federated Learning: A Hedonic Potential-Game Approach

Resumo Técnico: Formação de Coalizões Estável e Orçamentariamente Viável para Aprendizado Federado Agrupado

Declaração do Problema
Sistemas de aprendizado federado (FL) frequentemente sofrem com heterogeneidade estatística, onde uma única "grande coalizão" de todos os participantes gera modelos subótimos. Embora o FL agrupado (clustered FL) aborde o lado estatístico ao agrupar participantes compatíveis, o lado econômico permanece pouco explorado. Especificamente, há uma carência de frameworks que garantam simultaneamente:

1. Estabilidade: Os participantes não têm incentivo para deixar unilateralmente sua coalizão atribuída para outra (estabilidade de Nash) ou para serem rejeitados por uma coalizão de destino (estabilidade individual).
2. Viabilidade Orçamentária: A entidade coordenadora pode financiar as transferências necessárias para compensar os participantes sem incorrer em déficit.
3. Eficiência: A partição resultante aproxima o ótimo de bem-estar social global.

Abordagens existentes frequentemente tratam estabilidade e restrições orçamentárias separadamente ou assumem a superaditividade do excedente, o que não se sustenta em ambientes de FL heterogêneos e não convexos.

Metodologia
O artigo modela o problema como um jogo de formação de coalizões hedônicas com excedente transferível.

• Modelo de Sistema: Os participantes $N$ são particionados em coalizões. Cada coalizão $S$ treina um modelo específico da coalizão $\theta_S$ usando objetivos locais ponderados. O modelo lida com falhas de comunicação (atualizações perdidas) via uma regra de agregação segura que deixa o modelo inalterado se nenhuma atualização chegar.
• Modelo Econômico:
  • Excedente: O excedente total transferível $W(S)$ é definido como o benefício de aprendizado esperado $B(S)$ menos os custos do coordenador $C_0(S)$ e os custos dos participantes $d_i(S)$.
  • Transferências: Um coordenador paga transferências $t_i(S)$ aos participantes. A utilidade do participante é $U_i(S) = t_i(S) - d_i(S)$.
  • Viabilidade Orçamentária: A regra de alocação é fracamente viável do ponto de vista orçamentário se o coordenador retiver excedente não negativo ($R_0(S) \ge 0$) em cada coalizão formada.
• Preferências Hedônicas: As preferências são induzidas por uma regra de alocação que converte o excedente em utilidades. O artigo foca em alocações de excedente de pares simétricos, onde a utilidade de um participante em uma coalizão é a soma dos valores de pares $v_{ij}$ com todos os outros membros $j \in S$.
• Análise Teórica de Jogos:
  • Os autores provam que alocações de pares simétricos induzem um jogo de potencial exato. A função de potencial é a soma dos valores de pares dentro das coalizões.
  • Esta estrutura garante a existência de uma partição estável de Nash e assegura que qualquer sequência de movimentos de melhor resposta estrita termine em passos finitos.
  • A Estabilidade Individual (onde os membros do destino devem consentir com um entrante) também é analisada, mostrando que, se os valores de pares forem não negativos, a estabilidade de Nash implica a estabilidade individual.
• Bem-estar e Eficiência:
  • O bem-estar social é decomposto em utilidade do participante (ligada à função de potencial) e folga retida pelo coordenador.
  • O artigo estabelece que o equilíbrio orçamentário exato (zero folga retida) gera uma partição estável de Nash que é ótima em termos de bem-estar apenas se o excedente for exatamente representável por pares.
  • Sem a representabilidade exata, a perda de bem-estar pode ser ilimitada sob viabilidade orçamentária. No entanto, se a folga retida for limitada em relação ao ótimo, um limite de eficiência multiplicativa (Preço da Estabilidade) é derivado.
  • A maximização do potencial global é mostrada como equivalente ao agrupamento de correlação de máximo-acordo ponderado. O artigo propõe um pipeline: aproximar o agrupamento, então aplicar a estabilização por melhor resposta estrita para alcançar uma partição estável preservando as garantias de aproximação.
• Verificação: O artigo fornece uma verificação de oráculo de tempo polinomial para a viabilidade orçamentária quando a função de folga retida é submodular.

Principais Contribuições

1. Modelagem: Introduz um modelo de FL específico de coalizão que lida com rodadas de comunicação malsucedidas sem agregações indefinidas e não assume superaditividade.
2. Separação Econômica: Separa explicitamente benefícios de aprendizado, custos, transferências e excedente retido pelo coordenador, derivando condições para viabilidade orçamentária e racionalidade individual.
3. Garantias de Estabilidade: Prova que alocações de pares simétricos criam um jogo de potencial exato, garantindo a existência de partições estáveis de Nash e individualmente estáveis com convergência finita.
4. Limites de Eficiência: Caracteriza a relação entre a folga retida pelo coordenador e a eficiência do bem-estar. Prova que o equilíbrio exato gera estabilidade ótima apenas em uma classe específica de excedentes, enquanto a folga relativa limitada fornece um limite de eficiência multiplicativa apertado.
5. Complexidade Computacional: Vincula a maximização do potencial global ao agrupamento de correlação (NP-difícil) e deriva garantias de bem-estar de ponta a ponta para pipelines de aproximação mais estabilização.
6. Verificação: Mostra que inúmeras restrições orçamentárias podem ser verificadas em tempo de oráculo polinomial se a folga retida for submodular.
7. Validação Empírica: Realiza um estudo pré-registrado no CIFAR-10 com $n=4$ participantes.

Resultados Experimentais
O estudo avalia o mecanismo em cinco sementes de dados CIFAR-10 com distribuições heterogêneas:

• Otimalidade de Bem-estar: Em uma calibração "benigna", o mecanismo descentralizado atingiu o ótimo de bem-estar da tabela estimada certificada para todas as cinco sementes. O Preço da Estabilidade empírico foi exatamente 1.
• Estabilidade vs. Baselines: Em contraste, uma linha de base de "compartilhamento de excedente igual" falhou em produzir um resultado estável de Nash em três das cinco sementes (o conjunto estável de Nash era vazio e a dinâmica ciclava).
• Convergência: O processo de melhor resposta descentralizado convergiu rapidamente (média de 1,53 movimentos) a partir de várias inicializações.
• Sensibilidade: Em uma calibração "enxuta" (sensível a custos), os custos de estabilidade aumentaram (Preço da Estabilidade até 1,29), e a partição ótima tornou-se sensível a erros de estimativa, destacando o trade-off entre rigor orçamentário e estabilidade.
• Estimativa: Estimadores de ganho de validação de pares (PVG) forneceram sinais de pares significativamente mais confiáveis do que o alinhamento de gradiente, que era propenoso a falsos positivos.

Significância e Alegações
O artigo afirma conectar valor de aprendizado, transferências monetárias, estabilidade e eficiência econômica sem confundir equilíbrio local, otimalidade global e tratabilidade computacional.

• Teórica: Corrige limitações de trabalhos preliminares ao interpretar corretamente o equilíbrio de Nash como um ótimo de potencial local e ao não assumir superaditividade. Estabelece que estabilidade e eficiência são conceitos distintos ligados pela folga retida pelo coordenador.
• Prática: O mecanismo proposto oferece uma maneira provadamente estável e orçamentariamente viável de organizar participantes de FL heterogêneos. Os resultados empíricos demonstram que, embora regras simples de divisão de excedente possam falhar em estabilizar, a abordagem de potencial de pares proposta garante a convergência para um estado estável que pode coincidir com o ótimo de bem-estar.
• Limitações: Os autores observam que o modelo atual assume que o coordenador conhece ou estima custos e benefícios (alocação de incentivos em vez de design de mecanismo de verdade/truthful mechanism design). A validação empírica é limitada a $n=4$ participantes para permitir enumeração exata e certificação, e os resultados são específicos para as tabelas de valores estimados do experimento.

O trabalho conclui que, embora o equilíbrio orçamentário exato não garanta a otimalidade do bem-estar em geral, o framework proposto fornece uma base teórica robusta e um mecanismo prático para a formação de coalizões estáveis e orçamentariamente viáveis no aprendizado federado agrupado.