Adaptive Data Admission and Retention for Streaming Federated Learning

Resumo Técnico: Admissão e Retenção Adaptativa de Dados para Aprendizado Federado de Fluxo (Streaming)

Definição do Problema
Este artigo aborda o desafio do Aprendizado Federado de Fluxo (Streaming Federated Learning - FL) em ambientes onde os dispositivos clientes possuem memória limitada e os dados de treinamento chegam sequencialmente com custos de amostragem variáveis no tempo. Diferente das configurações tradicionais de FL com conjuntos de dados estáticos offline, o FL de fluxo envolve um fluxo contínuo de novas amostras que incorrem em custos de aquisição, anotação ou transmissão. Os clientes não podem armazenar todos os dados históricos indefinidamente. Consequentemente, o sistema enfrenta um compromisso fundamental: admitir amostras novas melhora a diversidade e a generalização dos dados, mas incorre em custos imediatos, enquanto reter e reutilizar amostras históricas reduz custos, mas gera o risco de "desequilíbrio de reutilização" (dependência excessiva de dados obsoletos) e transbordamento de memória.

O problema central é formulado como uma tarefa de otimização estocástica restrita. O objetivo é minimizar o risco de população excessiva cumulativo (a diferença entre o risco do modelo aprendido e o risco de população ideal) sujeito a duas restrições de longo prazo:

1. Orçamento de custo de amostragem: O custo médio de admissão de amostras não deve exceder um limite prescrito.
2. Restrição de ocupação de buffer: O número médio de amostras armazenadas em cada buffer local de cliente não deve exceder sua capacidade de memória.

Crucialmente, a estrutura desacopla o controle: um Servidor de Parâmetros (PS) central decide as quantidades de admissão (quantas novas amostras aceitar), enquanto os clientes individuais gerenciam seus buffers locais de forma independente (quais amostras descartar) com base em informações locais, sem que o PS acesse os dados brutos.

Metodologia
Os autores propõem uma estrutura unificada composta por um limite de aprendizado teórico e uma política de controle online.

1. Derivação do Limite de Erro de Aprendizado:
   O artigo primeiro deriva um limite superior explícito para o risco de população excessiva cumulativo. Este limite caracteriza explicitamente três fatores críticos:

• Tamanho da amostra de treinamento instantânea ($n(t)$): O número de amostras atualmente no buffer utilizadas para o treinamento.
• Crescimento de amostras distintas ($N(t)$): O número cumulativo de amostras únicas visualizadas.
• Desequilíbrio de reutilização: A perda de diversidade estatística causada pela reutilização desigual das amostras armazenadas.
  Para capturar isso, os autores introduzem uma métrica de tamanho de amostra efetivo, $\tilde{N}_{eff}(t) = N(t) \cdot \tilde{V}(t)$, onde $\tilde{V}(t)$ é um fator que mede a uniformidade da reutilização de amostras. O limite mostra que o desempenho do aprendizado degrada se a reutilização de amostras for altamente desigual.

2. Política de Desvio-Mais-Penalidade de Restrição Ativa (ACDPP):
   Para otimizar o sistema online, os autores desenvolvem a política ACDPP, que combina:

• Retenção de $K$-Passos no Lado do Cliente: Uma regra estruturada onde cada amostra admitida é retida por exatamente $K$ rodadas antes de ser descartada. Essa regra determinística simplifica o padrão de reutilização, permitindo que o fator de tamanho de amostra efetivo $\tilde{V}(t)$ seja expresso em forma fechada.
• Admissão Online no Lado do Servidor: Um algoritmo Drift-Plus-Penalty (DPP) modificado. O servidor mantém uma fila virtual de dívida de custo para rastrear violações do orçamento de custo de amostragem. Ele minimiza uma expressão de "desvio-mais-penalidade" onde o termo de penalidade é um substituto para o limite de erro de aprendizado derivado anteriormente.
• Restrições Retangulares Variáveis no Tempo: Uma adição inovadora ao framework DPP padrão. A região de admissão viável é restringida dentro de um intervalo variável no tempo $[\Lambda_{min}(t), \Lambda_{max}(t)]$ que encolhe gradualmente em direção a um ponto de operação alvo $\bar{\Lambda}$ conforme o tempo avança. Este design equilibra a flexibilidade inicial (para se adaptar a custos variáveis) com a estabilidade tardia (para minimizar os termos $1/n(t)$ no limite de erro).

