Research map / Optimization / Distributed and compressed
Decoupled SGDA for Games with Intermittent Strategy Communication
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Decoupled SGDA, where each player takes local gradient steps on its own parameters using stale opponent strategies received at the last communication round, achieving communication-free convergence on fully decoupled games and communication speed-ups on weakly coupled games.
Problem
Solving N-player and two-player minimax games when players can only exchange strategies intermittently, so opponents' strategies are outdated and communication is costly.
Approach
Each player performs K local gradient steps updating only its own parameters using the opponent's parameters frozen at the start of the round; convergence depends on a coupling degree kappa_c = L_c/mu_bar rather than player condition numbers, giving communication acceleration when interaction is weak.
Key results
- On weakly coupled games Decoupled SGDA needs O(1/(1-4kappa_c) log(1/eps)) communication rounds versus O((kappa_u+kappa_v+kappa_uv^2) log(1/eps)) for GDA, and is zero-communication in the fully decoupled case (kappa_c=0).
- Theory states Decoupled SGDA can beat FOAM's sqrt(kappa_u kappa_v) rate when kappa_c satisfies a condition relative to player conditioning.
- In GAN training on CIFAR-10 and SVHN, Decoupled SGDA reaches lower FID with fewer communication rounds than GDA variants, with larger K helping.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Decoupled SGDA instead of GDA | Quadratic Games · Weakly Coupled Games | convergence at a fixed number of communication rounds | Helped |
| Increase the number of local steps K (ablation) | Decoupled SGDA · Quadratic Games with stronger interaction | convergence per synchronization round | Helped |
| Increase the number of local steps K (ablation) | Decoupled SGDA · Toy GAN | gradient norm at a fixed number of communication rounds | Mixed |
| Use Decoupled SGDA instead of Local SGDA | Quadratic Games · Weak-interaction settings | gradient norm at a fixed number of communication rounds | Helped |
| Increase off-diagonal gradient noise (ablation) | Decoupled SGDA · Quadratic Games with imbalanced noise | gradient norm at a fixed number of communication rounds | No clear effect |
| Increase off-diagonal gradient noise (ablation) | Local SGDA · Quadratic Games with imbalanced noise | gradient norm at a fixed number of communication rounds | Hurt |
| Use Decoupled SGDA instead of standard GDA and its variants | GAN training · CIFAR-10 | FID | Helped |
| Increase the number of local steps K (ablation) | Decoupled SGDA · CIFAR-10 | FID | Helped |
| Use Decoupled SGDA instead of standard GDA and its variants | GAN training · SVHN | FID | Helped |
| Increase the number of local steps K (ablation) | Decoupled SGDA · SVHN | FID | Helped |
Surprising findings
- Decoupled SGDA can outperform the optimal first-order method FOAM in communication rounds under a slightly stronger coupling assumption.
- Noise on off-diagonal (opponent) gradient estimates can be arbitrarily large without hurting the convergence bound, unlike Local SGDA.
Limitations
- Theoretical guarantees require strong monotonicity/strong convexity-concavity (SCSC) and the speed-up applies only to weakly coupled regimes.
- Ghost-SGDA extension is heuristic without theoretical guarantees.
- Non-convex GAN experiments are empirical only, without convergence theory.
Experimental setup
Datasets: CIFAR-10 SVHN
Benchmarks: CIFAR-10 SVHN
Metrics: gradient norm FID communication rounds to epsilon accuracy
Baselines: GDA Local SGDA Optimistic GDA Extragradient ALT-GDA EG/OGDA FOAM PEARL-SGD
Builds on: GDA Local SGDA FOAM PEARL-SGD
Closest papers by meaning
- Boosting Perturbed Gradient Ascent for Last-Iterate Convergence in Games (ICLR 2025 · similarity 0.84)
- Jointly Improving the Sample and Communication Complexities in Decentralized Stochastic Minimax Optimization (AAAI 2024 · similarity 0.84)
- Mediator Interpretation and Faster Learning Algorithms for Linear Correlated Equilibria in General Sequential Games (ICLR 2024 · similarity 0.84)
- Towards Runtime Analysis of Population-Based Co-evolutionary Algorithms on Sparse Binary Zero-Sum Game (AAAI 2025 · similarity 0.84)
- Constrained Exploitability Descent: An Offline Reinforcement Learning Method for Finding Mixed-Strategy Nash Equilibrium (ICML 2025 · similarity 0.83)
- Multiplayer Federated Learning: Reaching Equilibrium with Less Communication (NeurIPS 2025 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.