Oct, 2019

梅日定理回归、梯度下降升及其在非凸零和博弈中的周期和人为均衡

PDF
TL;DR本文研究了一类非凸非凹的极小极大博弈，应用于生成对抗网络中。作者从优化理论、博弈理论和动态系统的角度展开分析，证明了针对特定的问题实例，梯度下降升力动力学可能表现出多种不收敛至极小极大解的行为，包括周期性和波恩卡雷复发。
non-convexnon-concavemin-max gamesgenerative adversarial networksoptimization theory
发现论文，激发创造
  • 连续游戏中基于梯度的学习

    本研究提出了一个广泛适用于多智能体领域的竞争性基于梯度的学习模型，并使用动态系统理论对其进行了分析，对于有限和无限游戏，我们表征了一组非常小的局部纳什均衡，这组均衡将被激活，如果每个智能体采用基于梯度的学习算法。同时研究了基于算法自身构建的不属于纳什均衡的收敛策略在有限和无限游戏中的存在性，这可能解释了在零和游戏中，应用相关算法时出现的困难。最后，为了验证理论贡献，我们给出了一个示例验证。

    Apr, 2018

  • 局部曲率下极小极大博弈梯度方法的本地收敛

    本论文研究两人零和可微分博弈梯度方法的局部纳什均衡，证明了只要 S 为非零偏曲率，且反对称矩阵 A 的特征向量与 S 核的一般位置相关，则达到收敛，重点研究了连续游戏和极大极小博弈中的应用。

    May, 2023

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

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

    May, 2022

  • 竞争性梯度下降

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

    May, 2019

  • 通用和随机游戏的梯度下降方案研究

    本文研究一种梯度方案对两个玩家的随机博弈进行求解，并在模拟中显示该方案确实收敛到 Nash 均衡解。但如果只在目标函数的全局最小值处才能达到最优解，当渐近接近时仅能到达局部极小值，本文阐明了梯度方案收敛于广义和随机游戏中纳什均衡的重要必要条件。

    Jul, 2015

  • 在 Polyak-Łojasiewicz 条件下解决非凸非凹 Min-Max 博弈

    本文研究求解一个 min-max 零和游戏的问题，在非凸非凹的情况下证明了一种简单的多步梯度下降 - 上升算法可以找到该问题的一个 epsilon - 一阶稳定点，其中一个玩家的目标满足 Polyak-Lojasiewicz 条件。

    Dec, 2018

  • 利用非凸博弈中的隐藏结构以达到纳什均衡点的收敛

    该研究提出了一种名为预条件隐藏梯度下降（PHGD）的灵活的一阶方法，旨在利用机器学习中隐藏的凸结构以实现收敛到均衡状态。研究对非合作博弈、Nash 均衡和控制变量与凸结构之间的转换提供了明确的收敛率保证。

    Dec, 2023

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

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

    Jul, 2020

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

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

    Feb, 2019

  • 非凹博弈中可解的局部均衡

    在非凸博弈中，通过在线梯度下降和无悔学习等方法可以有效地收敛到具有光滑效用函数的博弈中的局部均衡状态。

    Mar, 2024