On Convergence of Gradient Descent Ascent: A Tight Local Analysis

mainstream algorithms for minimax optimization in generative adversarial networks (GANs). Convergence properties of GDA have drawn significant interest in the recent literature. Specifically, for min(x) max(y) f (x; y) where f is strongly-concave in y and possibly nonconvex in x, (Lin et al., 2020) proved the convergence of GDA with a stepsize ratio eta(y)/eta(x) = Theta(kappa(2)) where eta(x) and eta(y) are the stepsizes for x and y and kappa is the condition number for y. While this stepsize ratio suggests a slow training of the min player, practical GAN algorithms typically adopt similar stepsizes for both variables, indicating a wide gap between theoretical and empirical results. In this paper, we aim to bridge this gap by analyzing the local convergence of general nonconvex-nonconcave minimax problems. We demonstrate that a step-size ratio of Theta(kappa) is necessary and sufficient for local convergence of GDA to a Stackelberg Equilibrium, where kappa is the local condition number for y. We prove a nearly tight convergence rate with a matching lower bound. We further extend the convergence guarantees to stochastic GDA and extra-gradient methods (EG). Finally, we conduct several numerical experiments to support our theoretical findings.