Refined Analysis of Federated Averaging and Federated Richardson-Romberg

2024/12/02 by Mangold, Paul, Durmus, Alain, Dieuleveut, Aymeric +2
#FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2412.01389

Abstract

In this paper, we present a novel analysis of \FedAvg with constant step size, relying on the Markov property of the underlying process. We demonstrate that the global iterates of the algorithm converge to a stationary distribution and analyze its resulting bias and variance relative to the problem's solution. We provide a first-order bias expansion in both homogeneous and heterogeneous settings. Interestingly, this bias decomposes into two distinct components: one that depends solely on stochastic gradient noise and another on client heterogeneity. Finally, we introduce a new algorithm based on the Richardson-Romberg extrapolation technique to mitigate this bias.

Related

• Sharp Bounds for Federated Averaging (Local SGD) and Continuous Perspective
• SCAFFOLD: Stochastic Controlled Averaging for Federated Learning
• On the Unreasonable Effectiveness of Federated Averaging with Heterogeneous Data
• A Convergence Theory for Federated Average: Beyond Smoothness
• FedExP: Speeding Up Federated Averaging via Extrapolation