Sharp Bounds for Federated Averaging (Local SGD) and Continuous Perspective
arXiv:2111.03741
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 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. 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 with the same initialization. We prove novel sharp bounds on this quantity, and show intuitively how to analyze this quantity from a Stochastic Differential Equation (SDE) perspective.
Accepted to AISTATS 2022. The first two authors contributed equally
References in corpus (15)
- Agnostic Federated Learning
- A Field Guide to Federated Optimization
- On the Linear Speedup Analysis of Communication Efficient Momentum SGD for Distributed Non-Convex Optimization
- Federated Learning Based on Dynamic Regularization
- Variance Reduced Local SGD with Lower Communication Complexity
- FedSplit: An algorithmic framework for fast federated optimization
- Implicit Regularization in Deep Learning
- FedMix: Approximation of Mixup under Mean Augmented Federated Learning
- Lower Bounds and Optimal Algorithms for Personalized Federated Learning
- On the Computation and Communication Complexity of Parallel SGD with Dynamic Batch Sizes for Stochastic Non-Convex Optimization
- On the Outsized Importance of Learning Rates in Local Update Methods
- What Do We Mean by Generalization in Federated Learning?
- The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication
- Label Noise SGD Provably Prefers Flat Global Minimizers
- The Minimax Complexity of Distributed Optimization