AdaGDA: Faster Adaptive Gradient Descent Ascent Methods for Minimax Optimization

In the paper, we propose a class of faster adaptive Gradient Descent Ascent (GDA) methods for solving the nonconvex-strongly-concave minimax problems by using the unified adaptive matrices, which include almost all existing coordinate-wise and global adaptive learning rates. In particular, we provide an effective convergence analysis framework for our adaptive GDA methods. Specifically, we propose a fast Adaptive Gradient Descent Ascent (AdaGDA) method based on the basic momentum technique, which reaches a lower gradient complexity of tildeO(kappa4ε-4) for finding an ε-stationary point without large batches, which improves the existing results of the adaptive GDA methods by a factor of O(√kappa). Moreover, we propose an accelerated version of AdaGDA (VR-AdaGDA) method based on the momentum-based variance reduced technique, which achieves a lower gradient complexity of tildeO(kappa4.5ε-3) for finding an ε-stationary point without large batches, which improves the existing results of the adaptive GDA methods by a factor of O(ε-1). Moreover, we prove that our VR-AdaGDA method can reach the best known gradient complexity of tildeO(kappa3ε-3) with the mini-batch size O(kappa3). The experiments on policy evaluation and fair classifier learning tasks are conducted to verify the efficiency of our new algorithms.