Tighter Theory for Local SGD on Identical and Heterogeneous Data

Abstract

We provide a new analysis of local SGD, removing unnecessary assumptions and elaborating on the difference between two data regimes: identical and heterogeneous. In both cases, we improve the existing theory and provide values of the optimal stepsize and optimal number of local iterations. Our bounds are based on a new notion of variance that is specific to local SGD methods with different data. The tightness of our results is guaranteed by recovering known statements when we plug $H=1$, where $H$ is the number of local steps. The empirical evidence further validates the severe impact of data heterogeneity on the performance of local SGD.

AISTATS 2020. 31 pages, 1 algorithm, 5 theorems, 6 figures

References in corpus (12)

• SCAFFOLD: Stochastic Controlled Averaging for Federated Learning
• FedPAQ: A Communication-Efficient Federated Learning Method with Periodic Averaging and Quantization
• On the Convergence of Local Descent Methods in Federated Learning
• Expanding the Reach of Federated Learning by Reducing Client Resource Requirements
• On the Linear Speedup Analysis of Communication Efficient Momentum SGD for Distributed Non-Convex Optimization
• Variance Reduced Local SGD with Lower Communication Complexity
• The Error-Feedback Framework: Better Rates for SGD with Delayed Gradients and Compressed Communication
• SlowMo: Improving Communication-Efficient Distributed SGD with Slow Momentum
• First Analysis of Local GD on Heterogeneous Data
• Local AdaAlter: Communication-Efficient Stochastic Gradient Descent with Adaptive Learning Rates
• Parallel Restarted SPIDER -- Communication Efficient Distributed Nonconvex Optimization with Optimal Computation Complexity
• Distributed Optimization for Over-Parameterized Learning

Cited by in corpus (14)

• Personalized Federated Learning with Moreau Envelopes
• A Unified Theory of Decentralized SGD with Changing Topology and Local Updates
• FedCluster: Boosting the Convergence of Federated Learning via Cluster-Cycling
• Is Local SGD Better than Minibatch SGD?
• Communication-Efficient Robust Federated Learning with Noisy Labels
• Federated Learning with Superquantile Aggregation for Heterogeneous Data
• Achieving Linear Speedup with Partial Worker Participation in Non-IID Federated Learning
• Device Heterogeneity in Federated Learning: A Superquantile Approach
• The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication
• CDMA: A Practical Cross-Device Federated Learning Algorithm for General Minimax Problems
• CFedAvg: Achieving Efficient Communication and Fast Convergence in Non-IID Federated Learning
• Local Methods with Adaptivity via Scaling
• Local SGD for Near-Quadratic Problems: Improving Convergence under Unconstrained Noise Conditions
• Accelerated Stochastic ExtraGradient: Mixing Hessian and Gradient Similarity to Reduce Communication in Distributed and Federated Learning