Resumo Técnico: EvoCSFL

Declaração do Problema

O Aprendizado Federado (FL - Federated Learning) enfrenta desafios significativos em sua implantação prática devido à heterogeneidade dos dados dos clientes (distribuições Não-IID) e dos recursos do sistema (variabilidade no poder de computação, largura de banda e energia). Estratégias de seleção de clientes aleatórias, embora simples, falham em identificar clientes de alto desempenho, levando a uma convergência lenta, baixa precisão do modelo global e ao "problema do retardatário" (straggler problem), onde clientes com recursos limitados atrasam todo o ciclo de treinamento.

Os métodos existentes de seleção de clientes geralmente se dividem em três categorias: baseados em aleatoriedade, baseados em histórico e baseados em sondagem (probe-based). No entanto, essas abordagens têm dificuldade em capturar a natureza combinatória do problema de seleção. Avaliar todos os subconjuntos possíveis de clientes é computacionalmente proibitivo (um problema NP-difícil com um espaço de busca que cresce exponencialmente), e a aquisição de status em tempo real é frequentemente muito dispendiosa para ambientes dinâmicos. Consequentemente, os métodos atuais frequentemente ficam presos em ótimos locais ou falham em se adaptar efetivamente a configurações heterogêneas complexas.

Metodologia: EvoCSFL

O artigo propõe o EvoCSFL (Evolutionary Client Selection for FL), um framework evolutivo assistido por substituto (surrogate) que formula a seleção de clientes como um problema de otimização combinatória multiobjetivo. O framework consiste em quatro componentes principais:

1. Formulação do Problema e Design de Métricas

O problema de seleção de clientes é definido como encontrar um subconjunto $S$ de um conjunto candidato $C$ para otimizar uma função métrica abrangente $M(S)$. Esta função equilibra três objetivos:

• Desempenho do Modelo: Baseado na média ponderada das perdas de treinamento local.
• Latência: Definida pelo tempo máximo de treinamento e comunicação entre os clientes selecionados.
• Consumo de Energia: Definido pelo uso máximo de energia entre os clientes selecionados.

A métrica incorpora funções indicadoras para penalizar seleções que excedam orçamentos pré-definidos de latência ($L$) e energia ($E$).

2. Geração de Candidatos e Construção de Dados

Para evitar o alto custo de avaliar subconjuntos aleatórios, o EvoCSFL gera um conjunto inicial de dados de seleções candidatas usando três estratégias estabelecidas: TiFL, FedAvg e Oort. Essas estratégias fornecem um conjunto de subconjuntos de clientes com pontuações de desempenho associadas (calculadas via função métrica). Este conjunto de dados é aumentado com dados históricos de rodadas de comunicação anteriores para construir um conjunto de treinamento para o modelo substituto (surrogate model).

3. Construção do Modelo Substituto (Surrogate Model)

Uma Unidade Recorrente de Porta (GRU - Gated Recurrent Unit) é empregada como o modelo substituto para aproximar o desempenho de subconjuntos de clientes sem executar rodadas de treinamento reais.

• Entrada: Uma sequência de IDs de clientes representando uma seleção.
• Processamento: A sequência é alimentada no codificador GRU. Para impor a invariância de ordem (já que o desempenho depende do conjunto, não da ordem), os dados de treinamento são aumentados através do embaralhamento aleatório das sequências de clientes.
• Saída: Um embedding unificado via mean pooling, passado por uma camada não linear para prever uma pontuação composta.
• Perda (Loss): O modelo é treinado usando o Erro Quadrático Médio (MSE) entre as pontuações previstas e reais.

4. Algoritmo Genético Assistido por Substituto (SAGA)

Em vez de usar métodos baseados em gradiente que são propensos a ótimos locais, o EvoCSFL emprega um Algoritmo Genético (GA) guiado pelo modelo substituto:

• Inicialização: A população é inicializada usando seleções históricas de alta qualidade, em vez de amostragem aleatória, para focar a busca em subespaços promissores.
• Operadores Evolutivos:
  • Seleção: Seleção por roleta (roulette wheel selection).
  • Cruzamento (Crossover): O Cruzamento Ordenado (OX - Ordered Crossover) é utilizado em vez do Cruzamento de Ponto Único (Single-Point Crossover) para garantir que os descendentes não contenham IDs de clientes duplicados, evitando o overhead de detecção de conflitos.
  • Mutação: Uma estratégia híbrida envolvendo mutação de troca (swap mutation) e mutação de substituição para equilibrar a busca local e a diversidade.
