2019/10/28 by Lampros Flokas, Flokas, Lampros, Emmanouil-Vasileios Vlatakis-Gkaragkounis +3 · 1 citation
Computer Science · Mathematics · #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC) #cs.GT #cs.LG #math.OC #stat.ML
paper · pdf · doi:10.48550/arxiv.1910.13010
To appear in NeurIPS 2019 (Spotlight talk)
arxiv created 2019/10/28 · arxiv updated 2019/10/30
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é 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.