Local SGD with Periodic Averaging: Tighter Analysis and Adaptive Synchronization

Abstract

Communication overhead is one of the key challenges that hinders the scalability of distributed optimization algorithms. In this paper, we study local distributed SGD, where data is partitioned among computation nodes, and the computation nodes perform local updates with periodically exchanging the model among the workers to perform averaging. While local SGD is empirically shown to provide promising results, a theoretical understanding of its performance remains open. We strengthen convergence analysis for local SGD, and show that local SGD can be far less expensive and applied far more generally than current theory suggests. Specifically, we show that for loss functions that satisfy the Polyak-Łojasiewicz condition, $O((pT{)}^{1/3})$ rounds of communication suffice to achieve a linear speed up, that is, an error of $O(1/pT)$, where $T$ is the total number of model updates at each worker. This is in contrast with previous work which required higher number of communication rounds, as well as was limited to strongly convex loss functions, for a similar asymptotic performance. We also develop an adaptive synchronization scheme that provides a general condition for linear speed up. Finally, we validate the theory with experimental results, running over AWS EC2 clouds and an internal GPU cluster.

arXiv commentPaper accepted to NeurIPS 2019 - We fixed a flaw in the earlier version regarding the dependency on constants but this change does not affect the communication complexity

Cited by in corpus (38)

• Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization
• Adaptive Personalized Federated Learning
• On the Convergence of Local Descent Methods in Federated Learning
• Communication-Efficient Distributed Deep Learning: A Comprehensive Survey
• Communication optimization strategies for distributed deep neural network training: A survey
• Is Local SGD Better than Minibatch SGD?
• Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradients
• Federated Learning with Buffered Asynchronous Aggregation
• Federated Learning with Compression: Unified Analysis and Sharp Guarantees
• Taming Resource Heterogeneity In Distributed ML Training With Dynamic Batching
• Federated Accelerated Stochastic Gradient Descent
• Communication-Efficient Distributed Stochastic AUC Maximization with Deep Neural Networks
• Device Heterogeneity in Federated Learning: A Superquantile Approach
• Federated Learning with Superquantile Aggregation for Heterogeneous Data
• Bias-Variance Reduced Local SGD for Less Heterogeneous Federated Learning
• Local SGD With a Communication Overhead Depending Only on the Number of Workers
• FedDR -- Randomized Douglas-Rachford Splitting Algorithms for Nonconvex Federated Composite Optimization
• Local Stochastic Gradient Descent Ascent: Convergence Analysis and Communication Efficiency
• Federated Composite Optimization
• The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication
• Communication-efficient SGD: From Local SGD to One-Shot Averaging
• Local Stochastic Approximation: A Unified View of Federated Learning and Distributed Multi-Task Reinforcement Learning Algorithms
• DBS: Dynamic Batch Size For Distributed Deep Neural Network Training
• LocalNewton: Reducing Communication Bottleneck for Distributed Learning
• Citadel: Protecting Data Privacy and Model Confidentiality for Collaborative Learning with SGX
• Exploiting Heterogeneity in Robust Federated Best-Arm Identification
• The Minimax Complexity of Distributed Optimization
• Local SGD Optimizes Overparameterized Neural Networks in Polynomial Time
• Federated Deep AUC Maximization for Heterogeneous Data with a Constant Communication Complexity
• CD-SGD: Distributed Stochastic Gradient Descent with Compression and Delay Compensation
• Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyond
• Statistical Estimation and Inference via Local SGD in Federated Learning
• CADA: Communication-Adaptive Distributed Adam
• Compositional federated learning: Applications in distributionally robust averaging and meta learning
• Asynchronous Parallel Nonconvex Optimization Under the Polyak-Lojasiewicz Condition
• Design and Analysis of Uplink and Downlink Communications for Federated Learning
• The Gradient Convergence Bound of Federated Multi-Agent Reinforcement Learning with Efficient Communication
• HPSGD: Hierarchical Parallel SGD With Stale Gradients Featuring