Resumo Técnico: HeteRo-Select

Definição do Problema

Os sistemas de Aprendizado Federado (FL) tradicionalmente alocam compressão de gradiente com base na velocidade do link (largura de banda) e na capacidade do dispositivo. Embora eficaz quando a largura de banda correlaciona-se com a informatividade dos dados, essa premissa falha sob condições de dados não-IID (não independentes e identicamente distribuídos). Em redes de borda do mundo real, clientes com dados locais altamente subrepresentados (alta informatividade estatística) frequentemente operam em conexões de baixa largura de banda. Um alocador baseado em capacidade (como o estado da arte FedCG) inadvertidamente atribui a compressão mais agressiva a esses clientes críticos, descartando coordenadas de gradiente estatisticamente importantes e introduzindo perda de informação estrutural. Esse descompasso entre restrições de sistema e utilidade estatística degrada a convergência e a eficiência.

Metodologia: HeteRo-Select

O artigo propõe o HeteRo-Select, um framework que substitui a largura de banda como o principal motor da compressão por uma pontuação de informatividade por cliente ($S_k$). A largura de banda é mantida apenas como um teto rígido para evitar latência de atraso (straggler latency). O framework unifica três decisões de comunicação em uma única pontuação normalizada:

1. Pontuação de Informatividade Composta ($S_k$):
   A pontuação é uma soma ponderada de quatro componentes, normalizada via min-max para $[0, 1]$:

   • Informatividade de Perda ($V'_k$): Perda local normalizada, servindo como um proxy para a distância da convergência.
   • Diversidade de Direção de Gradiente ($D_k$): Mede a diferença angular entre o gradiente recente de um cliente e a média móvel do servidor. Isso atua como um proxy seguro para a privacidade das distribuições de dados subrepresentadas.
   • Justiça/Equidade ($F'_k$): Uma penalidade aditiva para clientes sobre-selecionados e um bônus para sub-selecionados para evitar a inanição (starvation).
   • Obsolescência/Estagnação ($St'_k$): Um bônus logarítmico para clientes não selecionados recentemente, garantindo probabilidades de seleção estritamente positivas e evitando que o sistema colapse em um subconjunto estreito.

2. Mecanismo de Decisão Unificado:

   • Seleção de Clientes: As probabilidades são derivadas via um softmax escalonado por temperatura de $S_k$.
   • Razão de Compressão ($\theta_k$): A razão de compressão por cliente é alocada proporcionalmente a $S_k$ dentro de um orçamento global com cronograma de cosseno, limitado pelo limite de largura de banda do cliente ($\theta_k \leq \theta^{cap}_k$).
   • Peso de Agregação: O servidor agrega atualizações usando pesos proporcionais a $S_k$ antes de aplicar o momento (momentum).

3. Feedback de Erro Adaptativo e Esparsificação:

   • Feedback de Erro: A taxa de decaimento do buffer $\beta(t)$ está vinculada ao orçamento global de compressão. Quando a compressão é pesada (baixo $\theta_t$), os resíduos são preservados por mais tempo para evitar o colapso do buffer.
   • Esparsificação Ponderada pela Curvatura: Enquanto a maioria das camadas usa a seleção padrão baseada em magnitude (top-k), um pequeno conjunto de camadas (amostradas via regra de Markov) utiliza um critério ponderado pela curvatura ($v^2_{k,i} / |H_{ii}|$). Isso reduz o peso de coordenadas em regiões de alta curvatura onde pequenos gradientes são altamente influentes, computado via uma estimativa diagonal de Hutchinson por cliente.

4. Treinamento Local:
   Os clientes executam FedProx com uma taxa de aprendizado global em decaimento. O artigo observa explicitamente que escalar a taxa de aprendizado local pela pontuação de informatividade degrada o desempenho (causando sobrepasso/overshoot), confirmando que o sinal da pontuação é mais eficaz na camada de comunicação, não no otimizador local.

Principais Contribuições

1. Framework Unificado: Uma única pontuação normalizada impulsiona a seleção de clientes, a razão de compressão e o peso de agregação, deslocando o sinal de otimização da capacidade do sistema para a informatividade estatística.
2. Mecanismos Adaptativos: Introdução de um cronograma de feedback de erro vinculado ao orçamento de compressão e uma estratégia de amostragem de camada de Markov para esparsificação ponderada pela curvatura.
3. Garantias Teóricas:
   • Prova de que a amostragem proporcional à pontuação reduz a heterogeneidade efetiva do subconjunto selecionado ($E[B^2_{sel}] \leq B^2$).
   • Prova de que a compressão proporcional à pontuação alcança um erro de top-k agregado menor do que a alocação uniforme sob um orçamento de tráfego fixo.
4. Validação Empírica: Demonstração da eficácia do método através de vários tamanhos de modelo e níveis de heterogeneidade de dados sem necessidade de reajuste de hiperparâmetros.

Resultados Experimentais

Avaliado sob um protocolo que corresponde ao baseline FedCG (100 clientes, 10 selecionados por rodada, 100 rodadas):

• CIFAR-10 (AlexNet): O HeteRo-Select alcança um aceleração de 1.78× e uma redução de 18.2% no tráfego para atingir a meta de 70% de acurácia em comparação ao FedCG.
• Generalização de Escala Cruzada: A mesma configuração (sem reajuste) atingiu com sucesso as acurácias alvo em:
  • MNIST (Regressão Logística, 7.8k parâmetros).
  • CIFAR-10 (AlexNet, 2.78M parâmetros).
  • TinyImageNet (ResNet-18, 11.27M parâmetros).
  • Nota: A meta do CIFAR-100 não foi alcançada dentro de 100 rodadas devido à heterogeneidade extrema, embora a eficiência em níveis de acurácia inferiores tenha permanecido superior.
• Teste de Estresse (Anti-correlação): Quando a largura de banda e a informatividade foram deliberadamente invertidas (clientes informativos em links lentos), o HeteRo-Select ainda atingiu a acurácia alvo com menos tráfego cumulativo do que a execução com largura de banda normal. O sistema converteu déficits de largura de banda em atrasos de tempo em vez de perdas de acurácia através do buffer de erro adaptativo.
• Estudos de Ablação:
  • A remoção do componente de diversidade ($D_k$) causou uma lacuna significativa entre o pico e a acurácia final (1.2 pts), confirmando seu papel na prevenção do desvio (drift) nas rodadas finais.
  • Taxas de aprendizado local adaptativas à pontuação degradaram o desempenho; um cronograma de decaimento global foi considerado ideal.
  • Foi necessária uma regularização proximal forte ($\mu=0.1$) para realizar os ganhos de redução de variância.

Significância e Alegações

O artigo afirma que o HeteRo-Select aborda um descompasso estrutural fundamental nos sistemas atuais de FL: a tendência de comprimir os gradientes mais informativos de forma mais pesada devido às restrições de largura de banda. Ao desacoplar a decisão do que comprimir da capacidade de transmitir, o método garante que a utilidade estatística impulsione a alocação de recursos.

Os autores posicionam o HeteRo-Select como uma extensão da filosofia de otimização conjunta vista no FedCG, mas com um sinal de otimização deslocado. O trabalho demonstra que tratar a informatividade como o principal motor permite que o sistema mantenha altas taxas de convergência e robustez, mesmo quando as capacidades do sistema e as distribuições de dados são anti-correlacionadas. O artigo mantém-se modesto quanto às suas limitações, reconhecendo que a heterogeneidade extrema (ex: CIFAR-100 com 40 classes ausentes) pode exceder a capacidade de um orçamento de rodadas fixas, e que a sonda de curvatura de Hutchinson adiciona um pequeno overhead computacional que nem sempre recupera seu custo em ganhos de acurácia em escalas de modelos menores.