Abstract: Federated Averaging (FedAvg), also known as Local SGD, is one of the most popular algorithms in Federated Learning (FL). Despite its simplicity and popularity, the convergence rate of FedAvg has thus far been undetermined. Even under the simplest assumptions (convex, smooth, homogeneous, and bounded covariance), the best-known upper and lower bounds do not match, and it is not clear whether the existing analysis captures the capacity of the algorithm. In this work, we resolve this question by providing a lower bound for FedAvg that matches the existing upper bound, showing the existing analysis is not improvable. Additionally, we establish a lower bound in a heterogeneous setting that nearly matches the existing upper bound. While our lower bounds show the limitations of FedAvg, under an additional assumption of third-order smoothness, we prove more optimistic state-of-the-art convergence results in both convex and non-convex settings. Our analysis stems from a notion we call iterate bias, which is defined by the deviation of the expectation of the SGD trajectory from the noiseless gradient descent trajectory. We prove novel sharp bounds on this quantity and show intuitively how to analyze it from a Stochastic Differential Equation (SDE) perspective.
Introduction
Federated Averaging (FedAvg), or Local SGD, is the workhorse of Federated Learning. Instead of communicating with a server after every single gradient step, clients perform several local steps of SGD before averaging their models. While this saves massive amounts of communication, it introduces a "drift" where local models wander away from the global optimum. For years, there has been a gap between the best-known upper bounds (the guaranteed speed) and lower bounds (the proven limits) for FedAvg, even in the simplest settings. Researchers were unsure if the algorithm was fundamentally limited or if mathematical tools were insufficient to prove a better rate. This paper aims to close that gap and provide a definitive answer.
Methods and the Concept of Iterate Bias
The authors employ three primary strategies to dissect FedAvg:
- Iterate Bias Analysis: They define "iterate bias" as the deviation of the expected SGD trajectory from the noiseless Gradient Descent path. They prove that even with an infinite number of clients, the average model can drift away from the optimum if the objective function's curvature (Hessian) changes abruptly.
- Continuous Perspective (SDEs): To make the math more intuitive, they analyze the continuous limit of SGD using Stochastic Differential Equations. By applying the Kolmogorov backward equation, they show how the third derivative of a function drives the bias of the algorithm.
- Worst-Case Construction: To prove their lower bounds, they construct "hard" objective functions—specifically piecewise quadratics with sudden changes in curvature. These functions are technically "smooth" by standard definitions but have unbounded third derivatives, which "tricks" FedAvg into drifting.
Key Insights
- The "Aha!" of Iterate Bias: The most surprising finding is that FedAvg can fail to converge to the optimum even with infinite homogeneous clients. If the function's Hessian isn't constant, the noise in SGD pushes the iterates into regions with flatter curvature, creating a systematic bias that averaging cannot fix.
- Bridging Theory and Practice: Standard theory assumes "smoothness" (Lipschitz gradients), which allows for functions with "kinks" in their second derivatives. The authors argue that real-world functions (like logistic regression) are usually "third-order smooth." When they add this assumption, the predicted convergence rate improves significantly, matching what practitioners actually see in the field.
- SDEs as a Tool: The paper demonstrates that looking at SGD as a continuous process (an SDE) makes it much easier to identify the specific terms (like the third derivative) that cause optimization errors.
Key Results
The authors established sharp lower bounds that match existing upper bounds, proving that the $1/R^{2/3}$ rate is fundamental and cannot be improved under standard smoothness assumptions.
- Sharp Lower Bounds: The authors established a lower bound of $\Omega(H^{1/3}\sigma^{2/3}D^{4/3} / K^{1/3}R^{2/3})$ for the homogeneous case, which perfectly matches the best-known upper bounds.
- Heterogeneous Setting: They established a nearly matching lower bound for heterogeneous data, showing that the limitations of FedAvg are even more pronounced when clients have different data distributions.
- Optimistic Rates: Under the new third-order smoothness assumption, they proved a state-of-the-art non-convex convergence rate of $O(1/R^{4/5})$, a significant improvement over the previous $O(1/R^{2/3})$ rate.
Conclusion
This paper settles a long-standing theoretical mystery in Federated Learning. By introducing the concept of iterate bias and using a continuous perspective via SDEs, the authors provide sharp lower bounds that match existing upper bounds, proving that current analysis is as good as it gets under standard assumptions. They also show that FedAvg performs much better on "nicer" functions that have smooth third-order derivatives, explaining the gap between pessimistic theory and strong empirical performance.
Summary updated