mlsanityData to 7 Oct 2026

Last-iterate convergence rates for min-max optimization

arXiv 1906.02027 ↗First posted 5 Jun 2019math.OC cs.GT cs.LGcited by 25

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year

Citing papers per year: 2021: 13; 2022: 7; 2023: 5.

25 papers.

Sort:

  1. 2021Independent Policy Gradient Methods for Competitive Reinforcement Learningcited by 97
  2. 2021Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivitycited by 43
  3. 2021Extragradient Method: O(1/K) Last-Iterate Convergence for Monotone Variational Inequalities and Connections With Cocoercivitycited by 39
  4. 2021Stochastic Extragradient: General Analysis and Improved Ratescited by 31
  5. 2023Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPscited by 27
  6. 2021Exploration-Exploitation in Multi-Agent Competition: Convergence with Bounded Rationalitycited by 20
  7. 2023ReLOAD: Reinforcement Learning with Optimistic Ascent-Descent for Last-Iterate Convergence in Constrained MDPscited by 19
  8. 2023Single-Call Stochastic Extragradient Methods for Structured Non-monotone Variational Inequalities: Improved Analysis under Weaker Conditionscited by 14
  9. 2022Clipped Stochastic Methods for Variational Inequalities with Heavy-Tailed Noisecited by 13
  10. 2022Two-Scale Gradient Descent Ascent Dynamics Finds Mixed Nash Equilibria of Continuous Games: A Mean-Field Perspectivecited by 13
  11. 2022Riemannian Hamiltonian methods for min-max optimization on manifoldscited by 12
  12. 2021Quasi-Newton Methods for Saddle Point Problems and Beyondcited by 10
13 more
  1. 2021Solving Min-Max Optimization with Hidden Structure via Gradient Descent Ascentcited by 8
  2. 2021Nonconvex-Nonconcave Min-Max Optimization with a Small Maximization Domaincited by 8
  3. 2021Last-Iterate Convergence of Saddle-Point Optimizers via High-Resolution Differential Equationscited by 8
  4. 2022Robust No-Regret Learning in Min-Max Stackelberg Gamescited by 5
  5. 2021Local and Global Uniform Convexity Conditionscited by 4
  6. 2021On the Initialization for Convex-Concave Min-max Problemscited by 4
  7. 2022STay-ON-the-Ridge: Guaranteed Convergence to Local Minimax Equilibrium in Nonconvex-Nonconcave Gamescited by 4
  8. 2021Generative Minimization Networks: Training GANs Without Competitioncited by 3
  9. 2022A Survey of Decision Making in Adversarial Gamescited by 3
  10. 2022Generalised agent for solving higher board states of tic tac toe using Reinforcement Learningcited by 1
  11. 2021Constants of Motion: The Antidote to Chaos in Optimization and Game Dynamicscited by 0
  12. 2023Local Convergence of Gradient Methods for Min-Max Games: Partial Curvature Generically Sufficescited by 0
  13. 2023Stability of Multi-Agent Learning: Convergence in Network Games with Many Playerscited by 0