May, 2023

保证几何惩罚有界的黎曼极小 - 极大优化的加速方法

PDF
TL;DR本文研究的是优化问题，其中函数在乘积 Riemann 流形上是几何上凸的，设计了加速的方法，改进了现有的方法，并在 Riemann 最小 - 最大的情况下证明了全局线性收敛。
发现论文，激发创造
  • 凸凹最小化极小化优化的改进算法

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

    Jun, 2020

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

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

    Oct, 2020

  • 凸优化的梯度方法：在较弱条件下获得更好的收敛速率

    本文研究了梯度方法在凸优化中的收敛行为，证明了仅满足某些线段上的 Lipschitz 连续性和强凸性条件时，其复杂度可达到已知的最优值。同时，利用切线条件和投影的约束得到了更为松弛的条件，并应用于稀疏优化问题中构造更快的求解算法。

    Mar, 2013

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

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

    Jul, 2019

  • 结构化非凸 - 非凹二次规划的高效优化方法

    通过提出一种新的结构化非凸 - 非凹 min-max 优化问题类，引入了一个泛化的外推方法，该方法证明收敛到一个稳定点。这种算法不仅适用于欧几里得空间，还适用于一般的 l p-norm 有限维实向量空间，同时对其在随机 oracle 条件下的稳定性和样本复杂度提供了边界。

    Oct, 2020

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

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

    Feb, 2020

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

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

    May, 2022

  • 约束下的黎曼流形优化简单算法

    本文介绍了扩展现有算法，从欧几里得情况到黎曼情况的从等式和不等式约束中考虑代码优化问题，在高维下实现计算效率与准确度的提高，具有重要的实践应用。

    Jan, 2019

  • 有约束极小极大优化的复杂性

    本文通过分析优化问题的计算复杂性，阐明了一系列非凸非凹目标函数的约束极值优化问题存在的困难，同时证明了该问题在 Nemirovsky-Yudin 模型中的难度，这与最小化问题在同样设置下可以使用 Projected Gradient Descent 进行近似局部最小值的行为形成了对比。

    Sep, 2020

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

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

    Feb, 2020