mlsanityData to 13 Oct 2026

Decoupled SGDA for Games with Intermittent Strategy Communication

arXiv 2501.14652 ↗First posted 24 Jan 2025cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

We focus on reducing communication overhead in multiplayer games, where frequently exchanging strategies between players is not feasible and players have noisy or outdated strategies of the other players. We introduce Decoupled SGDA, a novel adaptation of Stochastic Gradient Descent Ascent (SGDA). In this approach, players independently update their strategies based on outdated opponent strategies, with periodic synchronization to align strategies. For Strongly-Convex-Strongly-Concave (SCSC) games, we demonstrate that Decoupled SGDA achieves near-optimal communication complexity comparable to the best-known GDA rates. For weakly coupled games where the interaction between players is lower relative to the non-interactive part of the game, Decoupled SGDA significantly reduces communication costs compared to standard SGDA. Our findings extend to multi-player games. To provide insights into the effect of communication frequency and convergence, we extensively study the convergence of Decoupled SGDA for quadratic minimax problems. Lastly, in settings where the noise over the players is imbalanced, Decoupled SGDA significantly outperforms federated minimax methods.

Key facts. No citing papers in the map yet (data through 13 Oct 2026). Builds on 40 of its 59 references that are in the map. First posted on arXiv 24 Jan 2025.

Builds on

40 of 59 references.

References · 40

  1. 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,653
  2. 2017Towards Deep Learning Models Resistant to Adversarial Attackscited by 6,379
  3. 2017Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environmentscited by 1,525
  4. 2019Deep Leakage from Gradientscited by 1,017
  5. 2019Adversarial Training for Free!cited by 641
  6. 2018Local SGD Converges Fast and Communicates Littlecited by 601
  7. 2020iDLG: Improved Deep Leakage from Gradientscited by 380
  8. 2020A Unified Theory of Decentralized SGD with Changing Topology and Local Updatescited by 364
  9. 2019Tighter Theory for Local SGD on Identical and Heterogeneous Datacited by 266
  10. 2020Is Local SGD Better than Minibatch SGD?cited by 151
  11. 2019Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methodscited by 148
  12. 2020Minibatch vs Local SGD for Heterogeneous Distributed Learningcited by 147
28 more
  1. 2019A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approachcited by 142
  2. 2020Near-Optimal Algorithms for Minimax Optimizationcited by 119
  3. 2018The Mechanics of n-Player Differentiable Gamescited by 118
  4. 2020Federated Accelerated Stochastic Gradient Descentcited by 85
  5. 2019Unified Optimal Analysis of the (Stochastic) Gradient Methodcited by 82
  6. 2019Efficient Algorithms for Smooth Minimax Optimizationcited by 76
  7. 2021Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with O(1/k2) Rate on Squared Gradient Normcited by 72
  8. 2020A Framework for Evaluating Gradient Leakage Attacks in Federated Learningcited by 64
  9. 2019A Decentralized Parallel Algorithm for Training Generative Adversarial Netscited by 43
  10. 2021Local Stochastic Gradient Descent Ascent: Convergence Analysis and Communication Efficiencycited by 40
  11. 2022Federated Minimax Optimization: Improved Convergence Analyses and Algorithmscited by 37
  12. 2020Improved Algorithms for Convex-Concave Minimax Optimizationcited by 34
  13. 2018Bandit learning in concave N-person gamescited by 33
  14. 2021Near-optimal Local Convergence of Alternating Gradient Descent-Ascent for Minimax Optimizationcited by 31
  15. 2019On Lower Iteration Complexity Bounds for the Saddle Point Problemscited by 28
  16. 2018A Real-Time Game Theoretic Planner for Autonomous Two-Player Drone Racingcited by 21
  17. 2022The First Optimal Algorithm for Smooth and Strongly-Convex-Strongly-Concave Minimax Optimizationcited by 20
  18. 2020Accelerating Smooth Games by Manipulating Spectral Shapescited by 18
  19. 2022Competition, Alignment, and Equilibria in Digital Marketplacescited by 17
  20. 2020Taming GANs with Lookahead-Minmaxcited by 16
  21. 2023Adversarial Training Should Be Cast as a Non-Zero-Sum Gamecited by 13
  22. 2024The Limits and Potentials of Local SGD for Distributed Heterogeneous Learning with Intermittent Communicationcited by 12
  23. 2024Fundamental Benefit of Alternating Updates in Minimax Optimizationcited by 9
  24. 2020Multi-Hypothesis Interactions in Game-Theoretic Motion Planningcited by 5
  25. 2023PRECISION: Decentralized Constrained Min-Max Learning with Low Communication and Sample Complexitiescited by 5
  26. 2025Multiplayer Federated Learning: Reaching Equilibrium with Less Communicationcited by 5
  27. 2021Minimax Problems with Coupled Linear Constraints: Computational Complexity, Duality and Solution Methodscited by 4
  28. 2021Game Theory and Machine Learning in UAVs-Assisted Wireless Communication Networks: A Surveycited by 1

Built on by

Not cited yet.