SketchGuard: Scaling Byzantine-Robust Decentralized Federated Learning via Sketch-Based Screening

1. Declaração do Problema

O Aprendizado Federado Descentralizado (DFL) permite que clientes treinem modelos colaborativamente sem um servidor central, aprimorando a privacidade e a tolerância a falhas. No entanto, o DFL é altamente vulnerável a ataques bizâncios, onde nós maliciosos submetem atualizações envenenadas para interromper o treinamento.

O Gargalo Central:
Defesas robustas a bizâncios existentes (por exemplo, BALANCE, SCCLIP, UBAR) dependem de filtragem baseada em consistência local. Para decidir se deve confiar em um vizinho, um cliente deve:

1. Receber o vetor completo do modelo de alta dimensão do vizinho ($d$ dimensões).
2. Calcular a distância entre o vetor completo e seu próprio modelo.
3. Filtrar com base nessa distância.

A Ineficiência:
Essa abordagem incorre em um custo de comunicação de $O(d \cdot |N_i|)$ por rodada (onde $|N_i|$ é o número de vizinhos), independentemente de quantos vizinhos são eventualmente rejeitados. Em redes em grande escala ou com modelos grandes (por exemplo, 60 milhões de parâmetros), essa comunicação de pré-filtragem torna-se uma barreira fundamental para a implantação, desperdiçando largura de banda em atualizações maliciosas que são descartadas imediatamente após a transmissão.

2. Metodologia: SketchGuard

Os autores propõem o SketchGuard, um framework que desacopla a filtragem da agregação usando estruturas de dados de Count Sketch.

Mecanismo Central

Em vez de trocar modelos completos para triagem, o SketchGuard opera em duas fases:

1. Troca de Esboço (Fase 2):
   • Clientes comprimem suas atualizações de modelo de $d$ dimensões em um Count Sketch de baixa dimensão de tamanho $k$ (onde $k \ll d$).
   • Vizinhos trocam apenas esses esboços (custo de $O(k \cdot |N_i|)$).
   • Clientes calculam distâncias no domínio do esboço para identificar vizinhos "aceitos".
2. Busca Seletiva de Modelo Completo (Fase 4):
   • Vetores de modelo completos são buscados apenas a partir de vizinhos que passaram na filtragem baseada em esboço.
   • Verificação: Antes da agregação, o cliente recalcula o esboço do modelo completo recebido para garantir que corresponda ao esboço enviado na Fase 2. Isso impede que adversários enviem um esboço benigno para passar na filtragem e um modelo completo malicioso posteriormente.

Fundamentação Teórica

O método baseia-se na propriedade de Preservação de Distância do Count Sketch (Lema II.1). Para quaisquer dois vetores $u, v$, com alta probabilidade:
$$(1-\epsilon)\|u-v\|^2 \leq \|CS(u) - CS(v)\|^2 \leq (1+\epsilon)\|u-v\|^2$$
Isso garante que, se um vizinho estiver distante no espaço completo, ele provavelmente estará distante no espaço do esboço, permitindo que o filtro o rejeite com alta confiança.

3. Contribuições Principais

• Inovação Algorítmica: O SketchGuard reduz a complexidade de comunicação por rodada de $O(d|N_i|)$ para $O(k|N_i| + d|S_i|)$, onde $|S_i|$ é o conjunto de vizinhos aceitos. Isso elimina o custo de transmitir modelos completos para vizinhos rejeitados (bizâncios).
• Garantias Teóricas:
  • Os autores provam a convergência para configurações estritamente convexas e não convexas.
  • Demonstram que a filtragem baseada em esboço desvia da filtragem de precisão completa por, no máximo, um fator de $\sqrt{(1+\epsilon)/(1-\epsilon)}$ no limiar efetivo.
  • As taxas de convergência correspondem às taxas ótimas até esse fator controlado, provando que a compressão não quebra fundamentalmente a robustez.
• Análise de Segurança: O design de duas fases com verificação de esboço fecha a superfície de ataque onde um nó bizâncio poderia enviar um esboço benigno, mas um modelo completo malicioso.

4. Resultados Experimentais

O framework foi avaliado em três benchmarks não-IID (FEMNIST, CelebA, Sent140), cinco topologias de rede e quatro tipos de ataque (Desvio Direcionado, Gaussiano, Krum, Backdoor).

• Robustez:

  • O SketchGuard iguala o estado da arte (BALANCE) em termos de Taxa de Erro de Teste (TER).
  • O desvio absoluto médio na TER é de $\leq 0,5$ pontos percentuais em comparação com o BALANCE.
  • Permanece robusto mesmo quando 80% dos vizinhos são bizâncios.
  • A robustez é estável em taxas de compressão que variam de 7:1 a 13.000:1.

• Ganhos de Eficiência:

  • Comunicação: Sob condições adversárias (taxa de rejeição de 50–70%), o SketchGuard alcança 50–70% de economia total de comunicação em comparação com baselines de precisão completa. Em condições benignas, o overhead é insignificante (<0,02%).
  • Cálculo: Reduz o tempo de cálculo em até 82% em redes de alto grau (por exemplo, 299 vizinhos) porque a etapa de triagem é $O(k)$ em vez de $O(d)$.
  • Escalabilidade: Enquanto as baselines escalam linearmente com o tamanho do modelo e o grau da rede, o SketchGuard escala sublinearmente com o tamanho do modelo e permanece quase constante em relação à conectividade da rede para a fase de triagem.

5. Significado e Impacto

• Resolvendo a Barreira de Escalabilidade: O SketchGuard aborda a limitação crítica que impede a implantação de DFL robusto a bizâncios em ambientes de grande escala e com restrições de largura de banda (por exemplo, IoT, borda móvel). Torna a robustez viável para modelos grandes (60M+ parâmetros), onde métodos anteriores eram impraticáveis.
• Generalizabilidade: O framework atua como um "wrapper" aplicável a qualquer defesa bizâncio baseada em similaridade (por exemplo, UBAR, SCCLIP) que dependa de distâncias euclidianas, não apenas à regra de agregação específica usada nos experimentos.
• Rigor Teórico: Fornece a primeira análise formal de convergência para filtragem baseada em esboço em configurações descentralizadas, quantificando o trade-off entre compressão e robustez.

Em resumo, o SketchGuard transforma o DFL robusto a bizâncios de um conceito teoricamente sólido, mas pesado em comunicação, em uma solução escalável e prática, aproveitando o esboço aleatorizado para filtrar nós maliciosos antes que ocorra a transmissão de dados dispendiosa.