mlsanityData to 7 Oct 2026

Local Stochastic Gradient Descent Ascent: Convergence Analysis and Communication Efficiency

arXiv 2102.13152 ↗First posted 25 Feb 2021cs.LG math.OCcited by 40

Not on the map. Why?

Abstract (arXiv)

Local SGD is a promising approach to overcome the communication overhead in distributed learning by reducing the synchronization frequency among worker nodes. Despite the recent theoretical advances of local SGD in empirical risk minimization, the efficiency of its counterpart in minimax optimization remains unexplored. Motivated by large scale minimax learning problems, such as adversarial robust learning and training generative adversarial networks (GANs), we propose local Stochastic Gradient Descent Ascent (local SGDA), where the primal and dual variables can be trained locally and averaged periodically to significantly reduce the number of communications. We show that local SGDA can provably optimize distributed minimax problems in both homogeneous and heterogeneous data with reduced number of communications and establish convergence rates under strongly-convex-strongly-concave and nonconvex-strongly-concave settings. In addition, we propose a novel variant local SGDA+, to solve nonconvex-nonconcave problems. We give corroborating empirical evidence on different distributed minimax problems.

Key facts. Cited by 40 papers in the map (data through 7 Oct 2026). Builds on 39 of its 59 references that are in the map. First posted on arXiv 25 Feb 2021.

Builds on

39 of 59 references.

References · 39

  1. 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,592
  2. 2018Federated Optimization in Heterogeneous Networkscited by 2,971
  3. 2016Federated Learning: Strategies for Improving Communication Efficiencycited by 1,461
  4. 2019On the Convergence of FedAvg on Non-IID Datacited by 1,220
  5. 2018Local SGD Converges Fast and Communicates Littlecited by 595
  6. 2016Federated Optimization: Distributed Machine Learning for On-Device Intelligencecited by 558
  7. 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 526
  8. 2017Deep Gradient Compression: Reducing the Communication Bandwidth for Distributed Trainingcited by 471
  9. 2019On Gradient Descent Ascent for Nonconvex-Concave Minimax Problemscited by 266
  10. 2019Tighter Theory for Local SGD on Identical and Heterogeneous Datacited by 266
  11. 2017Training GANs with Optimismcited by 217
  12. 2018Don't Use Large Mini-Batches, Use Local SGDcited by 201
27 more
  1. 2019SCAFFOLD: Stochastic Controlled Averaging for Federated Learningcited by 174
  2. 2018Stochastic model-based minimization of weakly convex functionscited by 157
  3. 2020Is Local SGD Better than Minibatch SGD?cited by 151
  4. 2019On the Convergence of Local Descent Methods in Federated Learningcited by 150
  5. 2019Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methodscited by 148
  6. 2016QSGD: Communication-Efficient SGD via Gradient Quantization and Encodingcited by 147
  7. 2020Minibatch vs Local SGD for Heterogeneous Distributed Learningcited by 147
  8. 2018A Variational Inequality Perspective on Generative Adversarial Networkscited by 144
  9. 2017Convergence Analysis of Two-layer Neural Networks with ReLU Activationcited by 137
  10. 2018Optimistic mirror descent in saddle-point problems: Going the extra (gradient) milecited by 132
  11. 2020Near-Optimal Algorithms for Minimax Optimizationcited by 119
  12. 2018An Alternative View: When Does SGD Escape Local Minima?cited by 115
  13. 2018Cooperative SGD: A unified Framework for the Design and Analysis of Communication-Efficient SGD Algorithmscited by 106
  14. 2019Local SGD with Periodic Averaging: Tighter Analysis and Adaptive Synchronizationcited by 106
  15. 2020Robust Federated Learning: The Case of Affine Distribution Shiftscited by 102
  16. 2020FedGAN: Federated Generative Adversarial Networks for Distributed Datacited by 89
  17. 2020Federated Accelerated Stochastic Gradient Descentcited by 85
  18. 2018Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problemscited by 75
  19. 2019Efficient Algorithms for Smooth Minimax Optimizationcited by 75
  20. 2018Interaction Matters: A Note on Non-asymptotic Local Convergence of Generative Adversarial Networkscited by 68
  21. 2019A Decentralized Parallel Algorithm for Training Generative Adversarial Netscited by 43
  22. 2019SGD Converges to Global Minimum in Deep Learning via Star-convex Pathcited by 39
  23. 2019On Solving Minimax Optimization Locally: A Follow-the-Ridge Approachcited by 34
  24. 2017Extragradient method with variance reduction for stochastic variational inequalitiescited by 33
  25. 2019Towards Better Understanding of Adaptive Gradient Algorithms in Generative Adversarial Netscited by 29
  26. 2018Linear Convergence of the Primal-Dual Gradient Method for Convex-Concave Saddle Point Problems without Strong Convexitycited by 28
  27. 2019Communication-Efficient Local Decentralized SGD Methodscited by 21

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 6; 2022: 13; 2023: 10; 2024: 4; 2025: 5; 2026: 2.