Principais Contribuições

• Caracterização Teórica: O artigo estabelece um limite de erro de aprendizado para FL de fluxo baseado em memória que vincula explicitamente o desempenho ao tamanho de amostra instantâneo, contagem de amostras distintas e desequilíbrio de reutilização via uma representação de tamanho de amostra efetivo.
• Design de Algoritmo: A proposta da política ACDPP, que integra uma regra de retenção de $K$-passos estruturada no lado do cliente com uma regra de admissão online no lado do servidor apresentando restrições retangulares variáveis no tempo.
• Garantias de Desempenho: Os autores provam que a política proposta alcança:
  • Regret Sublinear: O risco excessivo cumulativo cresce de forma sublinear em relação a um benchmark de oráculo sem custo (que possui memória ilimitada e custo de amostragem zero).
  • Violação de Custo Sublinear: A violação cumulativa do orçamento de custo de amostragem cresce de forma sublinear.
  • Violação de Buffer Limitada: Através da seleção offline do horizonte de retenção $K$, mostra-se que a violação cumulativa de ocupação de buffer é uniformemente limitada ($O(1)$).
• Framework de Comparação: A análise emprega uma cadeia de comparação de múltiplas etapas conectando a política ACDPP a uma política auxiliar de admissão constante e, finalmente, ao oráculo sem custo, fornecendo limites de regret explícitos.

Resultados Experimentais
A política foi avaliada em três conjuntos de dados de classificação de imagens: MNIST, CIFAR-10 e ImageNette, sob partições de dados não-i.i.d. e i.i.d.

• Desempenho: A ACDPP superou consistentemente as linhas de base, incluindo uma política híbrida (misturando amostras novas e antigas) e uma política de admissão constante. No CIFAR-10 (não-i.i.d.), a ACDPP melhorou a acurácia de teste em 26,7 pontos percentuais sobre a linha de base híbrida e 3,5 pontos sobre a linha de base de admissão constante.
• Velocidade de Convergência: A ACDPP convergiu significativamente mais rápido, atingindo as acurácias alvo aproximadamente 2,2x a 2,6x mais rápido que as linhas de base em vários conjuntos de dados.
• Satisfação de Restrições: Experimentos confirmaram que a política manteve a ocupação do buffer dentro dos limites prescritos e estabilizou a fila de dívida de custo, validando as garantias teóricas.

Significância e Alegações
O artigo afirma preencher uma lacuna na literatura existente ao fornecer um framework centrado no aprendizado que otimiza conjuntamente a admissão e o gerenciamento de memória sob custos dinâmicos, em vez de focar apenas em recursos do sistema (comunicação/computação) ou seleção estática de amostras.

• Ele vai além dos métodos de seleção "baseados em pontuação" (que assumem que amostras de alto gradiente são valiosas) ao minimizar diretamente o risco de população excessiva cumulativo com garantias de regret teóricas.
• Aborda o desafio específico de dados de fluxo (streaming) onde o aprendiz deve decidir quantas amostras admitir e por quanto tempo retê-las, um problema não totalmente abordado pelos trabalhos anteriores centrados em recursos ou em seleção.
• Os autores enfatizam que sua abordagem fornece garantias de regret sublinear explícitas e lida com os efeitos acoplados da admissão e retenção de amostras, ofereando uma solução fundamentada para o treinamento de modelos de larga escala e privacidade-preservada em sistemas de borda (edge) com fluxos de dados em evolução.