# Local Convergence of Gradient Methods for Min-Max Games: Partial Curvature Generically Suffices

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 29 references that are in the map.
- First posted on arXiv 26 May 2023.

## Builds on (most cited first, 14 of 14)

- [A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approach](https://mlsanity.com/paper/1901.08511/) (2019)
- [Interaction Matters: A Note on Non-asymptotic Local Convergence of Generative Adversarial Networks](https://mlsanity.com/paper/1802.06132/) (2018)
- [Gradient descent GAN optimization is locally stable](https://mlsanity.com/paper/1706.04156/) (2017)
- [Negative Momentum for Improved Game Dynamics](https://mlsanity.com/paper/1807.04740/) (2018)
- [Differentiable Game Mechanics](https://mlsanity.com/paper/1905.04926/) (2019)
- [Near-optimal Local Convergence of Alternating Gradient Descent-Ascent for Minimax Optimization](https://mlsanity.com/paper/2102.09468/) (2021)
- [Linear Convergence of the Primal-Dual Gradient Method for Convex-Concave Saddle Point Problems without Strong Convexity](https://mlsanity.com/paper/1802.01504/) (2018)
- [Finite Regret and Cycles with Fixed Step-Size via Alternating Gradient Descent-Ascent](https://mlsanity.com/paper/1907.04392/) (2019)
- [Last-iterate convergence rates for min-max optimization](https://mlsanity.com/paper/1906.02027/) (2019)
- [Mirrorless Mirror Descent: A Natural Derivation of Mirror Descent](https://mlsanity.com/paper/2004.01025/) (2020)
- [An Exponentially Converging Particle Method for the Mixed Nash Equilibrium of Continuous Games](https://mlsanity.com/paper/2211.01280/) (2022)
- [Convergence Rates of Two-Time-Scale Gradient Descent-Ascent Dynamics for Solving Nonconvex Min-Max Problems](https://mlsanity.com/paper/2112.09579/) (2021)
- [Average-case Acceleration for Bilinear Games and Normal Matrices](https://mlsanity.com/paper/2010.02076/) (2020)
- [Limiting Behaviors of Nonconvex-Nonconcave Minimax Optimization via Continuous-Time Systems](https://mlsanity.com/paper/2010.10628/) (2020)

## Abstract (arXiv)

We study the convergence to local Nash equilibria of gradient methods for two-player zero-sum differentiable games. It is well-known that such dynamics converge locally when S succ 0 and may diverge when S=0, where Ssucceq 0 is the symmetric part of the Jacobian at equilibrium that accounts for the "potential" component of the game. We show that these dynamics also converge as soon as S is nonzero (partial curvature) and the eigenvectors of the antisymmetric part A are in general position with respect to the kernel of S. We then study the convergence rates when S ll A and prove that they typically depend on the average of the eigenvalues of S, instead of the minimum as an analogy with minimization problems would suggest. To illustrate our results, we consider the problem of computing mixed Nash equilibria of continuous games. We show that, thanks to partial curvature, conic particle methods -- which optimize over both weights and supports of the mixed strategies -- generically converge faster than fixed-support methods. For min-max games, it is thus beneficial to add degrees of freedom "with curvature": this can be interpreted as yet another benefit of over-parameterization.