Refined Analysis of Constant Step Size Federated Averaging and Federated Richardson-Romberg Extrapolation

Paul Mangold, Alain Oliviero Durmus, Aymeric Dieuleveut, Sergey Samsonov, Eric Moulines
Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, PMLR 258:5023-5031, 2025.

Abstract

In this paper, we present a novel analysis of $\texttt{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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v258-mangold25a, title = {Refined Analysis of Constant Step Size Federated Averaging and Federated Richardson-Romberg Extrapolation}, author = {Mangold, Paul and Durmus, Alain Oliviero and Dieuleveut, Aymeric and Samsonov, Sergey and Moulines, Eric}, booktitle = {Proceedings of The 28th International Conference on Artificial Intelligence and Statistics}, pages = {5023--5031}, year = {2025}, editor = {Li, Yingzhen and Mandt, Stephan and Agrawal, Shipra and Khan, Emtiyaz}, volume = {258}, series = {Proceedings of Machine Learning Research}, month = {03--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v258/main/assets/mangold25a/mangold25a.pdf}, url = {https://proceedings.mlr.press/v258/mangold25a.html}, abstract = {In this paper, we present a novel analysis of $\texttt{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.} }
Endnote
%0 Conference Paper %T Refined Analysis of Constant Step Size Federated Averaging and Federated Richardson-Romberg Extrapolation %A Paul Mangold %A Alain Oliviero Durmus %A Aymeric Dieuleveut %A Sergey Samsonov %A Eric Moulines %B Proceedings of The 28th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2025 %E Yingzhen Li %E Stephan Mandt %E Shipra Agrawal %E Emtiyaz Khan %F pmlr-v258-mangold25a %I PMLR %P 5023--5031 %U https://proceedings.mlr.press/v258/mangold25a.html %V 258 %X In this paper, we present a novel analysis of $\texttt{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.
APA
Mangold, P., Durmus, A.O., Dieuleveut, A., Samsonov, S. & Moulines, E.. (2025). Refined Analysis of Constant Step Size Federated Averaging and Federated Richardson-Romberg Extrapolation. Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 258:5023-5031 Available from https://proceedings.mlr.press/v258/mangold25a.html.

Related Material