Research map / Optimization / Distributed and compressed
Jointly Improving the Sample and Communication Complexities in Decentralized Stochastic Minimax Optimization
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 DGDA-VR, a single-loop decentralized gradient descent-ascent method with SPIDER variance reduction and gradient tracking that needs one communication round per iteration for stochastic nonconvex-strongly-concave minimax problems.
Problem
Decentralized stochastic nonconvex-strongly-concave minimax optimization over a connected network, where existing methods either need multiple communication rounds per iteration or have suboptimal/unsound complexity guarantees.
Approach
Combines SPIDER-type variance reduction with gradient tracking in a decentralized GDA update using a single mixing step per iteration, with a time-scale ratio ηx = ηy/κ² and a 1/κ-scaled ηy, achieving optimal O(ε^-3) oracle and O(ε^-2) communication complexity without multi-round gossip.
Key results
- DGDA-VR achieves O(ε^-3) oracle complexity and O(ε^-2) communication complexity with a single communication round per iteration, matching stated lower bounds.
- On the PL game, DGDA-VR is competitive with SOTA baselines in stationarity violation over 50 epochs.
- Sensitivity analysis shows DGDA-VR is not sensitive to batch sizes S1, S2 and frequency q.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use DGDA-VR with SPIDER-type variance reduction and a single communication round per iteration | Decentralized stochastic nonconvex-strongly-concave minimax optimization · Stochastic nonconvex-strongly-concave minimax | oracle complexity: O(\epsilon^{-3}) | Helped |
| Use DGDA-VR with a single communication round per iteration | Decentralized stochastic nonconvex-strongly-concave minimax optimization · Stochastic nonconvex-strongly-concave minimax | communication complexity: O(\epsilon^{-2}) | Helped |
| Use variance reduction in DGDA-VR | Decentralized stochastic nonconvex-strongly-concave minimax optimization · Stochastic nonconvex-strongly-concave minimax | oracle complexity: O(ϵ−3) | Helped |
| Use DGDA-VR instead of a method requiring multiple communication rounds per iteration | Decentralized stochastic nonconvex-strongly-concave minimax optimization · Stochastic nonconvex-strongly-concave minimax | communication rounds per iteration | Helped |
| Use DGDA-VR | Decentralized stochastic nonconvex-strongly-concave minimax optimization · Stochastic nonconvex-strongly-concave minimax | oracle complexity: O(\epsilon^{-3}); \Omega\left(L\sigma\epsilon^{-3}\right) | Mixed |
| Use DGDA-VR | Decentralized stochastic nonconvex-strongly-concave minimax optimization · Stochastic nonconvex-strongly-concave minimax | communication complexity: O(\epsilon^{-2}); \Omega\left(\frac{L}{\sqrt{1-\rho}\epsilon^2}\right) | Mixed |
Surprising findings
- The DM-HSGD proof (Xian et al. 2021) has fundamental errors so its claimed complexity results do not hold, according to the authors.
Limitations
- Complexity bounds depend on an unclear 1/κ adjustment to the y step size; the authors are unsure whether it is optimal.
- Analysis assumes strong concavity in y and smoothness; nonconvex-nonconcave settings are not covered.
- Experiments use a ring graph with equal weights and relatively small agent counts (M=8 or 20).
Experimental setup
Datasets: a9a ijcnn1 MNIST synthetic Polyak-Lojasiewicz game data
Benchmarks: PL game (quadratic minimax) robust non-convex linear regression on a9a and ijcnn1 robust neural network training on MNIST
Metrics: stationarity violation consensus violation oracle complexity (data points visited) communication rounds
Baselines: DPSOG DM-HSGD GT-DA DREAM GT-SRVR DSGDA
Builds on: SPIDER SARAH gradient tracking DM-HSGD DREAM
Closest papers by meaning
- A Faster Decentralized Algorithm for Nonconvex Minimax Problems (NeurIPS 2021 · similarity 0.92)
- An Online Optimization Perspective on First-Order and Zero-Order Decentralized Nonsmooth Nonconvex Stochastic Optimization (ICML 2024 · similarity 0.90)
- Decentralized Convex Finite-Sum Optimization with Better Dependence on Condition Numbers (ICML 2024 · similarity 0.89)
- Near-Optimal Distributed Minimax Optimization under the Second-Order Similarity (NeurIPS 2024 · similarity 0.89)
- Towards Faster Decentralized Stochastic Optimization with Communication Compression (ICLR 2025 · similarity 0.88)
- Lower Bounds and Optimal Algorithms for Non-Smooth Convex Decentralized Optimization over Time-Varying Networks (NeurIPS 2024 · similarity 0.88)
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.