# AdaGDA: Faster Adaptive Gradient Descent Ascent Methods for Minimax Optimization

arXiv: https://arxiv.org/abs/2106.16101 · HTML: https://mlsanity.com/paper/2106.16101/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 55 references that are in the map.
- First posted on arXiv 30 Jun 2021.

## Builds on (most cited first, 30 of 32)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [OpenAI Gym](https://mlsanity.com/paper/1606.01540/) (2016)
- [On the Convergence of Adam and Beyond](https://mlsanity.com/paper/1904.09237/) (2019)
- [Ensemble Adversarial Training: Attacks and Defenses](https://mlsanity.com/paper/1705.07204/) (2017)
- [Lower Bounds for Non-Convex Stochastic Optimization](https://mlsanity.com/paper/1912.02365/) (2019)
- [Momentum-Based Variance Reduction in Non-Convex SGD](https://mlsanity.com/paper/1905.10018/) (2019)
- [SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator](https://mlsanity.com/paper/1807.01695/) (2018)
- [AdaBelief Optimizer: Adapting Stepsizes by the Belief in Observed Gradients](https://mlsanity.com/paper/2010.07468/) (2020)
- [On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems](https://mlsanity.com/paper/1906.00331/) (2019)
- [AdaGrad stepsizes: Sharp convergence over nonconvex landscapes](https://mlsanity.com/paper/1806.01811/) (2018)
- [On the Convergence of A Class of Adam-Type Algorithms for Non-Convex Optimization](https://mlsanity.com/paper/1808.02941/) (2018)
- [On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizes](https://mlsanity.com/paper/1805.08114/) (2018)
- [Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods](https://mlsanity.com/paper/1902.08297/) (2019)
- [Mini-batch Stochastic Approximation Methods for Nonconvex Stochastic Composite Optimization](https://mlsanity.com/paper/1308.6594/) (2013)
- [Near-Optimal Algorithms for Minimax Optimization](https://mlsanity.com/paper/2002.02417/) (2020)
- [Distributionally Robust Federated Averaging](https://mlsanity.com/paper/2102.12660/) (2021)
- [Robust Federated Learning: The Case of Affine Distribution Shifts](https://mlsanity.com/paper/2006.08907/) (2020)
- [Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problems](https://mlsanity.com/paper/2001.03724/) (2020)
- [Weakly-Convex Concave Min-Max Optimization: Provable Algorithms and Applications in Machine Learning](https://mlsanity.com/paper/1810.02060/) (2018)
- [Hybrid Block Successive Approximation for One-Sided Non-Convex Min-Max Problems: Algorithms and Applications](https://mlsanity.com/paper/1902.08294/) (2019)
- [The Complexity of Nonconvex-Strongly-Concave Minimax Optimization](https://mlsanity.com/paper/2103.15888/) (2021)
- [Accelerated Zeroth-Order and First-Order Momentum Methods from Mini to Minimax Optimization](https://mlsanity.com/paper/2008.08170/) (2020)
- [SUPER-ADAM: Faster and Universal Framework of Adaptive Gradients](https://mlsanity.com/paper/2106.08208/) (2021)
- [Complexity Lower Bounds for Nonconvex-Strongly-Concave Min-Max Optimization](https://mlsanity.com/paper/2104.08708/) (2021)
- [First-order Convergence Theory for Weakly-Convex-Weakly-Concave Min-max Problems](https://mlsanity.com/paper/1810.10207/) (2018)
- [BiAdam: Fast Adaptive Bilevel Optimization Methods](https://mlsanity.com/paper/2106.11396/) (2021)
- [Zeroth-Order Algorithms for Nonconvex Minimax Problems with Improved Complexities](https://mlsanity.com/paper/2001.07819/) (2020)
- [Proximal Gradient Descent-Ascent: Variable Convergence under KL Geometry](https://mlsanity.com/paper/2102.04653/) (2021)
- [Gradient Descent Ascent for Minimax Problems on Riemannian Manifolds](https://mlsanity.com/paper/2010.06097/) (2020)

## Built on by (most cited first, 13 of 13)

- [Faster Single-loop Algorithms for Minimax Optimization without Strong Concavity](https://mlsanity.com/paper/2112.05604/) (2021)
- [Enhanced Bilevel Optimization via Bregman Distance](https://mlsanity.com/paper/2107.12301/) (2021)
- [Nest Your Adaptive Algorithm for Parameter-Agnostic Nonconvex Minimax Optimization](https://mlsanity.com/paper/2206.00743/) (2022)
- [Solving a Class of Non-Convex Minimax Optimization in Federated Learning](https://mlsanity.com/paper/2310.03613/) (2023)
- [TiAda: A Time-scale Adaptive Algorithm for Nonconvex Minimax Optimization](https://mlsanity.com/paper/2210.17478/) (2022)
- [Decentralized Riemannian Algorithm for Nonconvex Minimax Problems](https://mlsanity.com/paper/2302.03825/) (2023)
- [Enhanced Adaptive Gradient Algorithms for Nonconvex-PL Minimax Optimization](https://mlsanity.com/paper/2303.03984/) (2023)
- [Adaptive Federated Minimax Optimization with Lower Complexities](https://mlsanity.com/paper/2211.07303/) (2022)
- [Near-Optimal Decentralized Momentum Method for Nonconvex-PL Minimax Problems](https://mlsanity.com/paper/2304.10902/) (2023)
- [Faster Stochastic Variance Reduction Methods for Compositional MiniMax Optimization](https://mlsanity.com/paper/2308.09604/) (2023)
- [Electroencephalogram Emotion Recognition via AUC Maximization](https://mlsanity.com/paper/2408.08979/) (2024)
- [Adaptive Algorithms with Sharp Convergence Rates for Stochastic Hierarchical Optimization](https://mlsanity.com/paper/2509.15399/) (2025)
- [Achieving Near-Optimal Convergence for Distributed Minimax Optimization with Adaptive Stepsizes](https://mlsanity.com/paper/2406.02939/) (2024)

## Abstract (arXiv)

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.