Refined Analysis of Constant Step Size Federated Averaging and Federated Richardson-Romberg Extrapolation
Mangold, Paul Durmus, Alain Oliviero Dieuleveut, Aymeric Samsonov, Sergey Moulines, Eric
Mangold, Paul
Durmus, Alain Oliviero
Dieuleveut, Aymeric
Samsonov, Sergey
Moulines, Eric
Supervisor
Department
Machine Learning
Embargo End Date
Type
Poster
Date
2025
License
Language
English
Collections
Research Projects
Organizational Units
Journal Issue
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
Citation
P. Mangold, A. O. Durmus, A. Dieuleveut, S. Samsonov, and E. Moulines, “Refined Analysis of Constant Step Size Federated Averaging and Federated Richardson-Romberg Extrapolation,” in Proc. 2025 Int. Conf. on Artificial Intelligence and Statistics (AISTATS), Valencia, Spain, Apr. 2025.
Source
Proceedings of the 28th International Conference on Artificial Intelligence and Statistics (AISTATS) 2025
Conference
28th International Conference on Artificial Intelligence and Statistics (AISTATS)
Keywords
Subjects
Source
28th International Conference on Artificial Intelligence and Statistics (AISTATS)
Publisher
OpenReview