# Two-Timescale Gradient Descent Ascent Algorithms for Nonconvex Minimax Optimization

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- Builds on 53 of its 94 references that are in the map.
- First posted on arXiv 21 Aug 2024.

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

- [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)
- [Stochastic model-based minimization of weakly convex functions](https://mlsanity.com/paper/1803.06523/) (2018)
- [Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods](https://mlsanity.com/paper/1902.08297/) (2019)
- [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)
- [Distributionally Robust Logistic Regression](https://mlsanity.com/paper/1509.09259/) (2015)
- [Cycles in adversarial regularized learning](https://mlsanity.com/paper/1709.02738/) (2017)
- [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 Limit Points of (Optimistic) Gradient Descent in Min-Max Optimization](https://mlsanity.com/paper/1807.03907/) (2018)
- [Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimization](https://mlsanity.com/paper/1807.04252/) (2018)
- [Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization](https://mlsanity.com/paper/2011.00364/) (2020)
- [The Complexity of Constrained Min-Max Optimization](https://mlsanity.com/paper/2009.09623/) (2020)
- [Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problems](https://mlsanity.com/paper/2001.03724/) (2020)
- [Efficient Algorithms for Smooth Minimax Optimization](https://mlsanity.com/paper/1907.01543/) (2019)
- [Interaction Matters: A Note on Non-asymptotic Local Convergence of Generative Adversarial Networks](https://mlsanity.com/paper/1802.06132/) (2018)
- [Sub-sampled Cubic Regularization for Non-convex Optimization](https://mlsanity.com/paper/1705.05933/) (2017)
- [Weakly-Convex Concave Min-Max Optimization: Provable Algorithms and Applications in Machine Learning](https://mlsanity.com/paper/1810.02060/) (2018)
- [A Single-Loop Smoothed Gradient Descent-Ascent Algorithm for Nonconvex-Concave Min-Max Problems](https://mlsanity.com/paper/2010.15768/) (2020)
- [A Unified Single-loop Alternating Gradient Projection Algorithm for Nonconvex-Concave and Convex-Nonconcave Minimax Problems](https://mlsanity.com/paper/2006.02032/) (2020)
- [Hybrid Block Successive Approximation for One-Sided Non-Convex Min-Max Problems: Algorithms and Applications](https://mlsanity.com/paper/1902.08294/) (2019)
- [On the Convergence and Robustness of Training GANs with Regularized Optimal Transport](https://mlsanity.com/paper/1802.08249/) (2018)
- [Faster Single-loop Algorithms for Minimax Optimization without Strong Concavity](https://mlsanity.com/paper/2112.05604/) (2021)
- [Stochastic Variance Reduction for Variational Inequality Methods](https://mlsanity.com/paper/2102.08352/) (2021)
- [The Complexity of Nonconvex-Strongly-Concave Minimax Optimization](https://mlsanity.com/paper/2103.15888/) (2021)
- [Accelerated Zeroth-Order and First-Order Momentum Methods from Mini to Minimax Optimization](https://mlsanity.com/paper/2008.08170/) (2020)
- [Efficient Search of First-Order Nash Equilibria in Nonconvex-Concave Smooth Min-Max Problems](https://mlsanity.com/paper/2002.07919/) (2020)
- [Extragradient Method: O(1/K) Last-Iterate Convergence for Monotone Variational Inequalities and Connections With Cocoercivity](https://mlsanity.com/paper/2110.04261/) (2021)

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

- [Negative Stepsizes Make Gradient-Descent-Ascent Converge](https://mlsanity.com/paper/2505.01423/) (2025)
- [Stackelberg Learning from Human Feedback: Preference Optimization as a Sequential Game](https://mlsanity.com/paper/2512.16626/) (2025)
- [O(1/k) Finite-Time Bound for Non-Linear Two-Time-Scale Stochastic Approximation](https://mlsanity.com/paper/2504.19375/) (2025)
- [Non-Expansive Mappings in Two-Time-Scale Stochastic Approximation: Finite-Time Analysis](https://mlsanity.com/paper/2501.10806/) (2025)
- [NeuCLIP: Efficient Large-Scale CLIP Training with Neural Normalizer Optimization](https://mlsanity.com/paper/2511.08417/) (2025)
- [Causal Invariance Learning via Efficient Nonconvex Optimization](https://mlsanity.com/paper/2412.11850/) (2024)
- [A stochastic smoothing framework for nonconvex-nonconcave minEmax problems with applications to Wasserstein distributionally robust optimization](https://mlsanity.com/paper/2502.17602/) (2025)
- [A New Stochastic Approximation Method for Gradient-based Simulated Parameter Estimation](https://mlsanity.com/paper/2503.18319/) (2025)
- [EXOTIC: An Exact, Optimistic, Tree-Based Algorithm for Min-Max Optimization](https://mlsanity.com/paper/2508.12479/) (2025)
- [Two-Fidelity Best-Action Identification for Stochastic Minimax Tree](https://mlsanity.com/paper/2606.01708/) (2026)
- [Generative modeling using evolved quantum Boltzmann machines](https://mlsanity.com/paper/2512.02721/) (2025)
- [Generative Predictive Distributions for Time Series](https://mlsanity.com/paper/2606.16773/) (2026)
- [Retraction-Free Optimization over the Stiefel Manifold for the LoRA Fine-Tuning](https://mlsanity.com/paper/2607.25299/) (2026)
- [ReliableNet: A Chance-Constrained Approach to Trustworthy Classification in Deep Learning](https://mlsanity.com/paper/2608.09768/) (2026)
- [Matching Multi-Loop Complexities with a Single Loop: Optimal Optimization Stationarity and Best-Known Game Stationarity in Nonconvex--Concave Minimax Optimization](https://mlsanity.com/paper/2609.17973/) (2026)
- [Can You Trust Your Preference Models? Stackelberg Games for Alignment](https://mlsanity.com/paper/2610.15008/) (2026)

## Abstract (arXiv)

We provide a unified analysis of two-timescale gradient descent ascent (TTGDA) for solving structured nonconvex minimax optimization problems in the form of minx maxy ∈ Y f(x, y), where the objective function f(x, y) is nonconvex in x and concave in y, and the constraint set Y subseteq ℝn is convex and bounded. In the convex-concave setting, the single-timescale gradient descent ascent (GDA) algorithm is widely used in applications and has been shown to have strong convergence guarantees. In more general settings, however, it can fail to converge. Our contribution is to design TTGDA algorithms that are effective beyond the convex-concave setting, efficiently finding a stationary point of the function Phi(·) := maxy ∈ Y f(·, y). We also establish theoretical bounds on the complexity of solving both smooth and nonsmooth nonconvex-concave minimax optimization problems. To the best of our knowledge, this is the first systematic analysis of TTGDA for nonconvex minimax optimization, shedding light on its superior performance in training generative adversarial networks (GANs) and in other real-world application problems.