差的最大结构弱凸函数的单循环随机算法
本文提出一种新的随机优化原理,即使用 Blanchet 和 Glynn 的多级 Monte-Carlo 方法将任何最优随机梯度方法转换为 $x_*$ 的估计量,以此为基础获得了一种廉价且几乎无偏差的梯度估计器,可以应用于随机优化的多个领域,如随机优化,概率图形模型推理以及优化的机器学习等。
Jun, 2021
本文研究了一类非凸的最小值最大值问题,其中目标函数在最小化变量上是弱凸的,在最大化变量上是凸的。针对不同的光滑和不光滑的实例,我们提出了近端引导随机次梯度方法和近端引导随机方差减少方法。同时,我们分析了所提出方法在找到最小值和最大值对应的几乎稳定点的时间复杂性。
Oct, 2018
本文提出一族算法通过简单的随机模型样本和优化方法,成功的减少了目标函数。我们展示出,合理的近似质量和模型的正则性下,此类算法将自然的稳定度衡量推向 0,该衰减速度为 O (k^(-1/4)),基于此原理,我们为随机的近端子梯度法,近端次梯度法以及规则化的高斯牛顿法等提供了第一个复杂性保证。
Mar, 2018
该论文提出了一种名为 SREDA 的新方法,它使用方差缩减技术更有效地估计梯度,其在解决非凸 - 凹极小极大优化问题方面具有优异的性能,并且可应用于机器学习和对抗训练等领域。
Jan, 2020
本研究提出了一种统一的单循环交替梯度投影 (AGP) 算法,用于解决光滑的非凸 -(强)凹和(强)凸 - 非凹的极小 - 最大化问题,同时扩展了 BAPG 算法。证明该方法可在不同设置下找到目标函数的 ε- 稳定点,且其梯度复杂度被限制在 O(ε^-2)或 O(ε^-4)内。
Jun, 2020
本文探讨了多块最小最大双层优化问题,提出了一种单循环随机算法,其样本复杂性为 O(1/ϵ^4),应用于多任务深度 AUC 最大化和多任务深度局部 AUC 最大化。
Jun, 2022
该研究介绍了一种与梯度下降上升(GDA)算法相结合的 “平滑” 方案,以解决非凸 - 凹最小 - 最大问题,此方案能够稳定振荡,并确保收敛到一个定值解。实验结果表明,平滑后的 GDA 算法对于 minimizing pointwise maximum of a finite collection of nonconvex functions 可以实现 O (1/ε^2) 的迭代复杂度,对于 general nonconvex-concave problems 可以实现 O (1/ε^4) 的迭代复杂度,并且将该算法扩展到多个区块的情况下。
Oct, 2020
研究零阶算法求解非凸最小最大问题在确定性和随机设置下的紧密线性约束,为确定性和随机设置下求解非凸凹最小最大问题提出两种单环算法,即零阶原始 -- 对偶交替投影梯度(ZO-PDAPG)算法和零阶正则化动量原始 -- 对偶投影梯度算法(ZO-RMPDPG),其迭代复杂度被证明为 Ο(ε^(-2))(非凸凹最小最大问题)和 Ο(ε^(-4))(非凸凹最小最大问题),在确定性设置下,持有 ε- 稳定点,并且在随机设置下,迭代复杂度分别为 Ο̃(ε^(-3)) 和 Ο̃(ε^(-6.5))。据我们所知,它们是第一个能够解决确定性和随机设置下的非凸凹最小最大问题的零阶算法,并具有迭代复杂度保证。
Jan, 2024