Optimistic Gradient Descent Ascent in General-Sum Bilinear Games

Etienne de Montbrun and Jerôme Renault
Additional contact information
Etienne de Montbrun: TSE-R - Toulouse School of Economics - UT Capitole - Université Toulouse Capitole - UT - Université de Toulouse - EHESS - École des hautes études en sciences sociales - CNRS - Centre National de la Recherche Scientifique - INRAE - Institut National de Recherche pour l’Agriculture, l’Alimentation et l’Environnement
Jerôme Renault: TSE-R - Toulouse School of Economics - UT Capitole - Université Toulouse Capitole - UT - Université de Toulouse - EHESS - École des hautes études en sciences sociales - CNRS - Centre National de la Recherche Scientifique - INRAE - Institut National de Recherche pour l’Agriculture, l’Alimentation et l’Environnement

Post-Print from HAL

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".

Keywords: Minmax problems; Optimistic Gradient Descent Ascent; Computation of Equilibria; Bilinear Games; Zero-sum Games; General-sum Games (search for similar items in EconPapers)
Date: 2025-07
References: Add references at CitEc
Citations:

Published in Journal of Dynamics and Games, 2025, 12 (3), pp.267-301. ⟨10.3934/jdg.2024030⟩

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hal:journl:hal-05053682

DOI: 10.3934/jdg.2024030

Access Statistics for this paper

More papers in Post-Print from HAL
Bibliographic data for series maintained by CCSD ().