Proximal Gradient Descent-Ascent: Variable Convergence under KŁ Geometry
Proximal Gradient Descent-Ascent: Variable Convergence under KŁ Geometry
复制标题
DOI：
--
复制
发表时间：
2021-02
期刊：
影响因子：
--
通讯作者：
Ziyi Chen;Yi Zhou;Tengyu Xu;Yingbin Liang
中科院分区：
文献类型：
--
作者：
Ziyi Chen;Yi Zhou;Tengyu Xu;Yingbin Liang
梯度下降-上升（GDA）算法在求解极大极小优化问题中得到了广泛的应用。为了实现极小极大优化的收敛策略参数，GDA生成收敛变量序列而不是函数值或梯度范数的收敛序列是重要的。然而，GDA的变收敛性仅在凸几何下得到了证明，对一般的非凸极大极小优化缺乏理解。本文通过研究正则化非凸-强-凹极大极小优化的更一般的近似GDA的收敛性，填补了这一空白。具体来说，我们表明，近似GDA承认一个新的李雅普诺夫函数，单调下降的极大极小优化过程中，并驱动变量序列的临界点。通过利用这个李雅普诺夫函数和参数化一般非凸函数的局部几何的K{\L}几何，我们正式建立了近似GDA到临界点x^*$的变量收敛，即，$x_t\to x^*，y_t\to y^*（x^*）$。此外，在K{\L}参数化几何的全谱上，我们表明，近似GDA实现了不同类型的收敛速度，从次线性收敛到有限步收敛，这取决于与K{\L}参数相关联的几何。这是第一个关于非凸极大极小优化的变量收敛性的理论结果。
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.