1. 引言
本文考虑以下极小极大优化问题:
,
其中
是具有支持度
的随机向量,
是光滑函数,
对于
是凸的,对于
是非凹的。
在机器学习中,许多问题都可表述为
的形式,如生成性对抗网络(GAN)、分布式非凸优化、多域鲁棒学习、信号处理中的功率控制和收发器设计问题等。求解此类问题最简单的方法之一是梯度下降(GD)的自然泛化,称为梯度下降–上升(GDA)算法,在每次迭代时通过同步或交替的渐变更新来对
执行梯度下降步骤,对
执行梯度上升步骤。
凸–凹极小极大优化问题对应的变分不等式是单调算子,目前已有较好的成果 [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] 。
在凸–非凹环境下,对于任意给定的
,求解
是NP-难的。几乎现有的嵌套循环算法和部分现有的单循环算法 [12] [13] 都会失去理论保证,因为这些算法都需求解
。目前只有AGP算法 [14] 可求解目标函数
是光滑函数的凸–非凹极小极大优化问题,并证明了其收敛性。
凸–非凹极小极大优化问题的一类子问题是凸-PL极小极大优化问题,即
对于
是凸的,对于
是满足Polyak-Lojasiewicz(PL)条件的。PL条件最初是由Polyak [20] 引入,并证明了梯度下降以线性速率全局收敛。目标函数的变量
满足PL条件的假设比
具有强凹性的假设更温和,甚至不要求目标函数在
上是凹的,这种假设在线性二次型调节器 [21] 和超参数化神经网络 [22] 中被证明成立。对于极小极大优化问题,有的研究 [17] 是使变量
满足PL条件,有的研究 [23] [24] 则是通过使
满足PL条件来找到全局解,同时PL条件被证明适用于机器学习中某些非凸应用 [21] [25] ,包括与深度神经网络相关的问题 [22] [26] ,因此PL条件引起了广泛的关注。
非凸–凹环境下,许多算法 [11] [27] 结合随机梯度都取得了较好的收敛结果。受启发于Stoc-Smoothed-AGDA算法 [17] ,本文考虑在凸-PL环境下,将随机梯度与AGP算法 [14] 相结合,从而提出了随机交替梯度投影算法(SAGP)。
2. 交替梯度投影算法
本节首先回顾交替梯度投影算法(AGP) [14] 。考虑以下极小极大优化问题:
,
其中
是光滑函数,
为非空闭凸集。
交替梯度投影算法是单循环算法,每次迭代通过两个梯度投影步骤更新
和
。在第
次迭代中,AGP算法使用如下辅助函数的梯度进行更新,即:
,
其中
和
是正则化参数。在凸–非凹环境下,
,
是非负单调递减序列,以下给出交替梯度投影算法的框架:
算法1 交替梯度投影算法(AGP)
步骤1 输入固定步长
,
,初始点
及参数
,
步骤2 计算
并更新
:
,
步骤3 更新
:
,
步骤4 当算法满足终止准则时,停止;否则,令
,返回步骤2。
3. PL条件
目标函数
在
上的PL条件:对于任意固定的
,
有非空解集和有限最优值,存在
使得
。
4. 随机交替梯度投影算法
根据文献 [17] 所述,在随机环境中求解NC-PL极小极大优化问题,基于交替梯度下降–上升算法(AGDA)和Smoothed-AGDA算法 [16] ,采用随机梯度
和
进行更新,其中
和
分别是
和
的无偏随机估计且方差有界
,构造了新算法Stoc-AGDA和Stoc-Smoothed-AGDA。由于上述算法具有良好的数值表现,对于凸-PL极小极大优化问题,本文考虑将随机梯度结合到交替梯度投影算法(AGP)中,以下给出随机交替梯度投影算法的框架:
算法2 随机交替梯度投影算法(SAGP)
步骤1 输入固定步长
,
,初始点
及参数
,
步骤2 for all
do,
步骤3 抽取两个独立同分布样本
,
,
步骤4
,
步骤5
,
步骤6 end for,
步骤7 随机从
中均匀抽取
。
5. 数值实验
本节将SAGP算法应用于求解具有线性生成器的Toy WGAN模型,本文设置与 [17] 相同,并给出实验结果验证了新算法的有效性,模型表示如下:
,
其中生成器为
,判别器为
,
是来自生成器的真实数据或假数据,
为真实数据和潜在变量的分布。真实数据
和潜在变量
的高斯分布数据集来自平均值为0、方差为1的正态分布,
产生于
。批量大小固定为100,实验重复3次。实验结果如图1所示。
图1对比了SAGP算法和SAGDA算法的收敛速度,其中
轴代表迭代次数,
轴代表随机梯度范数取值范围的变化过程,其中RMSprop算法步长为5e−4,参数为0.9;Adam算法步长为5e−4,参数为0.5和0.9;SAGDA算法步长
= 1e−1,
= 5e−1;SAGP算法步长
= 2e−1,
= 8e−1。图1和图2分别对应于四种算法在高斯分布数据集上的实验结果对比。从图中可以看出,本文提出的新算法SAGP的收敛速度整体上比SAGDA算法快,有效地验证了新算法的可行性。
![](//html.hanspub.org/file/31-1700499x89_hanspub.png?20230222083559597)
Figure 1. The change process of the range of the random gradient norm of the discriminator on the Gaussian distribution data set
图1. 在高斯分布数据集上判别器的随机梯度范数取值范围的变化过程
![](//html.hanspub.org/file/31-1700499x90_hanspub.png?20230222083559597)
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)。