一种求解凸-PL极小极大优化问题的随机交替梯度投影算法

A Stochastic Alternating Gradient Projection Algorithm for Convex-PL Minimax Optimization Problems

摘要: 针对机器学习中常见的一类非凸极小极大优化问题，本文提出了一种新的随机交替梯度投影算法，该算法基于交替梯度投影算法，在随机环境中用随机梯度进行更新，和随机交替梯度下降–上升算法相比，运算效率大大提高。在高斯分布数据集上的数值实验结果表明新算法是可行有效的。

Abstract: To solve a class of nonconvex minimax optimization problems in machine learning, we propose a new stochastic alternating gradient projection algorithm (SAGP). This algorithm is based on the alternating gradient projection algorithm (AGP), which is updated with stochastic gradients in a stochastic environment. Compared with the stochastic alternating gradient descent ascent algorithm (SAGDA), the operation efficiency is greatly improved. Numerical experiments on Gaussian distributed data sets show that the new algorithm is feasible and effective.

1. 引言

本文考虑以下极小极大优化问题：

$\underset{x\in R^n}{\min }\underset{y\in R^m}{\max }f(x,y)\triangleq {\rm E}\left[F(x,y;\xi )\right]$ ，

其中 $\xi$ 是具有支持度 $\Xi$ 的随机向量， $f(x,y)$ 是光滑函数， $f(x,y)$ 对于 $x$ 是凸的，对于 $y$ 是非凹的。

在机器学习中，许多问题都可表述为 $\underset{x}{\min }\underset{y}{\max }f(x,y)$ 的形式，如生成性对抗网络(GAN)、分布式非凸优化、多域鲁棒学习、信号处理中的功率控制和收发器设计问题等。求解此类问题最简单的方法之一是梯度下降(GD)的自然泛化，称为梯度下降–上升(GDA)算法，在每次迭代时通过同步或交替的渐变更新来对 $x$ 执行梯度下降步骤，对 $y$ 执行梯度上升步骤。

凸–凹极小极大优化问题对应的变分不等式是单调算子，目前已有较好的成果 [1] [2] [3] [4] [5] 。非凸极小极大优化问题，包括非凸–凹、凸–非凹、非凸–非凹极小极大优化问题，由于其非凸性、非凹性和非光滑性的特殊结构，一般是NP-难的，目前已有一些理论成果。在非凸–凹环境下，求解此类问题的算法有两类，分别是嵌套循环算法 [6] [7] [8] [9] [10] 和单循环算法。单循环算法多基于GDA算法改进，如two-time-scale GDA and stochastic GDA算法 [11] ，GDmax算法 [12] ，混合块逐次逼近算法(HiBSA) [13] ，交替梯度投影算法(AGP) [14] ，proximal alternating GDA算法 [15] ，Smoothed-GDA算法 [16] ，Stoc-AGDA和Stoc-Smoothed-AGDA [17] 和其他改进的GDA算法 [18] [19] 。

在凸–非凹环境下，对于任意给定的 $x$ ，求解 $\underset{y}{\max }f(x,y)$ 是NP-难的。几乎现有的嵌套循环算法和部分现有的单循环算法 [12] [13] 都会失去理论保证，因为这些算法都需求解 $\underset{y}{\max }f(x,y)$ 。目前只有AGP算法 [14] 可求解目标函数 $f(x,y)$ 是光滑函数的凸–非凹极小极大优化问题，并证明了其收敛性。

凸–非凹极小极大优化问题的一类子问题是凸-PL极小极大优化问题，即 $f(x,y)$ 对于 $x$ 是凸的，对于 $y$ 是满足Polyak-Lojasiewicz(PL)条件的。PL条件最初是由Polyak [20] 引入，并证明了梯度下降以线性速率全局收敛。目标函数的变量 $y$ 满足PL条件的假设比 $y$ 具有强凹性的假设更温和，甚至不要求目标函数在 $y$ 上是凹的，这种假设在线性二次型调节器 [21] 和超参数化神经网络 [22] 中被证明成立。对于极小极大优化问题，有的研究 [17] 是使变量 $y$ 满足PL条件，有的研究 [23] [24] 则是通过使 $x$ 满足PL条件来找到全局解，同时PL条件被证明适用于机器学习中某些非凸应用 [21] [25] ，包括与深度神经网络相关的问题 [22] [26] ，因此PL条件引起了广泛的关注。

非凸–凹环境下，许多算法 [11] [27] 结合随机梯度都取得了较好的收敛结果。受启发于Stoc-Smoothed-AGDA算法 [17] ，本文考虑在凸-PL环境下，将随机梯度与AGP算法 [14] 相结合，从而提出了随机交替梯度投影算法(SAGP)。

2. 交替梯度投影算法

本节首先回顾交替梯度投影算法(AGP) [14] 。考虑以下极小极大优化问题：

$\underset{x\in X}{\min }\underset{y\in Y}{\max }f(x,y)$ ，

其中 $f:X\times Y\to R$ 是光滑函数， $X\subseteq R^n,Y\subseteq R^m$ 为非空闭凸集。

交替梯度投影算法是单循环算法，每次迭代通过两个梯度投影步骤更新 $x$ 和 $y$ 。在第 $t$ 次迭代中，AGP算法使用如下辅助函数的梯度进行更新，即：

$\hat{f}(x,y)=f(x,y)+\frac{b_t}{2}{\Vert x\Vert }^2-\frac{c_t}{2}{\Vert y\Vert }^2$ ，

其中 $b_t\ge 0$ 和 $c_t\ge 0$ 是正则化参数。在凸–非凹环境下， $c_t=0$ ， $\left\{b_t\right\}$ 是非负单调递减序列，以下给出交替梯度投影算法的框架：

算法1 交替梯度投影算法(AGP)

