mlsanityData to 7 Oct 2026

Local SGD Optimizes Overparameterized Neural Networks in Polynomial Time

arXiv 2107.10868 ↗First posted 22 Jul 2021cs.LG math.OCcited by 10

Not on the map. Why?

Abstract (arXiv)

In this paper we prove that Local (S)GD (or FedAvg) can optimize deep neural networks with Rectified Linear Unit (ReLU) activation function in polynomial time. Despite the established convergence theory of Local SGD on optimizing general smooth functions in communication-efficient distributed optimization, its convergence on non-smooth ReLU networks still eludes full theoretical understanding. The key property used in many Local SGD analysis on smooth function is gradient Lipschitzness, so that the gradient on local models will not drift far away from that on averaged model. However, this decent property does not hold in networks with non-smooth ReLU activation function. We show that, even though ReLU network does not admit gradient Lipschitzness property, the difference between gradients on local models and average model will not change too much, under the dynamics of Local SGD. We validate our theoretical results via extensive experiments. This work is the first to show the convergence of Local SGD on non-smooth functions, and will shed lights on the optimization theory of federated training of deep neural networks.

Key facts. Cited by 10 papers in the map (data through 7 Oct 2026). Builds on 34 of its 40 references that are in the map. First posted on arXiv 22 Jul 2021.

Builds on

34 of 40 references.

References · 34

  1. 2015Deep Residual Learning for Image Recognitioncited by 51,809
  2. 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,592
  3. 2019Advances and Open Problems in Federated Learningcited by 3,021
  4. 2018Federated Optimization in Heterogeneous Networkscited by 2,971
  5. 2019Federated Learning: Challenges, Methods, and Future Directionscited by 1,531
  6. 2016Federated Learning: Strategies for Improving Communication Efficiencycited by 1,461
  7. 2019On the Convergence of FedAvg on Non-IID Datacited by 1,220
  8. 2018Federated Learning with Non-IID Datacited by 1,099
  9. 2018A Convergence Theory for Deep Learning via Over-Parameterizationcited by 784
  10. 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 655
  11. 2018Local SGD Converges Fast and Communicates Littlecited by 595
  12. 2018Gradient Descent Finds Global Minima of Deep Neural Networkscited by 572
22 more
  1. 2018Federated Learning for Mobile Keyboard Predictioncited by 565
  2. 2019Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networkscited by 562
  3. 2016Federated Optimization: Distributed Machine Learning for On-Device Intelligencecited by 558
  4. 2018Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layerscited by 340
  5. 2019Tighter Theory for Local SGD on Identical and Heterogeneous Datacited by 266
  6. 2018Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Datacited by 260
  7. 2019SCAFFOLD: Stochastic Controlled Averaging for Federated Learningcited by 174
  8. 2020Is Local SGD Better than Minibatch SGD?cited by 151
  9. 2019On the Convergence of Local Descent Methods in Federated Learningcited by 150
  10. 2020Minibatch vs Local SGD for Heterogeneous Distributed Learningcited by 147
  11. 2017Convergence Analysis of Two-layer Neural Networks with ReLU Activationcited by 137
  12. 2019An Improved Analysis of Training Over-parameterized Deep Neural Networkscited by 120
  13. 2019Local SGD with Periodic Averaging: Tighter Analysis and Adaptive Synchronizationcited by 106
  14. 2018On the Power of Over-parametrization in Neural Networks with Quadratic Activationcited by 102
  15. 2017Recovery Guarantees for One-hidden-layer Neural Networkscited by 94
  16. 2020Federated Accelerated Stochastic Gradient Descentcited by 85
  17. 2020Global Convergence of Deep Networks with One Wide Layer Followed by Pyramidal Topologycited by 66
  18. 2017Globally Optimal Gradient Descent for a ConvNet with Gaussian Inputscited by 61
  19. 2017An Analytical Formula of Population Gradient for two-layered ReLU network and its Applications in Convergence and Critical Point Analysiscited by 52
  20. 2021On the Proof of Global Convergence of Gradient Descent for Deep ReLU Networks with Linear Widthscited by 44
  21. 2016Parallel SGD: When does averaging help?cited by 30
  22. 2020On the Global Convergence of Training Deep Linear ResNetscited by 29

Built on by

Cited by year

Citing papers per year: 2021: 1; 2022: 1; 2023: 4; 2024: 3; 2025: 1.

10 papers.

  1. 2023FedExP: Speeding Up Federated Averaging via Extrapolationcited by 68
  2. 2023Provable Multi-Task Representation Learning by Two-Layer ReLU Neural Networkscited by 15
  3. 2021On the Convergence of Shallow Neural Network Training with Randomly Masked Neuronscited by 11
  4. 2024The Effectiveness of Local Updates for Decentralized Learning under Data Heterogeneitycited by 7
  5. 2022Faster Convergence of Local SGD for Over-Parameterized Modelscited by 4
  6. 2025Widening the Network Mitigates the Impact of Data Heterogeneity on FedAvgcited by 2
  7. 2024Effectiveness of Distributed Gradient Descent with Local Steps for Overparameterized Modelscited by 1
  8. 2023On the Convergence of Federated Averaging under Partial Participation for Over-parameterized Neural Networkscited by 0
  9. 2023Distributed Continual Learning with CoCoA in High-dimensional Linear Regressioncited by 0
  10. 2024EDiT: A Local-SGD-Based Efficient Distributed Training Method for Large Language Modelscited by 0