Research map / Optimization / Nonconvex and smooth optimization
Achieving Near-Optimal Convergence for Distributed Minimax Optimization with Adaptive Stepsizes
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 D-AdaST, a distributed adaptive minimax method that tracks globally accumulated gradient norms via two extra scalar variables per node to keep adaptive stepsizes consistent, achieving near-optimal O~(eps^-(4+delta)) rate for NC-SC problems.
Problem
Distributed nonconvex-strongly-concave minimax optimization with adaptive stepsizes: locally computed adaptive stepsizes become inconsistent across nodes, causing non-convergence (steady-state error) in fully distributed networks.
Approach
Use gradient-tracking-style consensus on the accumulated gradient-norm buffers (two scalar tracking variables per node) so every node's adaptive stepsize converges to a consistent global value, combined with primal/dual exponent separation (0<beta<alpha<1) for time-scale separation without problem-dependent parameters.
Key results
- D-AdaST achieves O~(eps^-(4+delta)) sample complexity for NC-SC distributed minimax, near the centralized O~(eps^-4) lower bound, with delta arbitrarily small.
- Counterexample shows D-TiAda can have gradient norms stuck at their initial values, while the stepsize inconsistency zeta_v^2 fails to converge for D-TiAda but is driven to zero by D-AdaST.
- Experiments on MNIST robust training and CIFAR-10 WGAN show D-AdaST outperforms D-AdaGrad, D-TiAda, D-NeAda and D-Adam across ring, exponential and dense graphs and initial stepsizes.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add stepsize tracking (ablation) | D-TiAda · Distributed NC-SC minimax | convergence to a stationary point | Helped |
| use D-AdaST instead of D-TiAda | Distributed quadratic minimax example · Synthetic quadratic functions | convergence to a stationary point | Helped |
| use D-AdaST instead of D-SGDA | Distributed quadratic minimax example · Synthetic quadratic functions | convergence to a stationary point | Helped |
| use D-AdaST instead of vanilla distributed adaptive methods | Robust CNN training · MNIST | optimization performance | Helped |
| use D-AdaST instead of D-Adam or D-TiAda | Wasserstein GAN training · CIFAR-10 | inception score | Helped |
| vary the gap between α and β (ablation) | D-AdaST · Synthetic quadratic functions | transient time | Mixed |
| use Adam-like adaptive stepsizes (ablation) | Distributed robust CNN training · MNIST | optimization stability | Hurt |
Surprising findings
- Vanilla distributed adaptive minimax methods (D-TiAda) can fail to converge even though their centralized counterparts converge, due to stepsize inconsistency across nodes.
Limitations
- Theory requires bounded stochastic gradients (Assumption on C) and compact-domain style constraints, which may not hold generally.
- Convergence requires a large total iteration count K satisfying transient-time conditions that depend on kappa and the spectral gap.
- Experiments are limited to small-scale networks (up to 40 nodes) and simple architectures.
Experimental setup
Datasets: MNIST CIFAR-10 synthetic quadratic functions
Benchmarks: MNIST CIFAR-10 synthetic quadratic functions
Metrics: gradient norm squared inception score stepsize inconsistency test accuracy under adversarial perturbation
Baselines: D-SGDA D-TiAda D-AdaGrad D-NeAda D-Adam
Builds on: TiAda D-SGDA AdaGrad NeAda gradient tracking
Closest papers by meaning
- Adaptive and Optimal Second-order Optimistic Methods for Minimax Optimization (NeurIPS 2024 · similarity 0.89)
- Jointly Improving the Sample and Communication Complexities in Decentralized Stochastic Minimax Optimization (AAAI 2024 · similarity 0.88)
- Decentralized Gradient-Free Methods for Stochastic Non-smooth Non-convex Optimization (AAAI 2024 · similarity 0.87)
- Achieving Linear Convergence with Parameter-Free Algorithms in Decentralized Optimization (NeurIPS 2024 · similarity 0.87)
- Lower Bounds and Optimal Algorithms for Non-Smooth Convex Decentralized Optimization over Time-Varying Networks (NeurIPS 2024 · similarity 0.86)
- Convergence of Distributed Adaptive Optimization with Local Updates (ICLR 2025 · similarity 0.86)
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.