Minibatch vs Local SGD for Heterogeneous Distributed Learning

Abstract

We analyze Local SGD (aka parallel or federated SGD) and Minibatch SGD in the heterogeneous distributed setting, where each machine has access to stochastic gradient estimates for a different, machine-specific, convex objective; the goal is to optimize w.r.t. the average objective; and machines can only communicate intermittently. We argue that, (i) Minibatch SGD (even without acceleration) dominates all existing analysis of Local SGD in this setting, (ii) accelerated Minibatch SGD is optimal when the heterogeneity is high, and (iii) present the first upper bound for Local SGD that improves over Minibatch SGD in a non-homogeneous regime.

arXiv comment34 pages

References in corpus (11)

• Communication-Efficient Learning of Deep Networks from Decentralized Data
• Constrained Consensus
• Don't Use Large Mini-Batches, Use Local SGD
• Local SGD Converges Fast and Communicates Little
• A Unified Theory of Decentralized SGD with Changing Topology and Local Updates
• Cooperative SGD: A unified Framework for the Design and Analysis of Communication-Efficient SGD Algorithms
• Better Mini-Batch Algorithms via Accelerated Gradient Methods
• Communication Complexity of Distributed Convex Learning and Optimization
• Parallel SGD: When does averaging help?
• Unified Optimal Analysis of the (Stochastic) Gradient Method
• Is Local SGD Better than Minibatch SGD?

Cited by in corpus (28)

• Adaptive Personalized Federated Learning
• Federated Learning of a Mixture of Global and Local Models
• A Field Guide to Federated Optimization
• Mime: Mimicking Centralized Stochastic Algorithms in Federated Learning
• FedCluster: Boosting the Convergence of Federated Learning via Cluster-Cycling
• Federated Learning via Posterior Averaging: A New Perspective and Practical Algorithms
• Recent theoretical advances in decentralized distributed convex optimization
• Local Adaptivity in Federated Learning: Convergence and Consistency
• STEM: A Stochastic Two-Sided Momentum Algorithm Achieving Near-Optimal Sample and Communication Complexities for Federated Learning
• Taming Momentum in a Distributed Asynchronous Environment
• Bias-Variance Reduced Local SGD for Less Heterogeneous Federated Learning
• Local Stochastic Gradient Descent Ascent: Convergence Analysis and Communication Efficiency
• Minimax Estimation for Personalized Federated Learning: An Alternative between FedAvg and Local Training?
• The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication
• Local SGD: Unified Theory and New Efficient Methods
• Efficient Algorithms for Federated Saddle Point Optimization
• Proximal and Federated Random Reshuffling
• Taming GANs with Lookahead-Minmax
• Moshpit SGD: Communication-Efficient Decentralized Training on Heterogeneous Unreliable Devices
• Local SGD Optimizes Overparameterized Neural Networks in Polynomial Time
• CDMA: A Practical Cross-Device Federated Learning Algorithm for General Minimax Problems
• The Minimax Complexity of Distributed Optimization
• Delayed Projection Techniques for Linearly Constrained Problems: Convergence Rates, Acceleration, and Applications
• An Even More Optimal Stochastic Optimization Algorithm: Minibatching and Interpolation Learning
• Parallel and Distributed algorithms for ML problems
• FLIX: A Simple and Communication-Efficient Alternative to Local Methods in Federated Learning
• Asynchronous Distributed Optimization with Stochastic Delays
• Accelerated Stochastic ExtraGradient: Mixing Hessian and Gradient Similarity to Reduce Communication in Distributed and Federated Learning