基于 Polyak-Łojasiewicz 条件的极小化极大优化的更快随机算法
本文研究了使用交替 GDA 和平滑 GDA 算法解决纳什均衡问题的收敛速度,证明了在满足 Polyak-Lojasiewicz 条件时,这两种算法分别需要 O (κ²ε⁻²) 和 O (κε⁻²) 次迭代即可找到 ε- 极小点,而在类似条件下,这是目前最佳的单循环算法复杂度结果。实验证明这些算法在生成对抗网络训练和非线性回归中具有较高的效率。
Dec, 2021
本文提出了一种基于加速的近端点方法和最小值近端步求解器的算法,其梯度复杂度为 O(kappa_x kappa_y^0.5),匹配了已有的最优下界,可用于解决强凸强凹、凸凹、非凸强凹和非凸凹函数的问题。
Feb, 2020
本文研究求解一个 min-max 零和游戏的问题,在非凸非凹的情况下证明了一种简单的多步梯度下降 - 上升算法可以找到该问题的一个 epsilon - 一阶稳定点,其中一个玩家的目标满足 Polyak-Lojasiewicz 条件。
Dec, 2018
应用零阶方案来最小化 Polyak-Łojasewicz (PL) 函数,基于利用随机 oracle 来估计函数的梯度,算法收敛到无约束情况下的全局最小值和约束情况下的全局最小值邻域,附带相应的复杂度界限,并通过数值示例进行了理论结果的证明。
May, 2024
本文研究解决平滑最小最大优化问题的一阶方法,其中 g (x,y) 是平滑的且 g (x,・) 对于每个 x 均为凹性。对于 g (・,y),我们考虑两种情况 —— 强凸性和非凸性 —— 并在两种情况下改进了已知最佳速率。
Jul, 2019
通过重新定义问题为最小化问题,应用特定变体的近端点算法和使用最佳算法计算不准确的近端算子,我们将最小极小化优化问题的梯度计算复杂度降至 O (sqrt (kappax*kappay)*log (1/epsilon))
May, 2022
提出了 Perturbed Proximal Preconditioned SPIDER (3P-SPIDER) 算法,适用于解决有限和非凸复合优化问题,是随机变量度量前向 - 后向算法,提出了迷你批处理策略以减少方差并控制收敛,并通过逻辑回归模型的推理应用进行了数值比较。
Jan, 2023
本文提出了一种基于 SPIDER 梯度估计器的分布式算法,可用于处理随机的平滑、非凸优化问题,该算法结合了最优化方差减少技术与并行 SGD 算法,优化了可以用于联邦学习的非相同分布的数据的模型,提出的算法具有最优迭代复杂度复杂度,并实现了与现有方法相同的线性加速。
Dec, 2019
算法设计为在欧几里得或单纯形域内最小化 max (f_i (x)),若每个 f_i 为 1-Lipschitz 和 1 - 光滑函数,我们的方法可以在评价复杂度中找到 ε- 近似解,并具有优化性能。
Nov, 2023