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

May, 2023

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

Local Convergence of Gradient Methods for Min-Max Games under Partial Curvature

Guillaume Wang, Lénaïc Chizat

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

Abstract

We study the convergence to local nash equilibria of gradient methods for two-player zero-sum differentiable games. It is well-known that such dynamics converge locally when $S \succ 0$ and may diverge when $S=0$

nash equilibria gradient methods convergence rates continuous games partial curvature

发现论文，激发创造

极小 - 极大算法在黎曼流形上收敛于可微平衡点

通过普遍基于谱分析的方法，对 Riemann 流形上的零和可微博弈问题推广了可微 Steckelberg 平衡和可微 Nash 平衡，并给出了算法局部收敛的充分条件。这些算法通过引入随机梯度来扩展，并应用于训练 Wasserstein GAN 模型，从而提高 GAN 模型的性能。

May, 2024

竞争性梯度下降

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

May, 2019

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

本文研究了一类非凸非凹的极小极大博弈，应用于生成对抗网络中。作者从优化理论、博弈理论和动态系统的角度展开分析，证明了针对特定的问题实例，梯度下降升力动力学可能表现出多种不收敛至极小极大解的行为，包括周期性和波恩卡雷复发。

Oct, 2019

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

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

Mar, 2024

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

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

Feb, 2019

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

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

Jun, 2020

一种两人零和博弈的平均场分析

使用梯度下降法的粒子动态法可以在高维度的情况下找到两个玩家零和持续游戏中的混合纳什均衡，该方法对于训练对抗生成网络的混合模型是有效的。

Feb, 2020

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

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

Jul, 2020

测度上极小最大值均衡的同时传输演化

本文利用熵正则化方法，通过针对概率测度空间上的混合平衡点问题，采用对称梯度升降法求解 Wasserstein 距离来解决最小化最大问题，并取得全局收敛性。同时，提出 Wasserstein 几何下的凸凹可用于解决相关熵正则化的损失函数。

Feb, 2022

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

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

Dec, 2018