Proximal Gradient Descent-Ascent: Variable Convergence under KŁ Geometry
This work provides the first theoretical result on variable convergence for nonconvex minimax optimization, which is crucial for practitioners using GDA in complex, non-convex settings where only function value or gradient norm convergence was previously understood.
This paper investigates the convergence of proximal gradient descent-ascent (proximal-GDA) for regularized nonconvex-strongly-concave minimax optimization. It establishes that proximal-GDA achieves variable convergence to a critical point and demonstrates various convergence rates, from sublinear to finite-step, depending on the KŁ geometry.
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 KŁ 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., $x_t\to x^*, y_t\to y^*(x^*)$. Furthermore, over the full spectrum of the KŁ-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 KŁ parameter. This is the first theoretical result on the variable convergence for nonconvex minimax optimization.