非凸非凹极小极大优化的高阶方法
通过提出一种新的结构化非凸 - 非凹 min-max 优化问题类,引入了一个泛化的外推方法,该方法证明收敛到一个稳定点。这种算法不仅适用于欧几里得空间,还适用于一般的 l p-norm 有限维实向量空间,同时对其在随机 oracle 条件下的稳定性和样本复杂度提供了边界。
Oct, 2020
本文提出了一种有效的算法,通过在原函数上执行近似的近端点迭代,并利用 Nesterov 算法在正则化函数上运行不精确的神谕来找到关于站点准则的(εx,εy)第一阶纳什均衡,其中目标函数在两个变量中都是平滑的,对 y 是凸的;集合 X 和 Y 都是凸集和 “投影友好型” 的,Y 是紧凑的。
Feb, 2020
对于一类满足 $ ho$- 弱 Minty 变分不等式或满足 $ ho$- 凹同调性的受约束、$L$- 平滑、非凸非凹的 min-max 问题,我们给出在 $ ho <rac {1}{L}$ 范围内的最佳复杂性保证,并提供具有相同范围的随机情况下的算法和复杂性保证。分析收敛性改进的主要见解是利用算子的 “锥非扩展性” 特性。此外,我们还提供精细的不精确 Halpern 迭代分析和具有多层蒙特卡洛估计器的随机 KM 迭代的方法。
Feb, 2024
本文通过分析优化问题的计算复杂性,阐明了一系列非凸非凹目标函数的约束极值优化问题存在的困难,同时证明了该问题在 Nemirovsky-Yudin 模型中的难度,这与最小化问题在同样设置下可以使用 Projected Gradient Descent 进行近似局部最小值的行为形成了对比。
Sep, 2020
利用多阶梯度下降上升算法解决机器学习中非凸场景下最小最大鞍点问题,给出了基于 Polyak-Lojasiewicz 条件的算法和 Concave 最大玩家目标函数的算法,并在 Fashion-MNIST 数据集上进行公平分类实验。
Feb, 2019
本研究考虑了一类非凸非凹极值问题的一阶收敛理论和算法,它在机器学习中有广泛的应用,包括训练生成式对抗网络(GAN)。我们提出了一种算法框架,通过解决一系列强单调变分不等式,证明了所提出的方法的一阶收敛性和收敛率,并在 GAN 的训练中证明了所提出的算法的有效性。
Oct, 2018
我们通过使用第一阶 oracle 及条件数,提供了寻找 min-max 优化问题中目标函数在最小化变量上是非凸及在最大化变量上是强凸时的稳定点的复杂度的下界,这既适用于确定性 oracle 也适用于随机 oracle,并提供了各自的下界,并与其他文献的上界进行了比较。
Apr, 2021
本文提出了一种基于加速的近端点方法和最小值近端步求解器的算法,其梯度复杂度为 O(kappa_x kappa_y^0.5),匹配了已有的最优下界,可用于解决强凸强凹、凸凹、非凸强凹和非凸凹函数的问题。
Feb, 2020
提出了一种新的 MinMax 优化算法家族,它利用早期迭代所观察到的梯度数据的几何信息,以在后期执行更具信息性的额外梯度步骤,从而自适应地检测问题是否光滑。
Oct, 2020
针对非凸优化中最小最大优化问题,本研究提出了利用高效的 Hessian - 向量乘积的新型修正动量算法,建立了收敛条件并证明了所提算法的迭代复杂度为 O (ε^{-3})。通过在实际数据集上进行鲁棒的逻辑回归的应用验证了该方法的有效性。
Jun, 2024