40 papers.

Sort:

  1. 2022FedNest: Federated Bilevel, Minimax, and Compositional Optimizationcited by 60
  2. 2022Federated Minimax Optimization: Improved Convergence Analyses and Algorithmscited by 37
  3. 2021Decentralized Local Stochastic Extra-Gradient for Variational Inequalitiescited by 25
  4. 2022FRAug: Tackling Federated Learning with Non-IID Features via Representation Augmentationcited by 24
  5. 2021Distributed Methods with Compressed Communication for Solving Variational Inequalities, with Theoretical Guaranteescited by 15
  6. 2022An Optimal Transport Approach to Personalized Federated Learningcited by 12
  7. 2022Decentralized Stochastic Gradient Descent Ascent for Finite-Sum Minimax Problemscited by 11
  8. 2021FedChain: Chained Algorithms for Near-Optimal Communication Cost in Federated Learningcited by 10
  9. 2022FeDXL: Provable Federated Learning for Deep X-Risk Optimizationcited by 10
  10. 2023Solving a Class of Non-Convex Minimax Optimization in Federated Learningcited by 10
  11. 2021FedMM: Saddle Point Optimization for Federated Adversarial Domain Adaptationcited by 9
  12. 2022A Communication-efficient Algorithm with Linear Convergence for Federated Minimax Learningcited by 9
28 more
  1. 2023Federated Minimax Optimization with Client Heterogeneitycited by 8
  2. 2023Federated Compositional Deep AUC Maximizationcited by 8
  3. 2024Robust Decentralized Learning with Local Updates and Gradient Trackingcited by 8
  4. 2023Similarity, Compression and Local Steps: Three Pillars of Efficient Communications for Distributed Variational Inequalitiescited by 7
  5. 2022Fast Adaptive Federated Bilevel Optimizationcited by 6
  6. 2025Boosting Offline Optimizers with Surrogate Sensitivitycited by 6
  7. 2022Adaptive Federated Minimax Optimization with Lower Complexitiescited by 5
  8. 2025Multiplayer Federated Learning: Reaching Equilibrium with Less Communicationcited by 5
  9. 2023Near-Optimal Decentralized Momentum Method for Nonconvex-PL Minimax Problemscited by 4
  10. 2023Communication-Efficient Gradient Descent-Accent Methods for Distributed Variational Inequalities: Unified Analysis and Local Updatescited by 4
  11. 2023Stochastic Smoothed Gradient Descent Ascent for Federated Minimax Optimizationcited by 4
  12. 2022Distributed saddle point problems for strongly concave-convex functionscited by 3
  13. 2021CDMA: A Practical Cross-Device Federated Learning Algorithm for General Minimax Problemscited by 2
  14. 2021Local AdaGrad-Type Algorithm for Stochastic Convex-Concave Optimizationcited by 2
  15. 2022Faster Adaptive Momentum-Based Federated Methods for Distributed Composition Optimizationcited by 2
  16. 2022Provably Efficient Convergence of Primal-Dual Actor-Critic with Nonlinear Function Approximationcited by 1
  17. 2023Global Nash Equilibrium in Non-convex Multi-player Game: Theory and Algorithmscited by 1
  18. 2024Achieving Near-Optimal Convergence for Distributed Minimax Optimization with Adaptive Stepsizescited by 1
  19. 2024GP-FL: Model-Based Hessian Estimation for Second-Order Over-the-Air Federated Learningcited by 1
  20. 2025Federated Instrumental Variable Analysis via Federated Generalized Method of Momentscited by 1
  21. 2025Federated Stochastic Minimax Optimization under Heavy-Tailed Noisescited by 1
  22. 2022SAGDA: Achieving O(ε-2) Communication Complexity in Federated Min-Max Learningcited by 0
  23. 2023Federated Multi-Sequence Stochastic Approximation with Local Hypergradient Estimationcited by 0
  24. 2023Distributed Dual Coordinate Ascent with Imbalanced Data on a General Tree Networkcited by 0
  25. 2024Near-Optimal Distributed Minimax Optimization under the Second-Order Similaritycited by 0
  26. 2025Decoupled SGDA for Games with Intermittent Strategy Communicationcited by 0
  27. 2026Communication-Efficient Federated AUC Maximization with Cyclic Client Participationcited by 0
  28. 2026Provably Communication-Efficient and Privacy-Preserving Federated Graph Neural Networkscited by 0