# Convergence of Gradient Methods on Bilinear Zero-Sum Games

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Aug 2019.

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

- [Adaptive Learning in Continuous Games: Optimal Regret Bounds and Convergence to Nash Equilibrium](https://mlsanity.com/paper/2104.12761/) (2021)
- [Near-optimal Local Convergence of Alternating Gradient Descent-Ascent for Minimax Optimization](https://mlsanity.com/paper/2102.09468/) (2021)
- [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)
- [No-Regret Learning in Games with Noisy Feedback: Faster Rates and Adaptivity via Learning Rate Separation](https://mlsanity.com/paper/2206.06015/) (2022)
- [Complex Momentum for Optimization in Games](https://mlsanity.com/paper/2102.08431/) (2021)
- [Solving Min-Max Optimization with Hidden Structure via Gradient Descent Ascent](https://mlsanity.com/paper/2101.05248/) (2021)
- [Direct-Search for a Class of Stochastic Min-Max Problems](https://mlsanity.com/paper/2102.11386/) (2021)
- [Dissipative Gradient Descent Ascent Method: A Control Theory Inspired Algorithm for Min-max Optimization](https://mlsanity.com/paper/2403.09090/) (2024)
- [Generating Less Certain Adversarial Examples Improves Robust Generalization](https://mlsanity.com/paper/2310.04539/) (2023)
- [Last-Iterate Convergence of Adaptive Riemannian Gradient Descent for Equilibrium Computation](https://mlsanity.com/paper/2306.16617/) (2023)
- [Training Generative Adversarial Networks with Adaptive Composite Gradient](https://mlsanity.com/paper/2111.05508/) (2021)
- [An Efficient Nonlinear Acceleration method that Exploits Symmetry of the Hessian](https://mlsanity.com/paper/2210.12573/) (2022)

## Abstract (arXiv)

Min-max formulations have attracted great attention in the ML community due to the rise of deep generative models and adversarial methods, while understanding the dynamics of gradient algorithms for solving such formulations has remained a grand challenge. As a first step, we restrict to bilinear zero-sum games and give a systematic analysis of popular gradient updates, for both simultaneous and alternating versions. We provide exact conditions for their convergence and find the optimal parameter setup and convergence rates. In particular, our results offer formal evidence that alternating updates converge "better" than simultaneous ones.