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.

34 pages

References in corpus (4)

• A Unified Theory of Decentralized SGD with Changing Topology and Local Updates
• Better Mini-Batch Algorithms via Accelerated Gradient Methods
• Parallel SGD: When does averaging help?
• Is Local SGD Better than Minibatch SGD?

Cited by in corpus (27)

• 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
• 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
• Taming GANs with Lookahead-Minmax
• Proximal and Federated Random Reshuffling
• 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
• Parallel and Distributed algorithms for ML problems
• An Even More Optimal Stochastic Optimization Algorithm: Minibatching and Interpolation Learning
• 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