步骤1 输入固定步长 ${\tau }_1>0$ ， ${\tau }_2>0$ ，初始点 $(x_0,y_0)$ 及参数 $b_0>0$ ，

步骤2 计算 $b_t$ 并更新 $x_t$ ：

$x_{t+1}=P_X(x_t-{\tau }_1({\nabla }_{x}f(x_t,y_t)+b_t{x}_t))$ ，

步骤3 更新 $y_t$ ：

$y_{t+1}=P_Y(y_t+{\tau }_2{\nabla }_{y}f(x_{t+1},y_t))$ ，

步骤4 当算法满足终止准则时，停止；否则，令 $t=t+1$ ，返回步骤2。

3. PL条件

目标函数 $f(x,y)$ 在 $y$ 上的PL条件：对于任意固定的 $x$ ， $\underset{y}{\max }f(x,y)$ 有非空解集和有限最优值，存在 $\mu >0$ 使得 ${\Vert {\nabla }_{y}f(x,y)\Vert }^2\ge 2\mu \left[\underset{y}{\max }f(x,y)-f(x,y)\right],\forall x,y$ 。

4. 随机交替梯度投影算法

根据文献 [17] 所述，在随机环境中求解NC-PL极小极大优化问题，基于交替梯度下降–上升算法(AGDA)和Smoothed-AGDA算法 [16] ，采用随机梯度 $G_x(x,y,\xi )$ 和 $G_y(x,y,\xi )$ 进行更新，其中 $G_x(x,y,\xi )$ 和 $G_y(x,y,\xi )$ 分别是 ${\nabla }_{x}f(x,y)$ 和 ${\nabla }_{y}f(x,y)$ 的无偏随机估计且方差有界 ${\sigma }^2>0$ ，构造了新算法Stoc-AGDA和Stoc-Smoothed-AGDA。由于上述算法具有良好的数值表现，对于凸-PL极小极大优化问题，本文考虑将随机梯度结合到交替梯度投影算法(AGP)中，以下给出随机交替梯度投影算法的框架：

算法2 随机交替梯度投影算法(SAGP)

步骤1 输入固定步长 ${\tau }_1>0$ ， ${\tau }_2>0$ ，初始点 $(x_0,y_0)$ 及参数 $b_0>0$ ，

步骤2 for all $t=0,1,2,\cdots ,T-1$ do，

步骤3 抽取两个独立同分布样本 ${\xi }_1^t$ ， ${\xi }_2^t$ ，

步骤4 $x_{t+1}=x_t-{\tau }_1\left[G_x(x_t,y_t,{\xi }_1^t)+b_t{x}_t\right]$ ，

步骤5 $y_{t+1}=y_t+{\tau }_2{G}_y(x_{t+1},y_t,{\xi }_2^t)$ ，

步骤6 end for，

步骤7 随机从 ${\left\{(x_t,y_t)\right\}}_{t=0}^{T-1}$ 中均匀抽取 $(\tilde{x},\tilde{y})$ 。

5. 数值实验

本节将SAGP算法应用于求解具有线性生成器的Toy WGAN模型，本文设置与 [17] 相同，并给出实验结果验证了新算法的有效性，模型表示如下：

$\underset{\mu ,\sigma }{\min }\underset{{\varphi }_1,{\varphi }_2}{\max }F(\mu ,\sigma ,{\varphi }_1,{\varphi }_2)\triangleq {{\rm E}}_{(x^{real},z)\sim D}{D}_{\varphi }(x^{real})-D_{\varphi }(G_{\mu ,\sigma }(z))-\lambda {\Vert \varphi \Vert }^2$ ，

其中生成器为 $G_{\mu ,\sigma }(z)=\mu +\sigma z$ ，判别器为 $D_{\varphi }(x)={\varphi }_{1}x+{\varphi }_2{x}^2$ ， $x$ 是来自生成器的真实数据或假数据， $D$ 为真实数据和潜在变量的分布。真实数据 $x^{real}$ 和潜在变量 $z$ 的高斯分布数据集来自平均值为0、方差为1的正态分布， $x^{real}$ 产生于 $\hat{\mu }=0,\hat{\sigma }=0.1$ 。批量大小固定为100，实验重复3次。实验结果如图1所示。

图1对比了SAGP算法和SAGDA算法的收敛速度，其中 $x$ 轴代表迭代次数， $y$ 轴代表随机梯度范数取值范围的变化过程，其中RMSprop算法步长为5e−4，参数为0.9；Adam算法步长为5e−4，参数为0.5和0.9；SAGDA算法步长 ${\tau }_1$ = 1e−1， ${\tau }_2$ = 5e−1；SAGP算法步长 ${\tau }_1$ = 2e−1， ${\tau }_2$ = 8e−1。图1和图2分别对应于四种算法在高斯分布数据集上的实验结果对比。从图中可以看出，本文提出的新算法SAGP的收敛速度整体上比SAGDA算法快，有效地验证了新算法的可行性。

Figure 1. The change process of the range of the random gradient norm of the discriminator on the Gaussian distribution data set

图1. 在高斯分布数据集上判别器的随机梯度范数取值范围的变化过程

Figure 2. The change process of the value range of the random gradient norm of the generator on the Gaussian distribution data set

图2. 在高斯分布数据集上生成器的随机梯度范数取值范围的变化过程

6. 小结

本文在凸-PL环境下将交替梯度投影算法(AGP)与随机梯度相结合，提出了一种新的随机交替梯度投影算法(SAGP)。从实验结果分析来看，新算法在高斯分布数据集上优于SAGDA算法，从而验证了新算法的有效性和可行性。

基金项目

山西省基础研究计划(自由探索类)面上项目(202103021224303)；太原师范学院研究生教育创新项目(SYYJSYC-2287)。