• Avaliação de Aptidão (Fitness): O modelo substituto prevê a aptidão dos descendentes, permitindo que o algoritmo explore o vasto espaço combinatório de forma eficiente sem avaliações reais dispendiosas.
• Terminação: O processo itera até a convergência, retornando o subconjunto de clientes com a maior pontuação prevista.

Principais Contribuições

1. Formulação Combinatória: O artigo trata a seleção de clientes como um problema de otimização combinatória multiobjetivo, capturando explicitamente características coletivas de subconjuntos que os métodos de seleção ponto a ponto existentes negligenciam.
2. Eficiência Assistida por Substituto: Ao utilizar um modelo substituto baseado em GRU, o EvoCSFL permite a previsão de baixo custo e alta eficiência do desempenho da seleção, eliminando a necessidade de sondagem ou aquisição de status em tempo real dispendiosa.
3. Capacidade de Busca Global: A integração de algoritmos evolutivos permite a exploração eficiente do espaço de solução exponencialmente grande, identificando conjuntos de clientes próximos do ótimo com alta velocidade de convergência e robustez em ambientes heterogêneos e dinâmicos.
4. Primeira Aplicação de SAEAs em FL: Este trabalho é o primeiro a introduzir Algoritmos Evolutivos Assistidos por Substituto (SAEAs) especificamente para o problema de seleção de clientes em aprendizado federado.

Resultados Experimentais

Experimentos foram conduzidos em quatro conjuntos de dados (MNIST, CIFAR10, CINIC10, TinyImageNet) com graus variados de heterogeneidade de dados (IID e Non-IID). O EvoCSFL foi comparado contra seis baselines: FedAvg, AFL, TiFL, Oort, FedRank e FedGCS.

• Velocidade de Convergência: O EvoCSFL alcançou a convergência mais rápida em todos os benchmarks. No CIFAR10 e CINIC10 (IID), demonstrou acelerações de 2.49× e 2.70×, respectivamente, em comparação ao FedAvg.
• Eficiência Energética: O framework reduziu significativamente o consumo de energia, atingindo apenas 35.8% e 31.5% do custo energético do FedAvg nos referidos conjuntos de dados.
• Robustez em Non-IID: Em ambientes Non-IID desafiadores, o EvoCSFL superou todos os competidores, mostrando uma melhoria média de precisão de 7.5% sobre o FedAvg e superando o subótimo FedGCS em 1.69% no CIFAR10.
• Overhead: O overhead computacional adicional introduzido pelo EvoCSFL por rodada de comunicação foi mínimo (aprox. 3.98 segundos para 100 clientes), representando apenas 70% do tempo médio de treinamento, enquanto a pegada de memória permaneceu insignificante (0.667 MB).
• Análise de Componentes: Estudos de ablação confirmaram a necessidade da inicialização heurística e do modelo substituto. Além disso, o operador de Cruzamento Ordenado (OX) mostrou convergir significativamente mais rápido que o Cruzamento de Ponto Único (o OX convergiu em ~150 gerações versus a falha de convergência do SPX após 300 gerações).

Significância e Alegações

Os autores alegam que o EvoCSFL fornece uma solução robusta para o problema de "otimização dispendiosa" inerente à seleção de clientes em FL. Ao mudar de amostragem simples ou heurísticas gananciosas (greedy) para uma busca evolutiva assistida por substituto, o framework navega efetivamente pelos compromissos entre precisão do modelo, latência e consumo de energia.

O artigo enfatiza que o EvoCSFL não requer a sondagem em tempo real de todos os clientes, tornando-o adequado para ambientes dinâmicos onde os estados dos dispositivos flutuam. Os resultados sugerem que tratar a seleção de clientes como uma tarefa de otimização combinatória dinâmica, guiada por dados históricos e busca evolutiva, produz um desempenho superior em termos de velocidade de convergência, eficiência energética e robustez contra heterogeneidade de dados em comparação com os métodos de estado da arte. Os autores concluem que esta abordagem oferece um caminho prático para o implante de sistemas de FL eficientes em ambientes de borda (edge) heterogêneos e com recursos limitados.