Federated Averaging (FedAvg), also known as Local SGD, is the cornerstone of modern Federated Learning. By allowing clients to perform multiple local updates before synchronizing with a central server, it significantly reduces communication overhead. However, the theoretical understanding of its convergence speed has long remained incomplete. This paper resolves this mystery by introducing the concept of "iterate bias" and utilizing a continuous Stochastic Differential Equation (SDE) perspective to prove that existing upper bounds are sharp.
The Convergence Mystery
The central question in FedAvg research has been: How fast does it actually converge? For years, a gap persisted between optimistic upper bounds and pessimistic lower bounds. Empirical evidence often suggested that FedAvg performed better than the "worst-case" theory predicted. This discrepancy hinted that standard second-order smoothness assumptions (bounded Hessians) were insufficient to capture the algorithm's true behavior. This paper asks whether current theory fully captures the capacity of FedAvg, and if not, what is missing.
Methodology: SDEs and Iterate Bias
To bridge this gap, the authors analyze the standard FedAvg procedure, where clients perform local updates before server averaging.
The core of their analysis rests on three pillars:
- Iterate Bias: They define this as the deviation of the expected SGD trajectory from a noiseless Gradient Descent path. They demonstrate that noise in SGD can "push" the average iterate away from the global optimum if the objective function's curvature is unstable.
- Continuous Perspective: By modeling SGD as a Stochastic Differential Equation (SDE) and applying the Kolmogorov backward equation, they derive a closed-form approximation for this bias. This reveals that the drift is a second-order effect of noise interacting with the third derivative (the rate of change of the Hessian).
- Pathological Construction: To prove their lower bounds are sharp, they construct a piecewise quadratic objective with a sudden change in curvature. This function is smooth in the second-order sense but has an infinite third derivative, illustrating exactly where FedAvg struggles.
Visualizing the Drift
The impact of local steps on the iterate distribution is profound. As shown in the evolution of the probability density function, increasing the number of local steps causes the distribution to shift away from the mean.
This visualization confirms that even with many clients, the average iterate can drift away from the optimum. This drift is the "secret sauce" that explains the performance limits of the algorithm when the function isn't perfectly quadratic.
Key Results and Insights
The paper's findings settle several theoretical debates:
- Sharp Lower Bounds: The authors provide a lower bound for homogeneous FedAvg that perfectly matches the best known upper bounds, proving the current theory is unimprovable without additional assumptions.
- The Role of Third-Order Smoothness: The "slow" convergence rates in previous literature only occur when the Hessian changes drastically. By assuming "third-order smoothness" (a stable Hessian), the authors prove significantly faster rates.
- Improved Convergence Rates: Under third-order smoothness, the non-convex convergence rate improves from $O(1/R^{2/3})$ to $O(1/R^{4/5})$, where $R$ is the number of communication rounds. In the convex case, iterate bias reduces from $\Theta(\eta^2 k^{3/2})$ to $\Theta(\eta^3 k^2)$.
Conclusion
This work explains why FedAvg works so well in practice: most real-world loss functions possess relatively stable curvatures, avoiding the pathological drift that occurs in functions with abrupt Hessian changes. While the paper focuses on the simplest form of FedAvg, the authors suggest that their SDE-based framework could be a powerful tool for analyzing adaptive methods like FedAdam or scenarios with extreme data heterogeneity.
Summary updated