Mar, 2021

非凸强凹极小 - 极大优化的复杂性

PDF
TL;DR本文研究非凸强凹（NC-SC）平滑极小值问题的近似稳定点的复杂度，在一般和平均平滑有限和设置中建立了非平凡的较低复杂度下界。我们提出了一种通用的加速方案，使用现有的基于梯度的方法来解决一系列的精心制作的强凸 - 强凹子问题，进而缩小了复杂度差距，尤其是在一般情况下，我们提出的算法的复杂度几乎与下界相当。
nonconvex-strongly-concave minimax problemslower complexity boundsgradient-based methodsacceleration schemecondition number
发现论文，激发创造
  • 非凸强凹 Min-Max 优化的复杂度下界

    我们通过使用第一阶 oracle 及条件数，提供了寻找 min-max 优化问题中目标函数在最小化变量上是非凸及在最大化变量上是强凸时的稳定点的复杂度的下界，这既适用于确定性 oracle 也适用于随机 oracle，并提供了各自的下界，并与其他文献的上界进行了比较。

    Apr, 2021

  • 极小极大优化的近似最优算法

    本文提出了一种基于加速的近端点方法和最小值近端步求解器的算法，其梯度复杂度为 O（kappa_x kappa_y^0.5），匹配了已有的最优下界，可用于解决强凸强凹、凸凹、非凸强凹和非凸凹函数的问题。

    Feb, 2020

  • 平滑与强凸强凹极小 - 极大优化的首个最优算法

    通过重新定义问题为最小化问题，应用特定变体的近端点算法和使用最佳算法计算不准确的近端算子，我们将最小极小化优化问题的梯度计算复杂度降至 O (sqrt (kappax*kappay)*log (1/epsilon))

    May, 2022

  • 关于平滑非凸有限和优化的下界

    本文研究了平滑的非凸有限和优化的下界，并证明了在不同设置下找到 ε- 次优点和 ε- 近似稳定点的复杂度的严格下界，以及一些现有算法的最佳增量一阶预测器（IFO）复杂度。

    Jan, 2019

  • 基于修正偏置动量的加速随机极小 - 极大优化

    针对非凸优化中最小最大优化问题，本研究提出了利用高效的 Hessian - 向量乘积的新型修正动量算法，建立了收敛条件并证明了所提算法的迭代复杂度为 O (ε^{-3})。通过在实际数据集上进行鲁棒的逻辑回归的应用验证了该方法的有效性。

    Jun, 2024

  • 平滑极小极大优化的高效算法

    本文研究解决平滑最小最大优化问题的一阶方法，其中 g (x,y) 是平滑的且 g (x,・) 对于每个 x 均为凹性。对于 g (・，y)，我们考虑两种情况 —— 强凸性和非凸性 —— 并在两种情况下改进了已知最佳速率。

    Jul, 2019

  • 用于复合非凸强凹极小极大问题的分散梯度下降最大化方法

    本研究提出了一种基于去除双重共识规范的新颖分散极小极大问题重建方法，可以解决具有较高非光滑性和复杂性的问题，通过数值实验表明，所提出的算法具有较高的性能和效率。

    Apr, 2023

  • 非凸随机优化下的下限界

    采用随机一阶方法找到梯度范数不超过 ε 的 ε- 稳定点的复杂度下界，使用具有有界方差的无偏随机梯度预言机访问光滑但可能非凸函数的一种模型，证明任何算法在最坏情况下需要至少 ε^-4 个查询才能找到 ε- 稳定点。对于噪声梯度估计满足均方光滑性质的更严格模型，我们证明了 ε^ -3 个查询的下界，建立了最近提出的方差缩减技术的最优性。

    Dec, 2019

  • 非凸 - 凹平滑极小极大问题的一阶纳什均衡高效搜索

    本文提出了一种有效的算法，通过在原函数上执行近似的近端点迭代，并利用 Nesterov 算法在正则化函数上运行不精确的神谕来找到关于站点准则的（εx，εy）第一阶纳什均衡，其中目标函数在两个变量中都是平滑的，对 y 是凸的；集合 X 和 Y 都是凸集和 “投影友好型” 的，Y 是紧凑的。

    Feb, 2020

  • 凸凹最小化极小化优化的改进算法

    该研究针对广泛应用于深度学习等领域的极小极大优化问题提出了新算法，利用加速方法获得极小极大问题的优秀渐进收敛速度和更紧密的条件数依赖性.

    Jun, 2020