# Proximal Gradient Descent-Ascent: Variable Convergence under KL Geometry arXiv: https://arxiv.org/abs/2102.04653 · HTML: https://mlsanity.com/paper/2102.04653/ ## Key facts - Cited by 18 papers in the map (data through 14 Oct 2026). - Builds on 24 of its 47 references that are in the map. - First posted on arXiv 9 Feb 2021. ## Builds on (most cited first, 24 of 24) - [Generative Adversarial Imitation Learning](https://mlsanity.com/paper/1606.03476/) (2016) - [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016) - [Certifying Some Distributional Robustness with Principled Adversarial Training](https://mlsanity.com/paper/1710.10571/) (2017) - [On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems](https://mlsanity.com/paper/1906.00331/) (2019) - [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) - [The Limit Points of (Optimistic) Gradient Descent in Min-Max Optimization](https://mlsanity.com/paper/1807.03907/) (2018) - [Multi-Agent Generative Adversarial Imitation Learning](https://mlsanity.com/paper/1807.09936/) (2018) - [A Unified Single-loop Alternating Gradient Projection Algorithm for Nonconvex-Concave and Convex-Nonconcave Minimax Problems](https://mlsanity.com/paper/2006.02032/) (2020) - [Hybrid Block Successive Approximation for One-Sided Non-Convex Min-Max Problems: Algorithms and Applications](https://mlsanity.com/paper/1902.08294/) (2019) - [Linear Convergence of the Primal-Dual Gradient Method for Convex-Concave Saddle Point Problems without Strong Convexity](https://mlsanity.com/paper/1802.01504/) (2018) - [Local Saddle Point Optimization: A Curvature Exploitation Approach](https://mlsanity.com/paper/1805.05751/) (2018) - [Splitting methods with variable metric for KL functions](https://mlsanity.com/paper/1405.1357/) (2014) - [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) - [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) - [Distributed Proximal Gradient Algorithm for Partially Asynchronous Computer Clusters](https://mlsanity.com/paper/1704.03540/) (2017) - [Characterization of Gradient Dominance and Regularity Conditions for Neural Networks](https://mlsanity.com/paper/1710.06910/) (2017) - [Convergence of Cubic Regularization for Nonconvex Optimization under KL Property](https://mlsanity.com/paper/1808.07382/) (2018) - [On the Quadratic Convergence of the Cubic Regularization Method under a Local Error Bound Condition](https://mlsanity.com/paper/1801.09387/) (2018) - [Proximal Gradient Algorithm with Momentum and Flexible Parameter Restart for Nonconvex Optimization](https://mlsanity.com/paper/2002.11582/) (2020) ## Built on by (most cited first, 18 of 18) - [Lisa: Lazy Safety Alignment for Large Language Models against Harmful Fine-tuning Attack](https://mlsanity.com/paper/2405.18641/) (2024) - [Federated Minimax Optimization: Improved Convergence Analyses and Algorithms](https://mlsanity.com/paper/2203.04850/) (2022) - [Fusion of Global and Local Knowledge for Personalized Federated Learning](https://mlsanity.com/paper/2302.11051/) (2023) - [AdaGDA: Faster Adaptive Gradient Descent Ascent Methods for Minimax Optimization](https://mlsanity.com/paper/2106.16101/) (2021) - [Nonsmooth Nonconvex-Nonconcave Minimax Optimization: Primal-Dual Balancing and Iteration Complexity Analysis](https://mlsanity.com/paper/2209.10825/) (2022) - [A first-order augmented Lagrangian method for constrained minimax optimization](https://mlsanity.com/paper/2301.02060/) (2023) - [Federated Minimax Optimization with Client Heterogeneity](https://mlsanity.com/paper/2302.04249/) (2023) - [A Fast and Convergent Proximal Algorithm for Regularized Nonconvex and Nonsmooth Bi-level Optimization](https://mlsanity.com/paper/2203.16615/) (2022) - [Enhanced Adaptive Gradient Algorithms for Nonconvex-PL Minimax Optimization](https://mlsanity.com/paper/2303.03984/) (2023) - [A Cubic Regularization Approach for Finding Local Minimax Points in Nonconvex Minimax Optimization](https://mlsanity.com/paper/2110.07098/) (2021) - [Adaptive Federated Minimax Optimization with Lower Complexities](https://mlsanity.com/paper/2211.07303/) (2022) - [Accelerated Proximal Alternating Gradient-Descent-Ascent for Nonconvex Minimax Machine Learning](https://mlsanity.com/paper/2112.11663/) (2021) - [Near-Optimal Decentralized Momentum Method for Nonconvex-PL Minimax Problems](https://mlsanity.com/paper/2304.10902/) (2023) - [Randomized Stochastic Gradient Descent Ascent](https://mlsanity.com/paper/2111.13162/) (2021) - [Stability and Generalization of Differentially Private Minimax Problems](https://mlsanity.com/paper/2204.04858/) (2022) - [Stability and Generalization for Distributed SGDA](https://mlsanity.com/paper/2411.09365/) (2024) - [A first-order method for nonconvex-strongly-concave constrained minimax optimization](https://mlsanity.com/paper/2512.22909/) (2025) - [The Role of Gradient Modification in Heavy-Tailed Nonconvex Stochastic Min-Max Optimization](https://mlsanity.com/paper/2609.06064/) (2026) ## Abstract (arXiv) The gradient descent-ascent (GDA) algorithm has been widely applied to solve minimax optimization problems. In order to achieve convergent policy parameters for minimax optimization, it is important that GDA generates convergent variable sequences rather than convergent sequences of function values or gradient norms. However, the variable convergence of GDA has been proved only under convexity geometries, and there lacks understanding for general nonconvex minimax optimization. This paper fills such a gap by studying the convergence of a more general proximal-GDA for regularized nonconvex-strongly-concave minimax optimization. Specifically, we show that proximal-GDA admits a novel Lyapunov function, which monotonically decreases in the minimax optimization process and drives the variable sequence to a critical point. By leveraging this Lyapunov function and the KL geometry that parameterizes the local geometries of general nonconvex functions, we formally establish the variable convergence of proximal-GDA to a critical point x^*, i.e., xt→ x^*, yt→ y^*(x^*). Furthermore, over the full spectrum of the KL-parameterized geometry, we show that proximal-GDA achieves different types of convergence rates ranging from sublinear convergence up to finite-step convergence, depending on the geometry associated with the KL parameter. This is the first theoretical result on the variable convergence for nonconvex minimax optimization.