Minibatch vs Local SGD for Heterogeneous Distributed Learning

2020/06/08 by Blake Woodworth, Kumar Kshitij Patel, Woodworth, Blake +3 · 9 citations
Computer Science · Engineering · #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC) #Privacy-Preserving Technologies in Data #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.2006.04735

openalex publication_date 2020/06/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Citations

• Constrained Consensus and Optimization in Multi-Agent Networks
• Parallel SGD: When does averaging help?
• Local SGD Converges Fast and Communicates Little

Cited by

• On the Convergence and Stability of Distributed Sub-model Training
• Generalization and Optimization of SGD with Lookahead
• Understanding Outer Optimizers in Local SGD: Learning Rates, Momentum, and Acceleration
• Decentralized Stochastic Nonconvex Optimization under the (L₀,L₁)-Smoothness
• FLIX: A Simple and Communication-Efficient Alternative to Local Methods\n in Federated Learning
• Reusing Samples in Variance Reduction
• Federated Learning via Posterior Averaging: A New Perspective and Practical Algorithms
• A Field Guide to Federated Optimization
• Local Stochastic Gradient Descent Ascent: Convergence Analysis and Communication Efficiency

Related

• Is Local SGD Better than Minibatch SGD?
• The Limits and Potentials of Local SGD for Distributed Heterogeneous Learning with Intermittent Communication
• Minibatch and Local SGD: Algorithmic Stability and Linear Speedup in Generalization
• Local Stochastic Gradient Descent Ascent: Convergence Analysis and Communication Efficiency
• Bias-Variance Reduced Local SGD for Less Heterogeneous Federated Learning