TY  - JOUR
CY  - Springfield
ID  - publications50822
UR  - http://tse-fr.eu/pub/130526
IS  - n° 3
A1  - De Montbrun, Etienne
A1  - Renault, Jerôme
N2  - 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".
VL  - vol 12
TI  - Optimistic Gradient Descent Ascent in General-Sum Bilinear Games
AV  - none
EP  - 301
Y1  - 2025/07//
PB  - American Institute of Mathematical Science
JF  - Journal of Dynamics and Games
SN  - 2164-6066
SP  - 267
ER  -