mlsanityData to 7 Oct 2026

Refined Analysis of Federated Averaging and Federated Richardson-Romberg

arXiv 2412.01389 ↗First posted 2 Dec 2024stat.ML cs.LG math.OCcited by 0

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 21 of its 40 references that are in the map. First posted on arXiv 2 Dec 2024.

Builds on

21 of 40 references.

References · 21

  1. 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,592
  2. 2018Local SGD Converges Fast and Communicates Littlecited by 595
  3. 2018Parallel Restarted SGD with Faster Convergence and Less Communication: Demystifying Why Model Averaging Works for Deep Learningcited by 277
  4. 2019Tighter Theory for Local SGD on Identical and Heterogeneous Datacited by 266
  5. 2021Achieving Linear Speedup with Partial Worker Participation in Non-IID Federated Learningcited by 192
  6. 2019On the Linear Speedup Analysis of Communication Efficient Momentum SGD for Distributed Non-Convex Optimizationcited by 178
  7. 2019On the Convergence of Local Descent Methods in Federated Learningcited by 150
  8. 2020FedSplit: An algorithmic framework for fast federated optimizationcited by 108
  9. 2018Cooperative SGD: A unified Framework for the Design and Analysis of Communication-Efficient SGD Algorithmscited by 106
  10. 2017Bridging the Gap between Constant Step Size Stochastic Gradient Descent and Markov Chainscited by 84
  11. 2015Communication Complexity of Distributed Convex Learning and Optimizationcited by 59
  12. 2021Convergence and Accuracy Trade-Offs in Federated Learning and Meta-Learningcited by 52
9 more
  1. 2021Sharp Bounds for Federated Averaging (Local SGD) and Continuous Perspectivecited by 38
  2. 2022On the Unreasonable Effectiveness of Federated Averaging with Heterogeneous Datacited by 36
  3. 2022Variance Reduced ProxSkip: Algorithm, Theory and Application to Federated Learningcited by 33
  4. 2021Local Adaptivity in Federated Learning: Convergence and Consistencycited by 31
  5. 2022RandProx: Primal-Dual Optimization Algorithms with Randomized Proximal Updatescited by 27
  6. 2022Communication Acceleration of Local Gradient Methods via an Accelerated Primal-Dual Algorithm with Inexact Proxcited by 19
  7. 2024SCAFFLSA: Taming Heterogeneity in Federated Linear Stochastic Approximation and TD Learningcited by 6
  8. 2024Nonasymptotic Analysis of Stochastic Gradient Descent with the Richardson-Romberg Extrapolationcited by 6
  9. 2017Convergence diagnostics for stochastic gradient descent with constant step sizecited by 5

Built on by

Not cited yet.