Oct, 2019

局部解决极小化极大化优化问题：跟随脊线方法

PDF
TL;DR本研究提出了一种称之为 Follow-the-Ridge 的新算法，这个算法克服了梯度下降算法在解决 minimax 优化问题时遇到的一些问题，同时在 toy minimax 问题和 GAN 训练中取得较好的效果。
machine learningsequential gamesminimax optimizationfollow-the-ridge algorithmgan training
发现论文，激发创造
  • 非凸 - 非凹极小极大优化中的局部最优性是什么？

    本文提出了一种适用于序列博弈机器学习应用的局部最优定义 —— 局部 minmax， 并且提出了它的属性、存在结果以及与基本的局部搜索算法 —— 梯度下降上升 (GDA) 的强相关性，即在温和条件下，GDA 的所有稳定极限点都是局部 minmax 点，除了某些退化点。

    Feb, 2019

  • K-Beam Minimax：深度对抗学习的高效优化

    本文提出了一种新的 epsilon 次梯度下降算法来解决极小极大优化问题中内部最大化解的不连续性，该算法可以同时跟踪 K 个候选解，并且在 K 的复杂度下找到之前鞍点算法无法找到的解，在 GAN 训练和域自适应问题中有着显著的稳定性和收敛速度提升。

    May, 2018

  • 使用迭代一阶方法解决一类非凸极小极大博弈

    利用多阶梯度下降上升算法解决机器学习中非凸场景下最小最大鞍点问题，给出了基于 Polyak-Lojasiewicz 条件的算法和 Concave 最大玩家目标函数的算法，并在 Fashion-MNIST 数据集上进行公平分类实验。

    Feb, 2019

  • 竞争性梯度下降

    本文提出了一种用于计算竞争性双人游戏纳什均衡的新算法，该算法基于正则化双线性局部逼近的纳什均衡，避免了交替梯度下降中出现的振荡和发散，而且在达到指数级 (局部) 收敛性的同时，其收敛和稳定性的性质对于玩家之间的强交互是稳健的，具有更快的收敛速度。

    May, 2019

  • 通过跟随黑塞矩阵的特征向量发现多样化的解决方案 --Ridge Rider

    本文介绍一种新的方法 Ridge Rider，通过迭代地在损失面的不同 ridges 中进行移动和分叉，而非仅仅沿着梯度下降的方向， 以找到定性不同的解决方案。作者证明了这种方法在各种具有挑战性的问题中都有很好的表现。

    Nov, 2020

  • 用于两人零和马尔科夫博弈的正则化梯度下降 / 上升算法

    本文提出了一种用于在马尔可夫博弈中寻找纳什均衡的新方法，该方法结合梯度下降和熵正则化，获得了更好的收敛性能，并证明了该算法在合适的正则化参数选择下可以收敛到原问题的纳什均衡。

    May, 2022

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

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

    Jul, 2020

  • 一种收敛且与维度无关的极小 - 极大优化算法

    研究了一种新型的 min-max 优化框架，其中 max-player 在贪心策略下更新参数至一阶稳定点；给出了在平稳性要求下的定理证明，提出了一种利用随机梯度估计的 GAN 训练算法，成功地避免了模式崩溃的问题。

    Jun, 2020

  • 随机梯度下降法在极小极大问题中的稳定性和泛化性

    通过算法稳定性的视角，对凸凹和非凸非凹情形下的随机梯度方法在极小极大问题中的泛化能力进行了全面的分析，建立了稳定性与泛化能力之间的定量联系。在凸凹情形下，稳定性分析表明了随机梯度下降算法对于平滑和非平滑的极小极大问题皆可达到最优的泛化界。我们还确定了泛函弱凸弱凹和梯度占主导地位的问题的泛化界。

    May, 2021

  • 比梯度下降法更快地找到局部极小值

    本文介绍了一种非凸二阶优化算法，其时间复杂度与样本维度和训练样本数量呈线性关系，在训练神经网络和其他非凸目标的机器学习问题上具有广泛应用，并可以保证返回近似局部最小值。

    Nov, 2016