Optimistic Gradient Descent Ascent in Zero-Sum and General-Sum Bilinear Games
| Autor: | de Montbrun, Étienne, Renault, Jérôme |
|---|---|
| Rok vydání: | 2022 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | We study the convergence of Optimistic Gradient Descent Ascent in unconstrained bilinear games. In a first part, we consider the zero-sum case and extend previous results by Daskalakis et al. in 2018, Liang and Stokes in 2019, and others: we prove, for any payoff matrix, the exponential convergence of OGDA to a saddle point and also provide a new, optimal, geometric ratio for the convergence. We also characterize the step sizes inducing convergence, and are able to deduce the optimal step size for the speed of convergence. In a second part, we introduce OGDA for general-sum bilinear games: we show that in an interesting class of games, either OGDA converges exponentially fast to a Nash equilibrium, or the payoffs for both players converge exponentially fast to $+\infty$ (which might be interpreted as endogenous emergence of coordination, or cooperation, among players). We also give sufficient conditions for convergence of OGDA to a Nash equilibrium. These conditions are used to increase the speed of convergence of a min-max problem involving a matrix $A$, by introducing a general-sum game using the Moore-Penrose inverse matrix of $A$. This shows for the first time, at our knowledge, that general-sum games can be used to optimally improve algorithms designed for min-max problems. We finally illustrate our results on simple examples of Generative Adversarial Networks. Comment: Complements the previous version: - Added proofs for the convergence for $\eta \leq \frac{1}{\sqrt{3\mu_{\max}}}$ instead of $\eta \leq \frac{1}{2\sqrt{\mu_{\max}}}$ - Show the importance of the Moore-Penrose inverse to speed up a Zero-Sum game |
| Databáze: | arXiv |
| Externí odkaz: |
|