Timezone: »

 
Poster
Poincaré Recurrence, Cycles and Spurious Equilibria in Gradient-Descent-Ascent for Non-Convex Non-Concave Zero-Sum Games
Emmanouil-Vasileios Vlatakis-Gkaragkounis · Lampros Flokas · Georgios Piliouras

Wed Dec 11 05:00 PM -- 07:00 PM (PST) @ East Exhibition Hall B + C #221
in Theory -- Game Theory and Computational Economics »

We study a wide class of non-convex non-concave min-max games that generalizes over standard bilinear zero-sum games. In this class, players control the inputs of a smooth function whose output is being applied to a bilinear zero-sum game. This class of games is motivated by the indirect nature of the competition in Generative Adversarial Networks, where players control the parameters of a neural network while the actual competition happens between the distributions that the generator and discriminator capture. We establish theoretically, that depending on the specific instance of the problem gradient-descent-ascent dynamics can exhibit a variety of behaviors antithetical to convergence to the game theoretically meaningful min-max solution. Specifically, different forms of recurrent behavior (including periodicity and Poincar\'{e} recurrence) are possible as well as convergence to spurious (non-min-max) equilibria for a positive measure of initial conditions. At the technical level, our analysis combines tools from optimization theory, game theory and dynamical systems.

Keywords: Game Theory and Computational Economics · Control Theory · Theory · Deep Learning -> Adversarial Networks; Optimization; Optimization -> Non-Convex Optimization; Theory; Theory

Author Information

Emmanouil-Vasileios Vlatakis-Gkaragkounis (Columbia University)
Lampros Flokas (Columbia University)
Georgios Piliouras (Singapore University of Technology and Design)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors