AdaGDA: Faster Adaptive Gradient Descent Ascent Methods for Minimax Optimization

Feihu Huang, Xidong Wu, Zhengmian HuAISTATS 2023 · OpenReview

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 the coordinate-wise and global adaptive learning rates. Specifically, we first propose a new adaptive GDA method (AdaGDA) and prove its gradient complexity of $\tilde{O}(\kappa^4 \epsilon^{-4})$ for finding an $\epsilon$-stationary point. Then, we propose an accelerated adaptive GDA method (VR-AdaGDA) by using the variance reduction technique, and prove its gradient complexity of $\tilde{O}(\kappa^{4.5} \epsilon^{-3})$, which improves the existing best gradient complexity of adaptive minimax algorithms by a factor of $O(1/\epsilon)$.

Introduction

Minimax optimization—the process of finding a saddle point where one player minimizes a function while another maximizes it—serves as the mathematical foundation for several critical AI applications, including Generative Adversarial Networks (GANs), policy evaluation in Reinforcement Learning, and Robust Federated Learning.

Despite its importance, solving these problems is notoriously difficult, particularly when the objective is nonconvex in the minimization variable ($x$) and strongly concave in the maximization variable ($y$). While adaptive methods like Adam have become the standard for traditional minimization, extending their benefits to minimax settings has proven challenging. Existing adaptive minimax algorithms often only adapt the $x$ variable or suffer from high gradient complexity. This work introduces a framework that utilizes adaptive learning rates for both variables while simultaneously improving theoretical convergence bounds.

Proposed Methods

The authors introduce two primary algorithms designed to address the limitations of current adaptive minimax solvers:

  1. AdaGDA (Adaptive Gradient Descent Ascent): This method utilizes unified adaptive matrices ($A_t$ and $B_t$) to scale gradients for both $x$ and $y$. This approach allows for both coordinate-wise and global adaptive learning rates, providing the flexibility required for diverse neural network architectures.
  2. VR-AdaGDA (Variance-Reduced AdaGDA): This version incorporates the STochastic Recursive Momentum (STORM) variance reduction technique. By "denoising" stochastic gradient estimates, VR-AdaGDA achieves faster convergence without the need for excessively large mini-batch sizes.

A key contribution of this framework is the unified convergence analysis for two-sided adaptation, a significant advancement over previous methods like PDAda that only adapted the minimization variable.

Theoretical Results and Complexity

The proposed methods achieve significant breakthroughs in gradient complexity. AdaGDA reaches an $\epsilon$-stationary point with a complexity of $\tilde{O}(\kappa^4 \epsilon^{-4})$, which improves upon existing adaptive results by a factor of $O(\sqrt{\kappa})$, where $\kappa$ represents the condition number.

Comparison of gradient complexities and algorithm features for various minimax optimization methods.

As illustrated in the table above, VR-AdaGDA further improves this to $\tilde{O}(\kappa^{4.5} \epsilon^{-3})$, representing a massive $O(1/\epsilon)$ improvement over prior adaptive methods. Furthermore, with a specific mini-batch size of $O(\kappa^3)$, VR-AdaGDA can reach a gradient complexity of $\tilde{O}(\kappa^3 \epsilon^{-3})$, matching the best-known results for non-adaptive accelerated methods while maintaining the benefits of adaptation.

Experimental Evaluation

The researchers evaluated AdaGDA and VR-AdaGDA across two distinct domains:

  • Policy Evaluation (Reinforcement Learning): Experiments were conducted using 10,000 state-reward pairs from OpenAI Gym environments: CartPole-v1, Acrobat-v1, and MountainCarContinuous-v0.
  • Fair Classifier Learning: A robust optimization task aimed at minimizing the maximum loss across categories to ensure fairness. Benchmarks included MNIST, Fashion-MNIST, and CIFAR-10.
CNN architecture used for fair classification tasks on image benchmarks.

In these experiments, VR-AdaGDA consistently outperformed standard stochastic methods, converging to lower loss values more rapidly. For instance, in the MountainCar environment, the proposed methods exhibited significantly smoother and faster descent compared to the high-variance oscillations characteristic of standard SGDA.

Conclusion and Future Work

While AdaGDA and VR-AdaGDA represent a significant step forward, several avenues for future research remain. The current analysis assumes strong concavity in the $y$ variable; extending these results to general concave settings is a key challenge. Additionally, like most adaptive methods, these algorithms introduce hyperparameters that may require tuning for specific tasks. Finally, exploring the behavior of these methods in unconstrained settings or on Riemannian manifolds could further broaden their applicability.

Summary updated

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 i...
BibTeX
@inproceedings{huang2023adagda,
  author = {Feihu Huang and Xidong Wu and Zhengmian Hu},
  title = {{AdaGDA: Faster Adaptive Gradient Descent Ascent Methods for Minimax Optimization}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2023},
  url = {https://openreview.net/forum?id=1JBCPJ3I4l},
}
Figure