On Convergence of Gradient Descent Ascent: A Tight Local Analysis
Gradient Descent Ascent (GDA) methods are the 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_{\mathbf{x}} \max_{\mathbf{y}}
f(\mathbf{x};\mathbf{y})$ where $f$ is strongly-concave in $\mathbf{y}$ and
possibly nonconvex in $\mathbf{x}$, (Lin et al., 2020) proved the convergence
of GDA with a stepsize ratio
$\eta_{\mathbf{y}}/\eta_{\mathbf{x}}=\Theta(\kappa^2)$ where
$\eta_{\mathbf{x}}$ and $\eta_{\mathbf{y}}$ are the stepsizes for $\mathbf{x}$
and $\mathbf{y}$ and $\kappa$ is the condition number for $\mathbf{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 \emph{local convergence} of general
\emph{nonconvex-nonconcave} minimax problems. We demonstrate that a stepsize
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 $\mathbf{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.