Nest Your Adaptive Algorithm for Parameter-Agnostic Nonconvex Minimax Optimization
Adaptive algorithms like AdaGrad and AMSGrad are successful in nonconvex
optimization owing to their parameter-agnostic ability -- requiring no a priori
knowledge about problem-specific parameters nor tuning of learning rates.
However, when it comes to nonconvex minimax optimization, direct extensions of
such adaptive optimizers without proper time-scale separation may fail to work
in practice. We provide such an example proving that the simple combination of
Gradient Descent Ascent (GDA) with adaptive stepsizes can diverge if the
primal-dual stepsize ratio is not carefully chosen; hence, a fortiori, such
adaptive extensions are not parameter-agnostic. To address the issue, we
formally introduce a Nested Adaptive framework, NeAda for short, that carries
an inner loop for adaptively maximizing the dual variable with controllable
stopping criteria and an outer loop for adaptively minimizing the primal
variable. Such mechanism can be equipped with off-the-shelf adaptive optimizers
and automatically balance the progress in the primal and dual variables.
Theoretically, for nonconvex-strongly-concave minimax problems, we show that
NeAda can achieve the near-optimal $\tilde{O}(\epsilon^{-2})$ and
$\tilde{O}(\epsilon^{-4})$ gradient complexities respectively in the
deterministic and stochastic settings, without prior information on the
problem's smoothness and strong concavity parameters. To the best of our
knowledge, this is the first algorithm that simultaneously achieves
near-optimal convergence rates and parameter-agnostic adaptation in the
nonconvex minimax setting. Numerically, we further illustrate the robustness of
the NeAda family with experiments on simple test functions and a real-world
application.