Feb, 2020

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

PDF
TL;DR本文提出了一种基于加速的近端点方法和最小值近端步求解器的算法，其梯度复杂度为 O（kappa_x kappa_y^0.5），匹配了已有的最优下界，可用于解决强凸强凹、凸凹、非凸强凹和非凸凹函数的问题。
minimax problemsgradient complexityproximal point methodcondition numberslower bound
发现论文，激发创造
  • 平滑与强凸强凹极小 - 极大优化的首个最优算法

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

    May, 2022

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

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

    Jun, 2020

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

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

    Jul, 2019

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

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

    Feb, 2020

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

    本文研究非凸强凹（NC-SC）平滑极小值问题的近似稳定点的复杂度，在一般和平均平滑有限和设置中建立了非平凡的较低复杂度下界。我们提出了一种通用的加速方案，使用现有的基于梯度的方法来解决一系列的精心制作的强凸 - 强凹子问题，进而缩小了复杂度差距，尤其是在一般情况下，我们提出的算法的复杂度几乎与下界相当。

    Mar, 2021

  • 交替近端梯度步骤用于（随机）非凸 - 凹极小极大问题

    本文针对非凸凹的情况，在最小极大问题中应用交替梯度下降方法找到临界点并证明了一种新的全局收敛速率。

    Jul, 2020

  • 一种具有近似评估和复杂度保证的非凸最小化随机算法

    非凸函数的最小化，利用近似正负曲率方向步长，相对不精确度度量梯度和 Hessian 矩阵，松弛一阶和二阶精度的耦合，通过马丁格尔分析和浓度不等式得到收敛性分析，并将算法应用于经验风险最小化问题。

    Oct, 2023

  • 非凸强凹 Min-Max 优化的复杂度下界

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

    Apr, 2021

  • 加速梯度算法与自适应子空间搜索用于快速实例优化

    设计和分析基于梯度的算法，适用于机器学习中的优化问题，包括线性回归等，并改进了现有的复杂度下界。

    Dec, 2023

  • 适应性额外梯度方法用于极小化 - 极大化优化及博弈

    提出了一种新的 MinMax 优化算法家族，它利用早期迭代所观察到的梯度数据的几何信息，以在后期执行更具信息性的额外梯度步骤，从而自适应地检测问题是否光滑。

    Oct, 2020