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.
arXiv commentAccepted to AISTATS 2022. The first two authors contributed equally
References in corpus (29)
- Measuring the Effects of Non-Identical Data Distribution for Federated Visual Classification
- Federated Optimization:Distributed Optimization Beyond the Datacenter
- Ensemble Distillation for Robust Model Fusion in Federated Learning
- Improving Federated Learning Personalization via Model Agnostic Meta Learning
- Adaptive Personalized Federated Learning
- FedPAQ: A Communication-Efficient Federated Learning Method with Periodic Averaging and Quantization
- Federated Meta-Learning with Fast Convergence and Efficient Communication
- Agnostic Federated Learning
- Federated Learning of a Mixture of Global and Local Models
- Three Factors Influencing Minima in SGD
- Don't Use Large Mini-Batches, Use Local SGD
- A Field Guide to Federated Optimization
- Cooperative SGD: A unified Framework for the Design and Analysis of Communication-Efficient SGD Algorithms
- 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
- Accelerating Stochastic Gradient Descent For Least Squares Regression
- 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
- Real-Time Edge Intelligence in the Making: A Collaborative Learning Framework via Federated Meta-Learning
- On the Outsized Importance of Learning Rates in Local Update Methods
- Federated Residual Learning
- 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