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{\L} 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{\L}-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{\L} parameter.
This is the first theoretical result on the variable convergence for nonconvex
minimax optimization.

本文研究了一种更为广泛的两人博弈非凸强凹优化的收敛性，在 K-L 参数化几何全谱上，证明了 Proximal-GDA 算法的收敛速率是不同的，这是首个关于非凸极小极大优化变量收敛的理论结果。

KŁ几何下的近端梯度下降 - 上升算法：可变收敛

Proximal Gradient Descent-Ascent: Variable Convergence under KŁ  Geometry

Nonconvex-concave min-max problem arises in many machine learning
applications including minimizing a pointwise maximum of a set of nonconvex
functions and robust adversarial training of neural networks. A popular
approach to solve this problem is the gradient descent-ascent (GDA) algorithm
which unfortunately can exhibit oscillation in case of nonconvexity. In this
paper, we introduce a "smoothing" scheme which can be combined with GDA to
stabilize the oscillation and ensure convergence to a stationary solution. We
prove that the stabilized GDA algorithm can achieve an $O(1/\epsilon^2)$
iteration complexity for minimizing the pointwise maximum of a finite
collection of nonconvex functions. Moreover, the smoothed GDA algorithm
achieves an $O(1/\epsilon^4)$ iteration complexity for general
nonconvex-concave problems. Extensions of this stabilized GDA algorithm to
multi-block cases are presented. To the best of our knowledge, this is the
first algorithm to achieve $O(1/\epsilon^2)$ for a class of nonconvex-concave
problem. We illustrate the practical efficiency of the stabilized GDA algorithm
on robust training.

该研究介绍了一种与梯度下降上升（GDA）算法相结合的 “平滑” 方案，以解决非凸 - 凹最小 - 最大问题，此方案能够稳定振荡，并确保收敛到一个定值解。实验结果表明，平滑后的 GDA 算法对于 minimizing pointwise maximum of a finite collection of nonconvex functions 可以实现 O (1/ε^2) 的迭代复杂度，对于 general nonconvex-concave problems 可以实现 O (1/ε^4) 的迭代复杂度，并且将该算法扩展到多个区块的情况下。