# Negative Stepsizes Make Gradient-Descent-Ascent Converge

arXiv: https://arxiv.org/abs/2505.01423 · HTML: https://mlsanity.com/paper/2505.01423/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 47 of its 103 references that are in the map.
- First posted on arXiv 2 May 2025.

## Builds on (most cited first, 30 of 47)

- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems](https://mlsanity.com/paper/1906.00331/) (2019)
- [Training GANs with Optimism](https://mlsanity.com/paper/1711.00141/) (2017)
- [Optimization, Learning, and Games with Predictable Sequences](https://mlsanity.com/paper/1311.1869/) (2013)
- [A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approach](https://mlsanity.com/paper/1901.08511/) (2019)
- [Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile](https://mlsanity.com/paper/1807.02629/) (2018)
- [Near-Optimal Algorithms for Minimax Optimization](https://mlsanity.com/paper/2002.02417/) (2020)
- [The Mechanics of n-Player Differentiable Games](https://mlsanity.com/paper/1802.05642/) (2018)
- [The Numerics of GANs](https://mlsanity.com/paper/1705.10461/) (2017)
- [Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with O(1/k2) Rate on Squared Gradient Norm](https://mlsanity.com/paper/2102.07922/) (2021)
- [Interaction Matters: A Note on Non-asymptotic Local Convergence of Generative Adversarial Networks](https://mlsanity.com/paper/1802.06132/) (2018)
- [Fast Extra Gradient Methods for Smooth Structured Nonconvex-Nonconcave Minimax Problems](https://mlsanity.com/paper/2106.02326/) (2021)
- [Negative Momentum for Improved Game Dynamics](https://mlsanity.com/paper/1807.04740/) (2018)
- [Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problems](https://mlsanity.com/paper/2002.00057/) (2020)
- [The limits of min-max optimization algorithms: convergence to spurious non-critical sets](https://mlsanity.com/paper/2006.09065/) (2020)
- [Acceleration Methods](https://mlsanity.com/paper/2101.09545/) (2021)
- [Extragradient Method: O(1/K) Last-Iterate Convergence for Monotone Variational Inequalities and Connections With Cocoercivity](https://mlsanity.com/paper/2110.04261/) (2021)
- [Smooth Strongly Convex Interpolation and Exact Worst-case Performance of First-order Methods](https://mlsanity.com/paper/1502.05666/) (2015)
- [Last-Iterate Convergence of Optimistic Gradient Method for Monotone Variational Inequalities](https://mlsanity.com/paper/2205.08446/) (2022)
- [Near-optimal Local Convergence of Alternating Gradient Descent-Ascent for Minimax Optimization](https://mlsanity.com/paper/2102.09468/) (2021)
- [On Lower Iteration Complexity Bounds for the Saddle Point Problems](https://mlsanity.com/paper/1912.07481/) (2019)
- [Halpern-Type Accelerated and Splitting Algorithms For Monotone Inclusions](https://mlsanity.com/paper/2110.08150/) (2021)
- [No-Regret Dynamics in the Fenchel Game: A Unified Framework for Algorithmic Convex Optimization](https://mlsanity.com/paper/2111.11309/) (2021)
- [Acceleration by Stepsize Hedging II: Silver Stepsize Schedule for Smooth Convex Optimization](https://mlsanity.com/paper/2309.16530/) (2023)
- [Tight Last-Iterate Convergence of the Extragradient and the Optimistic Gradient Descent-Ascent Algorithm for Constrained Monotone Variational Inequalities](https://mlsanity.com/paper/2204.09228/) (2022)
- [Acceleration by Stepsize Hedging I: Multi-Step Descent and the Silver Stepsize Schedule](https://mlsanity.com/paper/2309.07879/) (2023)
- [Accelerating Smooth Games by Manipulating Spectral Shapes](https://mlsanity.com/paper/2001.00602/) (2020)
- [Generalized Optimistic Methods for Convex-Concave Saddle Point Problems](https://mlsanity.com/paper/2202.09674/) (2022)
- [Two-Timescale Gradient Descent Ascent Algorithms for Nonconvex Minimax Optimization](https://mlsanity.com/paper/2408.11974/) (2024)
- [Sharper Rates for Separable Minimax and Finite Sum Optimization via Primal-Dual Extragradient Methods](https://mlsanity.com/paper/2202.04640/) (2022)

## Built on by (most cited first, 11 of 11)

- [A lower bound for stepsize-based acceleration of gradient descent](https://mlsanity.com/paper/2608.10418/) (2026)
- [An Improved Last-Iterate Convergence Rate for Anchored Gradient Descent Ascent](https://mlsanity.com/paper/2604.03782/) (2026)
- [Optimal Alternating Regret for Online Learning and Games](https://mlsanity.com/paper/2608.24731/) (2026)
- [Improved Gradient Descent Lower Bounds Beyond Nesterov](https://mlsanity.com/paper/2609.02855/) (2026)
- [Pure Exploration via Frank-Wolfe Self-Play](https://mlsanity.com/paper/2509.19901/) (2025)
- [Min-Max Optimization Is Strictly Easier Than Variational Inequalities](https://mlsanity.com/paper/2511.03052/) (2025)
- [Flatland: The Adventures of Gradient Descent with Large Step Sizes](https://mlsanity.com/paper/2606.06722/) (2026)
- [Negative Momentum for Convex-Concave Optimization](https://mlsanity.com/paper/2604.17145/) (2026)
- [On Same-Sample and Independent-Sample Stochastic Extragradient for Monotone Variational Inequalities](https://mlsanity.com/paper/2608.06182/) (2026)
- [A stochastic subgradient method with optimal failure exponent](https://mlsanity.com/paper/2609.37425/) (2026)
- [Stochastic Gradient Descent Ascent is Suboptimal for Nonconvex-PL Min-Max Games](https://mlsanity.com/paper/2610.07814/) (2026)

## Abstract (arXiv)

Efficient computation of min-max problems is a central question in optimization, learning, games, and control. Arguably the most natural algorithm is gradient-descent-ascent (GDA). However, since the 1970s, conventional wisdom has argued that GDA fails to converge even on simple problems. This failure spurred an extensive literature on modifying GDA with additional building blocks such as extragradients, optimism, momentum, anchoring, etc. In contrast, we show that GDA converges in its original form by simply using a judicious choice of stepsizes. The key innovation is the proposal of unconventional stepsize schedules (dubbed slingshot stepsize schedules) that are time-varying, asymmetric, and periodically negative. We show that all three properties are necessary for convergence, and that altogether this enables GDA to converge on the classical counterexamples (e.g., unconstrained convex-concave problems). The core algorithmic intuition is that although negative stepsizes make backward progress, they de-synchronize the min and max variables (overcoming the cycling issue of GDA), and lead to a slingshot phenomenon in which the forward progress in the other iterations is overwhelmingly larger. This results in fast overall convergence. Geometrically, the slingshot dynamics leverage the non-reversibility of gradient flow: positive/negative steps cancel to first order, yielding a second-order net movement in a new direction that leads to convergence and is otherwise impossible for GDA to move in. We interpret this as a second-order finite-differencing algorithm and show that, intriguingly, it approximately implements consensus optimization, an empirically popular algorithm for min-max problems involving deep neural networks (e.g., training GANs).