Data to 7 Oct 2026

Minibatch vs Local SGD for Heterogeneous Distributed Learning

arXiv 2006.04735 ↗First posted 8 Jun 2020cs.LG math.OC stat.MLcited by 147

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 147 papers in the map (data through 7 Oct 2026). First posted on arXiv 8 Jun 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 31; 2022: 33; 2023: 31; 2024: 29; 2025: 16; 2026: 7.

147 papers.

Sort:

By area:

2021A Field Guide to Federated Optimizationcited by 312
2022ProxSkip: Yes! Local Gradient Steps Provably Lead to Communication Acceleration! Finally!cited by 134
2021Distributionally Robust Federated Averagingcited by 104
2021Learning with User-Level Privacycited by 72
2022Where to Begin? On the Impact of Pre-Training and Initialization in Federated Learningcited by 71
2021What Do We Mean by Generalization in Federated Learning?cited by 62
2022FedAvg with Fine Tuning: Local Updates Lead to Representation Learningcited by 55
2022A Unified Analysis of Federated Learning with Arbitrary Client Participationcited by 45
2021STEM: A Stochastic Two-Sided Momentum Algorithm Achieving Near-Optimal Sample and Communication Complexities for Federated Learningcited by 43
2021Anarchic Federated Learningcited by 42
2021Local Stochastic Gradient Descent Ascent: Convergence Analysis and Communication Efficiencycited by 40
2021Sharp Bounds for Federated Averaging (Local SGD) and Continuous Perspectivecited by 38

38 more

2022On Convergence of FedProx: Local Dissimilarity Invariant Bounds, Non-smoothness and Beyondcited by 37
2021Moshpit SGD: Communication-Efficient Decentralized Training on Heterogeneous Unreliable Devicescited by 36
2022On the Unreasonable Effectiveness of Federated Averaging with Heterogeneous Datacited by 36
2021Proximal and Federated Random Reshufflingcited by 33
2022Variance Reduced ProxSkip: Algorithm, Theory and Application to Federated Learningcited by 33
2021Local Adaptivity in Federated Learning: Convergence and Consistencycited by 31
2023On the Convergence of Federated Averaging with Cyclic Client Participationcited by 31
2021The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communicationcited by 30
2021Bias-Variance Reduced Local SGD for Less Heterogeneous Federated Learningcited by 30
2021Private Federated Learning Without a Trusted Server: Optimal Algorithms for Convex Lossescited by 30
2021FedDR -- Randomized Douglas-Rachford Splitting Algorithms for Nonconvex Federated Composite Optimizationcited by 29
2023Conformal Prediction for Federated Uncertainty Quantification Under Label Shiftcited by 29
2024Finite-Time Analysis of On-Policy Heterogeneous Federated Reinforcement Learningcited by 29
2022Private Non-Convex Federated Learning Without a Trusted Servercited by 26
2022TCT: Convexifying Federated Learning using Bootstrapped Neural Tangent Kernelscited by 26
2021Decentralized Local Stochastic Extra-Gradient for Variational Inequalitiescited by 25
2023Federated Temporal Difference Learning with Linear Function Approximation under Environmental Heterogeneitycited by 25
2021Towards Federated Learning on Time-Evolving Heterogeneous Datacited by 23
2022Server-Side Stepsizes and Sampling Without Replacement Provably Help in Federated Optimizationcited by 23
2022Accelerated Federated Learning with Decoupled Adaptive Optimizationcited by 23
2022Can 5th Generation Local Training Methods Support Client Sampling? Yes!cited by 22
2021Federated Deep AUC Maximization for Heterogeneous Data with a Constant Communication Complexitycited by 21
2021Smoothness Matrices Beat Smoothness Constants: Better Communication Compression Techniques for Distributed Optimizationcited by 21
2023Understanding How Consistency Works in Federated Learning via Stage-wise Relaxed Initializationcited by 21
2021Efficient Algorithms for Federated Saddle Point Optimizationcited by 20
2022A Communication-Efficient Distributed Gradient Clipping Algorithm for Training Deep Neural Networkscited by 20
2023Improved Communication Efficiency in Federated Natural Policy Gradient via ADMM-based Gradient Updatescited by 20
2022FedShuffle: Recipes for Better Use of Local Work in Federated Learningcited by 19
2022Federated Optimization Algorithms with Random Reshuffling and Gradient Compressioncited by 18
2023Achieving Linear Speedup in Non-IID Federated Bilevel Learningcited by 18
2023Federated Learning as Variational Inference: A Scalable Expectation Propagation Approachcited by 17
2022FedSysID: A Federated Approach to Sample-Efficient System Identificationcited by 15
2024FedImpro: Measuring and Improving Client Update in Federated Learningcited by 15
2021On Convergence of Federated Averaging Langevin Dynamicscited by 14
2022FedLite: A Scalable Approach for Federated Learning on Resource-constrained Clientscited by 14
2022Anchor Sampling for Federated Learning with Partial Client Participationcited by 14
2024SDP4Bit: Toward 4-bit Communication Quantization in Sharded Data Parallelism for LLM Trainingcited by 13
2021FLIX: A Simple and Communication-Efficient Alternative to Local Methods in Federated Learningcited by 12

50 most cited of 147 All 147 (JSON)