Refined Analysis of Federated Averaging's Bias and Federated Richardson-Romberg Extrapolation
This work addresses bias issues in federated learning, which is crucial for improving model accuracy in distributed and privacy-sensitive applications, but it is incremental as it builds on existing FedAvg analysis.
The paper tackles the bias in Federated Averaging (FedAvg) with constant step size by analyzing its convergence to a stationary distribution and decomposing the bias into components from stochastic gradient noise and client heterogeneity, and introduces a new algorithm using Richardson-Romberg extrapolation to reduce this bias.
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 expansion of the bias 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.