Is Local SGD Better than Minibatch SGD?

Abstract

We study local SGD (also known as parallel SGD and federated averaging), a natural and frequently used stochastic distributed optimization method. Its theoretical foundations are currently lacking and we highlight how all existing error guarantees in the convex setting are dominated by a simple baseline, minibatch SGD. (1) For quadratic objectives we prove that local SGD strictly dominates minibatch SGD and that accelerated local SGD is minimax optimal for quadratics; (2) For general convex objectives we provide the first guarantee that at least sometimes improves over minibatch SGD; (3) We show that indeed local SGD does not dominate minibatch SGD by presenting a lower bound on the performance of local SGD that is worse than the minibatch SGD guarantee.

arXiv comment29 pages

References in corpus (16)

• Communication-Efficient Learning of Deep Networks from Decentralized Data
• SCAFFOLD: Stochastic Controlled Averaging for Federated Learning
• Optimal Distributed Online Prediction using Mini-Batches
• Communication Efficient Distributed Optimization using an Approximate Newton-type Method
• Don't Use Large Mini-Batches, Use Local SGD
• Local SGD Converges Fast and Communicates Little
• Cooperative SGD: A unified Framework for the Design and Analysis of Communication-Efficient SGD Algorithms
• Better Mini-Batch Algorithms via Accelerated Gradient Methods
• Adaptive Bound Optimization for Online Convex Optimization
• Local SGD with Periodic Averaging: Tighter Analysis and Adaptive Synchronization
• Parallelizing Stochastic Gradient Descent for Least Squares Regression: mini-batching, averaging, and model misspecification
• Parallel SGD: When does averaging help?
• The Error-Feedback Framework: Better Rates for SGD with Delayed Gradients and Compressed Communication
• Unified Optimal Analysis of the (Stochastic) Gradient Method
• Tighter Theory for Local SGD on Identical and Heterogeneous Data
• On the Randomized Complexity of Minimizing a Convex Quadratic Function

Cited by in corpus (31)

• Adaptive Personalized Federated Learning
• A Field Guide to Federated Optimization
• A Unified Theory of Decentralized SGD with Changing Topology and Local Updates
• FedSplit: An algorithmic framework for fast federated optimization
• Client Selection in Federated Learning: Convergence Analysis and Power-of-Choice Selection Strategies
• Minibatch vs Local SGD for Heterogeneous Distributed Learning
• Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradients
• Federated Learning via Posterior Averaging: A New Perspective and Practical Algorithms
• Linearly Converging Error Compensated SGD
• Federated Learning with Compression: Unified Analysis and Sharp Guarantees
• Recent theoretical advances in decentralized distributed convex optimization
• STEM: A Stochastic Two-Sided Momentum Algorithm Achieving Near-Optimal Sample and Communication Complexities for Federated Learning
• On the Outsized Importance of Learning Rates in Local Update Methods
• A Better Alternative to Error Feedback for Communication-Efficient Distributed Learning
• Local Stochastic Gradient Descent Ascent: Convergence Analysis and Communication Efficiency
• Local SGD With a Communication Overhead Depending Only on the Number of Workers
• The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication
• Faster Non-Convex Federated Learning via Global and Local Momentum
• Federated Face Recognition
• Error Compensated Distributed SGD Can Be Accelerated
• FedPAGE: A Fast Local Stochastic Gradient Method for Communication-Efficient Federated Learning
• Communication-efficient SGD: From Local SGD to One-Shot Averaging
• Memory-Based Optimization Methods for Model-Agnostic Meta-Learning and Personalized Federated Learning
• Convergence and Accuracy Trade-Offs in Federated Learning and Meta-Learning
• Stochastic Optimization with Laggard Data Pipelines
• Exploiting Heterogeneity in Robust Federated Best-Arm Identification
• Delayed Projection Techniques for Linearly Constrained Problems: Convergence Rates, Acceleration, and Applications
• About some works of Boris Polyak on convergence of gradient methods and their development
• Distributed Sparse SGD with Majority Voting
• On Second-order Optimization Methods for Federated Learning
• Trade-offs of Local SGD at Scale: An Empirical Study