Effectiveness of Distributed Gradient Descent with Local Steps for Overparameterized Models
Not on the map. Why?
Abstract (arXiv)
In distributed training of machine learning models, gradient descent with local iterative steps, commonly known as Local (Stochastic) Gradient Descent (Local-(S)GD) or Federated averaging (FedAvg), is a very popular method to mitigate communication burden. In this method, gradient steps based on local datasets are taken independently in distributed compute nodes to update the local models, which are then aggregated intermittently. In the interpolation regime, Local-GD can converge to zero training loss. However, with many potential solutions corresponding to zero training loss, it is not known which solution Local-GD converges to. In this work we answer this question by analyzing implicit bias of Local-GD for classification tasks with linearly separable data. For the interpolation regime, our analysis shows that the aggregated global model obtained from Local-GD, with arbitrary number of local steps, converges exactly to the model that would be obtained if all data were in one place (centralized model) ''in direction''. Our result gives the exact rate of convergence to the centralized model with respect to the number of local steps. We also obtain the same implicit bias with a learning rate independent of number of local steps with a modified version of the Local-GD algorithm. Our analysis provides a new view to understand why Local-GD can still perform well with a very large number of local steps even for heterogeneous data. Lastly, we also discuss the extension of our results to Local-SGD and non-separable data.
Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Builds on 43 of its 62 references that are in the map. First posted on arXiv 10 Dec 2024.
Builds on
43 of 62 references.
References · 43
- 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,669
- 2019Advances and Open Problems in Federated Learningcited by 3,046
- 2018Federated Optimization in Heterogeneous Networkscited by 2,987
- 2016Federated Learning: Strategies for Improving Communication Efficiencycited by 1,475
- 2019On the Convergence of FedAvg on Non-IID Datacited by 1,229
- 2020Adaptive Federated Optimizationcited by 1,046
- 2020Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimizationcited by 906
- 2020Ditto: Fair and Robust Federated Learning Through Personalizationcited by 672
- 2017The Implicit Bias of Gradient Descent on Separable Datacited by 655
- 2020Personalized Federated Learning with Moreau Envelopescited by 618
- 2018Local SGD Converges Fast and Communicates Littlecited by 605
- 2018Do Better ImageNet Models Transfer Better?cited by 565
31 more
- 2013DeCAF: A Deep Convolutional Activation Feature for Generic Visual Recognitioncited by 424
- 2020A Unified Theory of Decentralized SGD with Changing Topology and Local Updatescited by 367
- 2018Horovod: fast and easy distributed deep learning in TensorFlowcited by 279
- 2018Parallel Restarted SGD with Faster Convergence and Less Communication: Demystifying Why Model Averaging Works for Deep Learningcited by 278
- 2020Implicit Bias of Gradient Descent for Wide Two-layer Neural Networks Trained with the Logistic Losscited by 268
- 2018Characterizing Implicit Bias in Terms of Optimization Geometrycited by 266
- 2019Tighter Theory for Local SGD on Identical and Heterogeneous Datacited by 266
- 2019SMART: Robust and Efficient Fine-Tuning for Pre-trained Natural Language Models through Principled Regularized Optimizationcited by 254
- 2018Implicit Bias of Gradient Descent on Linear Convolutional Networkscited by 251
- 2018Don't Use Large Mini-Batches, Use Local SGDcited by 202
- 2018Gradient descent aligns the layers of deep linear networkscited by 182
- 2020FedBE: Making Bayesian Model Ensemble Applicable to Federated Learningcited by 176
- 2020Is Local SGD Better than Minibatch SGD?cited by 151
- 2023DiLoCo: Distributed Low-Communication Training of Language Modelscited by 121
- 2023Stochastic Controlled Averaging for Federated Learning with Communication Compressioncited by 101
- 2022How catastrophic can catastrophic forgetting be in linear regression?cited by 81
- 2021On Large-Cohort Training for Federated Learningcited by 74
- 2023Theory on Forgetting and Generalization of Continual Learningcited by 72
- 2023FedExP: Speeding Up Federated Averaging via Extrapolationcited by 69
- 2024Implicit Bias of AdamW: ℓ_∞ Norm Constrained Optimizationcited by 58
- 2024The Implicit Bias of Adam on Separable Datacited by 36
- 2023Continual Learning in Linear Classification on Separable Datacited by 34
- 2022Analysis of Catastrophic Forgetting for Random Orthogonal Transformation Tasks in the Overparameterized Regimecited by 29
- 2023On the Implicit Bias of Adamcited by 27
- 2023Why (and When) does Local SGD Generalize Better than SGD?cited by 26
- 2024OpenDiLoCo: An Open-Source Framework for Globally Distributed Low-Communication Trainingcited by 24
- 2023Implicit Bias of Gradient Descent for Two-layer ReLU and Leaky ReLU Networks on Nearly-orthogonal Datacited by 18
- 2023A Comparative Evaluation of FedAvg and Per-FedAvg Algorithms for Dirichlet Distributed Heterogeneous Datacited by 14
- 2024The Limits and Potentials of Local SGD for Distributed Heterogeneous Learning with Intermittent Communicationcited by 12
- 2021Local SGD Optimizes Overparameterized Neural Networks in Polynomial Timecited by 10
- 2022Faster Convergence of Local SGD for Over-Parameterized Modelscited by 4
Built on by
Citing papers per year: 2026: 1.
1 paper.