AdaGDA: Faster Adaptive Gradient Descent Ascent Methods for Minimax Optimization

Abstract

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 $\tilde{O}({\kappa }^4{\epsilon }^{-4})$ for finding an $\epsilon$-stationary point without large batches, which improves the existing results of the adaptive GDA methods by a factor of $O(\sqrt{\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 $\tilde{O}({\kappa }^{4.5}{\epsilon }^{-3})$ for finding an $\epsilon$-stationary point without large batches, which improves the existing results of the adaptive GDA methods by a factor of $O({\epsilon }^{-1})$. Moreover, we prove that our VR-AdaGDA method can reach the best known gradient complexity of $\tilde{O}({\kappa }^3{\epsilon }^{-3})$ with the mini-batch size $O({\kappa }^3)$. The experiments on policy evaluation and fair classifier learning tasks are conducted to verify the efficiency of our new algorithms.

arXiv commentTo appear in AISTATS 2023

References in corpus (16)

• Decoupled Weight Decay Regularization
• Communication-Efficient Learning of Deep Networks from Decentralized Data
• On the Convergence of Adam and Beyond
• SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator
• On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems
• AdaGrad stepsizes: Sharp convergence over nonconvex landscapes
• Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods
• Near-Optimal Algorithms for Minimax Optimization
• Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problems
• Optimal Epoch Stochastic Gradient Descent Ascent Methods for Min-Max Optimization
• Accelerated Zeroth-Order and First-Order Momentum Methods from Mini to Minimax Optimization
• Distributionally Robust Federated Averaging
• The Complexity of Nonconvex-Strongly-Concave Minimax Optimization
• Complexity Lower Bounds for Nonconvex-Strongly-Concave Min-Max Optimization
• SUPER-ADAM: Faster and Universal Framework of Adaptive Gradients
• BiAdam: Fast Adaptive Bilevel Optimization Methods

Cited by in corpus (1)

• Enhanced Bilevel Optimization via Bregman Distance