# Accelerated Proximal Alternating Gradient-Descent-Ascent for Nonconvex Minimax Machine Learning

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 49 references that are in the map.
- First posted on arXiv 22 Dec 2021.

## Builds on (most cited first, 28 of 28)

- [Certifying Some Distributional Robustness with Principled Adversarial Training](https://mlsanity.com/paper/1710.10571/) (2017)
- [Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods](https://mlsanity.com/paper/1902.08297/) (2019)
- [A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approach](https://mlsanity.com/paper/1901.08511/) (2019)
- [Near-Optimal Algorithms for Minimax Optimization](https://mlsanity.com/paper/2002.02417/) (2020)
- [The Limit Points of (Optimistic) Gradient Descent in Min-Max Optimization](https://mlsanity.com/paper/1807.03907/) (2018)
- [Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problems](https://mlsanity.com/paper/2001.03724/) (2020)
- [Accelerated Gradient Methods for Nonconvex Nonlinear and Stochastic Programming](https://mlsanity.com/paper/1310.3787/) (2013)
- [Negative Momentum for Improved Game Dynamics](https://mlsanity.com/paper/1807.04740/) (2018)
- [A Unified Single-loop Alternating Gradient Projection Algorithm for Nonconvex-Concave and Convex-Nonconcave Minimax Problems](https://mlsanity.com/paper/2006.02032/) (2020)
- [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)
- [On Solving Minimax Optimization Locally: A Follow-the-Ridge Approach](https://mlsanity.com/paper/1910.07512/) (2019)
- [Improved Algorithms for Convex-Concave Minimax Optimization](https://mlsanity.com/paper/2006.06359/) (2020)
- [iPiano: Inertial Proximal Algorithm for Non-Convex Optimization](https://mlsanity.com/paper/1404.4805/) (2014)
- [Linear Convergence of the Primal-Dual Gradient Method for Convex-Concave Saddle Point Problems without Strong Convexity](https://mlsanity.com/paper/1802.01504/) (2018)
- [Finite Regret and Cycles with Fixed Step-Size via Alternating Gradient Descent-Ascent](https://mlsanity.com/paper/1907.04392/) (2019)
- [Local Saddle Point Optimization: A Curvature Exploitation Approach](https://mlsanity.com/paper/1805.05751/) (2018)
- [Alternating proximal-gradient steps for (stochastic) nonconvex-concave minimax problems](https://mlsanity.com/paper/2007.13605/) (2020)
- [Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning](https://mlsanity.com/paper/2008.10103/) (2020)
- [Saddle-point dynamics: conditions for asymptotic stability of saddle points](https://mlsanity.com/paper/1510.02145/) (2015)
- [Convergence Analysis of Proximal Gradient with Momentum for Nonconvex Optimization](https://mlsanity.com/paper/1705.04925/) (2017)
- [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)
- [Stabilizing Adversarial Nets With Prediction Methods](https://mlsanity.com/paper/1705.07364/) (2017)
- [An Optimal Multistage Stochastic Gradient Method for Minimax Problems](https://mlsanity.com/paper/2002.05683/) (2020)
- [Gradient Free Minimax Optimization: Variance Reduction and Faster Convergence](https://mlsanity.com/paper/2006.09361/) (2020)
- [On the Suboptimality of Negative Momentum for Minimax Optimization](https://mlsanity.com/paper/2008.07459/) (2020)
- [Local Convergence of the Heavy-ball Method and iPiano for Non-convex Optimization](https://mlsanity.com/paper/1606.09070/) (2016)

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

- [Tight Analysis of Extra-gradient and Optimistic Gradient Methods For Nonconvex Minimax Problems](https://mlsanity.com/paper/2210.09382/) (2022)
- [Improving Generalization via Meta-Learning on Hard Samples](https://mlsanity.com/paper/2403.12236/) (2024)
- [Variance-reduced accelerated methods for decentralized stochastic double-regularized nonconvex strongly-concave minimax problems](https://mlsanity.com/paper/2307.07113/) (2023)
- [On the Optimal Construction of Unbiased Gradient Estimators for Zeroth-Order Optimization](https://mlsanity.com/paper/2510.19953/) (2025)

## Abstract (arXiv)

Alternating gradient-descent-ascent (AltGDA) is an optimization algorithm that has been widely used for model training in various machine learning applications, which aims to solve a nonconvex minimax optimization problem. However, the existing studies show that it suffers from a high computation complexity in nonconvex minimax optimization. In this paper, we develop a single-loop and fast AltGDA-type algorithm that leverages proximal gradient updates and momentum acceleration to solve regularized nonconvex minimax optimization problems. By leveraging the momentum acceleration technique, we prove that the algorithm converges to a critical point in nonconvex minimax optimization and achieves a computation complexity in the order of O(kappa^frac116ε-2), where ε is the desired level of accuracy and kappa is the problem's condition number. Such a computation complexity improves the state-of-the-art complexities of single-loop GDA and AltGDA algorithms (see the summary of comparison in Creftable1). We demonstrate the effectiveness of our algorithm via an experiment on adversarial deep learning.