Related papers: Limiting Behaviors of Nonconvex-Nonconcave Minimax Optimization via Continuous-Time Systems

Limiting Behaviors of Nonconvex-Nonconcave Minimax Optimization via Continuous-Time Systems

URL: http://arxiv.org/abs/2010.10628v2
Date: Thu, 4 Mar 2021 18:09:47 GMT
Title: Limiting Behaviors of Nonconvex-Nonconcave Minimax Optimization via Continuous-Time Systems
Authors: Benjamin Grimmer, Haihao Lu, Pratik Worah, Vahab Mirrokni
Abstract summary: We study the limiting behaviors of three classic minimax algorithms: gradient descent (AGDA), ascentGDA, and the extragradient method (EGM) Numerically, we observe that all limiting behaviors can arise in Generative Adrial Networks (GAN) and are easily demonstrated for a range of GAN problems.
Score: 10.112779201155005
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Unlike nonconvex optimization, where gradient descent is guaranteed to converge to a local optimizer, algorithms for nonconvex-nonconcave minimax optimization can have topologically different solution paths: sometimes converging to a solution, sometimes never converging and instead following a limit cycle, and sometimes diverging. In this paper, we study the limiting behaviors of three classic minimax algorithms: gradient descent ascent (GDA), alternating gradient descent ascent (AGDA), and the extragradient method (EGM). Numerically, we observe that all of these limiting behaviors can arise in Generative Adversarial Networks (GAN) training and are easily demonstrated for a range of GAN problems. To explain these different behaviors, we study the high-order resolution continuous-time dynamics that correspond to each algorithm, which results in the sufficient (and almost necessary) conditions for the local convergence by each method. Moreover, this ODE perspective allows us to characterize the phase transition between these different limiting behaviors caused by introducing regularization as Hopf Bifurcations.