Optimistic Gradient Descent Ascent in General-Sum Bilinear Games

Abstract

We study the convergence of optimistic gradient descent ascent in unconstrained bilinear games. For zero-sum games, we prove exponential convergence to a saddle-point for any payoff matrix, and provide the exact ratio of convergence as a function of the step size. Then, we introduce OGDA for general-sum games and show that, in many cases, either OGDA converges exponentially fast to a Nash equilibrium, or the payoffs for both players converge to . We also show how to increase drastically the speed of convergence of a zero-sum problem by introducing a general-sum game using the Moore-Penrose inverse of the original payoff matrix. To our knowledge, this shows for the first time that general-sum games can be used to optimally improve algorithms designed for min-max problems. We illustrate our results on a toy example of a Wasserstein GAN. Finally, we show how the approach could be extended to the more general class of "hidden bilinear games".

Reference

Etienne de Montbrun, and Jérôme Renault, “Optimistic Gradient Descent Ascent in General-Sum Bilinear Games”, Journal of Dynamics and Games, vol. 12, n. 3, July 2025, pp. 267–301.