SCAFFOLD: Média Controlada Estocástica para Aprendizado Federado

A Média Federada (FedAvg) surgiu como o algoritmo preferido para aprendizado federado devido à sua simplicidade e baixo custo de comunicação. No entanto, apesar dos esforços de pesquisa recentes, seu desempenho não é totalmente compreendido. Obtivemos taxas de convergência precisas para o FedAvg e provamos que ele sofre de `desvio do cliente' quando os dados são heterogêneos (não-iid), resultando em convergência instável e lenta. Como solução, propomos um novo algoritmo (SCAFFOLD) que utiliza variáveis de controle (redução de variância) para corrigir o `desvio do cliente' em suas atualizações locais. Provamos que o SCAFFOLD requer significativamente menos rodadas de comunicação e não é afetado pela heterogeneidade dos dados ou amostragem de clientes. Além disso, mostramos que (para quadráticas) o SCAFFOLD pode aproveitar a similaridade nos dados do cliente, resultando em uma convergência ainda mais rápida. Este é o primeiro resultado a quantificar a utilidade dos passos locais na otimização distribuída.