Solving Min-Max Optimization with Hidden Structure via Gradient Descent Ascent

Abstract

Many recent AI architectures are inspired by zero-sum games, however, the behavior of their dynamics is still not well understood. Inspired by this, we study standard gradient descent ascent (GDA) dynamics in a specific class of non-convex non-concave zero-sum games, that we call hidden zero-sum games. In this class, players control the inputs of smooth but possibly non-linear functions whose outputs are being applied as inputs to a convex-concave game. Unlike general zero-sum games, these games have a well-defined notion of solution; outcomes that implement the von-Neumann equilibrium of the "hidden" convex-concave game. We prove that if the hidden game is strictly convex-concave then vanilla GDA converges not merely to local Nash, but typically to the von-Neumann solution. If the game lacks strict convexity properties, GDA may fail to converge to any equilibrium, however, by applying standard regularization techniques we can prove convergence to a von-Neumann solution of a slightly perturbed zero-sum game. Our convergence guarantees are non-local, which as far as we know is a first-of-its-kind type of result in non-convex non-concave games. Finally, we discuss connections of our framework with generative adversarial networks.

References in corpus (12)

• NIPS 2016 Tutorial: Generative Adversarial Networks
• Stabilizing Training of Generative Adversarial Networks through Regularization
• A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approach
• Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile
• On the Convergence and Robustness of Training GANs with Regularized Optimal Transport
• Last-iterate convergence rates for min-max optimization
• Explore Aggressively, Update Conservatively: Stochastic Extragradient Methods with Variable Stepsize Scaling
• GANs May Have No Nash Equilibria
• Convergence of Gradient Methods on Bilinear Zero-Sum Games
• SGD Learns One-Layer Networks in WGANs
• Chaos, Extremism and Optimism: Volume Analysis of Learning in Games
• Optimality and Stability in Non-Convex Smooth Games