非凸函数约束优化的单循环梯度下降和扰动上升算法
该研究介绍了一种与梯度下降上升(GDA)算法相结合的 “平滑” 方案,以解决非凸 - 凹最小 - 最大问题,此方案能够稳定振荡,并确保收敛到一个定值解。实验结果表明,平滑后的 GDA 算法对于 minimizing pointwise maximum of a finite collection of nonconvex functions 可以实现 O (1/ε^2) 的迭代复杂度,对于 general nonconvex-concave problems 可以实现 O (1/ε^4) 的迭代复杂度,并且将该算法扩展到多个区块的情况下。
Oct, 2020
本文研究了使用交替 GDA 和平滑 GDA 算法解决纳什均衡问题的收敛速度,证明了在满足 Polyak-Lojasiewicz 条件时,这两种算法分别需要 O (κ²ε⁻²) 和 O (κε⁻²) 次迭代即可找到 ε- 极小点,而在类似条件下,这是目前最佳的单循环算法复杂度结果。实验证明这些算法在生成对抗网络训练和非线性回归中具有较高的效率。
Dec, 2021
本文研究了一种更为广泛的两人博弈非凸强凹优化的收敛性,在 K-L 参数化几何全谱上,证明了 Proximal-GDA 算法的收敛速率是不同的,这是首个关于非凸极小极大优化变量收敛的理论结果。
Feb, 2021
研究非凸极小问题的解决方案,提出两种算法 AGDA 和随机 AGDA,以及一种方差缩减算法,可以应用于类似生成对抗网络和对抗学习等新兴机器学习应用。
Feb, 2020
本文研究了非凸 - 凹极小化问题,采用了两种不同时间尺度的梯度下降升高算法来解决该问题,并得到了算法能够在有效的时间内找到函数的一个稳定点的结论,这种算法在训练生成敌对网络等实际应用中具有出色的实际表现。
Jun, 2019
本研究提出了一种统一的单循环交替梯度投影 (AGP) 算法,用于解决光滑的非凸 -(强)凹和(强)凸 - 非凹的极小 - 最大化问题,同时扩展了 BAPG 算法。证明该方法可在不同设置下找到目标函数的 ε- 稳定点,且其梯度复杂度被限制在 O(ε^-2)或 O(ε^-4)内。
Jun, 2020
研究零阶算法求解非凸最小最大问题在确定性和随机设置下的紧密线性约束,为确定性和随机设置下求解非凸凹最小最大问题提出两种单环算法,即零阶原始 -- 对偶交替投影梯度(ZO-PDAPG)算法和零阶正则化动量原始 -- 对偶投影梯度算法(ZO-RMPDPG),其迭代复杂度被证明为 Ο(ε^(-2))(非凸凹最小最大问题)和 Ο(ε^(-4))(非凸凹最小最大问题),在确定性设置下,持有 ε- 稳定点,并且在随机设置下,迭代复杂度分别为 Ο̃(ε^(-3)) 和 Ο̃(ε^(-6.5))。据我们所知,它们是第一个能够解决确定性和随机设置下的非凸凹最小最大问题的零阶算法,并具有迭代复杂度保证。
Jan, 2024
给出了一种用于解决具有弱凸目标和凸线性 / 非线性约束问题的阻尼近端增广 Lagrange 方法(DPALM)。通过采用阻尼对偶步长而不是全步长,确保对偶迭代的有界性。如果每个 DPALM 子问题解到适当的精度,则 DPALM 可以在 O (ε^{-2}) 的外部迭代中产生一个近似 ε-KKT 点。此外,我们在目标函数为正则化平滑函数或正则化构成形式的情况下建立了 DPALM 的整体迭代复杂性。对于前一种情况,通过将加速近端梯度(APG)方法应用于每个 DPALM 子问题,DPALM 实现了复杂度为 Τ(ε^{-2.5}),从而产生一个 ε-KKT 点。对于后一种情况,通过使用 APG 来解决每个子问题的 Moreau 包络平滑版本,DPALM 的复杂度为 O (~ε^{-3}),从而得到一个近似 ε-KKT 点。我们的外部迭代复杂性和整体复杂性要么推广了现有的无约束或线性约束问题的最佳结果到凸约束问题,要么改进了解决相同结构问题的已知最佳结果。此外,通过在线性 / 二次约束的非凸二次规划和线性约束的鲁棒非线性最小二乘上进行数值实验,展示了所提出的 DPALM 方法在效率上超过了几种最先进的方法。
Nov, 2023
本文探讨了梯度下降上升(GDA)方法在生成对抗网络中极小化最大化优化问题的收敛性质及实现方式,研究表明 GDA 在本地条件数为 y 时的步长比至少需要为 θ(Kappa),并支持在随机 GDA 和额外梯度方法(EG)中的应用。
Jul, 2022
梯度下降和上升(GDA)法用于最小 - 最大优化问题时,通常会产生振荡行为,容易导致不稳定性,为解决这一问题,本文提出了一种通过引入耗散项来抑制振荡的方法,称为 Dissipative GDA (DGDA),DGDA 方法可以看作是在一个状态增广和规则化的鞍点函数上执行标准 GDA,该方法在双线性和强凸 - 强凹设置中具有线性收敛性,并通过与其他方法(如 GDA、Extra-Gradient,以及 Optimistic GDA)的比较来评估其性能,实验结果表明 DGDA 超过了这些方法,实现了更好的收敛速度,通过两个数值例子展示了 DGDA 方法在求解鞍点问题中的有效性。
Mar, 2024