# Last-iterate convergence rates for min-max optimization

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

## Key facts

- Cited by 25 papers in the map (data through 7 Oct 2026).
- First posted on arXiv 5 Jun 2019.

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

- [Independent Policy Gradient Methods for Competitive Reinforcement Learning](https://mlsanity.com/paper/2101.04233/) (2021)
- [Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity](https://mlsanity.com/paper/2107.00052/) (2021)
- [Extragradient Method: O(1/K) Last-Iterate Convergence for Monotone Variational Inequalities and Connections With Cocoercivity](https://mlsanity.com/paper/2110.04261/) (2021)
- [Stochastic Extragradient: General Analysis and Improved Rates](https://mlsanity.com/paper/2111.08611/) (2021)
- [Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPs](https://mlsanity.com/paper/2306.11700/) (2023)
- [Exploration-Exploitation in Multi-Agent Competition: Convergence with Bounded Rationality](https://mlsanity.com/paper/2106.12928/) (2021)
- [ReLOAD: Reinforcement Learning with Optimistic Ascent-Descent for Last-Iterate Convergence in Constrained MDPs](https://mlsanity.com/paper/2302.01275/) (2023)
- [Single-Call Stochastic Extragradient Methods for Structured Non-monotone Variational Inequalities: Improved Analysis under Weaker Conditions](https://mlsanity.com/paper/2302.14043/) (2023)
- [Clipped Stochastic Methods for Variational Inequalities with Heavy-Tailed Noise](https://mlsanity.com/paper/2206.01095/) (2022)
- [Two-Scale Gradient Descent Ascent Dynamics Finds Mixed Nash Equilibria of Continuous Games: A Mean-Field Perspective](https://mlsanity.com/paper/2212.08791/) (2022)
- [Riemannian Hamiltonian methods for min-max optimization on manifolds](https://mlsanity.com/paper/2204.11418/) (2022)
- [Quasi-Newton Methods for Saddle Point Problems and Beyond](https://mlsanity.com/paper/2111.02708/) (2021)
- [Solving Min-Max Optimization with Hidden Structure via Gradient Descent Ascent](https://mlsanity.com/paper/2101.05248/) (2021)
- [Nonconvex-Nonconcave Min-Max Optimization with a Small Maximization Domain](https://mlsanity.com/paper/2110.03950/) (2021)
- [Last-Iterate Convergence of Saddle-Point Optimizers via High-Resolution Differential Equations](https://mlsanity.com/paper/2112.13826/) (2021)
- [Robust No-Regret Learning in Min-Max Stackelberg Games](https://mlsanity.com/paper/2203.14126/) (2022)
- [Local and Global Uniform Convexity Conditions](https://mlsanity.com/paper/2102.05134/) (2021)
- [On the Initialization for Convex-Concave Min-max Problems](https://mlsanity.com/paper/2103.00284/) (2021)
- [STay-ON-the-Ridge: Guaranteed Convergence to Local Minimax Equilibrium in Nonconvex-Nonconcave Games](https://mlsanity.com/paper/2210.09769/) (2022)
- [Generative Minimization Networks: Training GANs Without Competition](https://mlsanity.com/paper/2103.12685/) (2021)
- [A Survey of Decision Making in Adversarial Games](https://mlsanity.com/paper/2207.07971/) (2022)
- [Generalised agent for solving higher board states of tic tac toe using Reinforcement Learning](https://mlsanity.com/paper/2212.12252/) (2022)
- [Constants of Motion: The Antidote to Chaos in Optimization and Game Dynamics](https://mlsanity.com/paper/2109.03974/) (2021)
- [Local Convergence of Gradient Methods for Min-Max Games: Partial Curvature Generically Suffices](https://mlsanity.com/paper/2305.17275/) (2023)
- [Stability of Multi-Agent Learning: Convergence in Network Games with Many Players](https://mlsanity.com/paper/2307.13922/) (2023)

## Abstract (arXiv)

While classic work in convex-concave min-max optimization relies on average-iterate convergence results, the emergence of nonconvex applications such as training Generative Adversarial Networks has led to renewed interest in last-iterate convergence guarantees. Proving last-iterate convergence is challenging because many natural algorithms, such as Simultaneous Gradient Descent/Ascent, provably diverge or cycle even in simple convex-concave min-max settings, and previous work on global last-iterate convergence rates has been limited to the bilinear and convex-strongly concave settings. In this work, we show that the Hamiltonian Gradient Descent (HGD) algorithm achieves linear convergence in a variety of more general settings, including convex-concave problems that satisfy a "sufficiently bilinear" condition. We also prove similar convergence rates for the Consensus Optimization (CO) algorithm of [MNG17] for some parameter settings of CO.