Research map / Optimization / Nonconvex and smooth optimization
Fundamental Benefit of Alternating Updates in 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.
Gives global convergence analysis showing alternating GDA (Alt-GDA) is provably faster than simultaneous GDA (Sim-GDA) on strongly-convex-strongly-concave problems, and proposes Alex-GDA, an extrapolation-based alternating framework matching EG's rate with fewer gradient computations and converging linearly on bilinear problems.
Problem
Whether alternating updates in gradient descent-ascent (GDA) provably converge faster than simultaneous updates for minimax optimization, in terms of global convergence rates rather than only local rates.
Approach
Provides tight global iteration complexity bounds with separate condition numbers (kappa_x, kappa_y, kappa_xy) for Sim-GDA and Alt-GDA, and introduces Alex-GDA, which alternates updates while computing gradients at linearly extrapolated iterates, interpolating between Sim-GDA (gamma=0) and Alt-GDA (gamma=1).
Key results
- Alt-GDA iteration complexity upper bound O(kappa_x + kappa_y + kappa_xy(sqrt(kappa_x)+sqrt(kappa_y))) is strictly smaller than the Sim-GDA lower bound Omega(kappa_x + kappa_y + kappa_xy^2).
- Alex-GDA achieves Theta(kappa_x + kappa_y + kappa_xy) iteration complexity, matching EG with half the gradient computations per iteration.
- Alex-GDA converges linearly on bilinear problems where Sim-GDA and Alt-GDA diverge or fail to converge; WGAN-GP with Alex-Adam reports FID 1.53 on MNIST and 6.3 on LSUN Bedroom versus 1.85 and 9.0 for Alt-Adam.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use alternating rather than simultaneous updates | GDA · SCSC, Lipschitz-gradient objectives | iteration complexity: Sim-GDA: Θ (κ_x + κ_y + κ_xy^2) · log(1/ε); Alt-GDA: O ((κ_x + κ_y + κ_xy (√κ_x + √κ_y)) · log(1/ε)) | Helped |
| use alternating rather than simultaneous updates | GDA · SCSC quadratic games, (100+100) dimensions | gradient computations: 1974.2 -> 105.9; 7865.0 -> 149.1; 42762.1 -> 394.9; 104220.5 -> 567.6; 416822.5 -> 777.4 | Helped |
| use Alex-GDA instead of Alt-GDA | GDA · SCSC quadratic games, (100+100) dimensions | gradient computations: 105.9 -> 62.7; 149.1 -> 100.6; 394.9 -> 133.1; 567.6 -> 138.8; 777.4 -> 135.4 | Helped |
| add momentum to Alex-GDA | Alex-GDA · SCSC quadratic games, (100+100) dimensions | gradient computations: 62.7 -> 44.7; 100.6 -> 69.1; 133.1 -> 58.3; 138.8 -> 73.2; 135.4 -> 83.9 | Helped |
| use Alex-Adam instead of Sim-Adam | Adam · WGAN-GP MNIST | FID: 3.97 (1.3) -> 1.53 (0.3) | Helped |
| use Alex-Adam instead of Alt-Adam | Adam · WGAN-GP MNIST | FID: 1.85 (0.3) -> 1.53 (0.3) | Helped |
| use Alex-Adam instead of Sim-Adam | Adam · WGAN-GP CIFAR-10 | FID: 45.0 (1.2) -> 23.8 (1.5) | Helped |
| use Alex-Adam instead of Alt-Adam | Adam · WGAN-GP CIFAR-10 | FID: 24.2 (1.7) -> 23.8 (1.5) | Helped |
| use Alex-Adam instead of Sim-Adam | Adam · WGAN-GP LSUN Bedroom | FID: 131.2 (8.4) -> 6.3 (0.6) | Helped |
| use Alex-Adam instead of Alt-Adam | Adam · WGAN-GP LSUN Bedroom | FID: 9.0 (1.2) -> 6.3 (0.6) | Helped |
| use Alex-GDA with extrapolated iterates | GDA on bilinear problems · unconstrained bilinear minimax problems | convergence | Helped |
| use Alex-GDA rather than EG | minimax optimization · SCSC, Lipschitz-gradient objectives | iteration complexity: Alex-GDA: Θ (κ_x + κ_y + κ_xy) · log(1/ε); EG: Ω (κ_x + κ_y + κ_xy) · log(1/ε) | No clear effect |
Surprising findings
- Alt-GDA and Sim-GDA both fail to converge on unconstrained bilinear problems, while Alex-GDA converges linearly there.
- The paper's Alt-GDA global bound scales as kappa^1.5, leaving a gap to the local kappa rate; the authors conjecture a non-quadratic lower bound.
Limitations
- Alt-GDA upper bound is not shown tight; a conjectured lower bound remains open.
- Convex-concave (non-strongly) convergence of Alex-GDA is only conjectured.
- GAN experiments use moderately tuned step sizes and gamma/delta per dataset.
Experimental setup
Datasets: MNIST CIFAR-10 LSUN Bedroom
Benchmarks: SCSC quadratic games MNIST CIFAR-10 LSUN Bedroom
Metrics: number of gradient computations FID
Baselines: Sim-GDA Alt-GDA EG OGD Sim-Adam Alt-Adam
Builds on: Extra-gradient Optimistic gradient descent Performance Estimation Problem
Closest papers by meaning
- On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems (ICML 2020 · similarity 0.91)
- TiAda: A Time-scale Adaptive Algorithm for Nonconvex Minimax Optimization (ICLR 2023 · similarity 0.91)
- High-probability complexity bounds for stochastic non-convex minimax optimization (NeurIPS 2024 · similarity 0.88)
- Adaptive and Optimal Second-order Optimistic Methods for Minimax Optimization (NeurIPS 2024 · similarity 0.88)
- Last-Iterate Convergence of Single-Loop Stochastic Methods for Constrained Convex-Concave Minimax Problems (NeurIPS 2026 · similarity 0.88)
- Generalization Analysis of Biased Stochastic Gradient Methods for Minimax Problems (NeurIPS 2026 · 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.