Sharp Bounds for Federated Averaging (Local SGD) and Continuous Perspective

Understand

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 first resolve this question by providing a lower bound for FedAvg that matches the existing upper bound, which shows the existing FedAvg upper bound analysis is not improvable.