STay-ON-the-Ridge: Guaranteed Convergence to Local Minimax Equilibrium in Nonconvex-Nonconcave Games
STay-ON-the-Ridge: Guaranteed Convergence to Local Minimax Equilibrium in Nonconvex-Nonconcave Games
复制标题
DOI：
10.48550/arxiv.2210.09769
复制
发表时间：
2022-10
期刊：
影响因子：
--
通讯作者：
C. Daskalakis;Noah Golowich;Stratis Skoulakis;Manolis Zampetakis
中科院分区：
文献类型：
--
作者：
C. Daskalakis;Noah Golowich;Stratis Skoulakis;Manolis Zampetakis
涉及非凸-非凹目标的最小-最大优化问题在对抗训练和其他多智能体学习环境中有着重要的应用。然而，没有已知的基于梯度下降的方法是保证收敛到（甚至是局部概念）最小-最大平衡的非凸-非凹设置。对于所有已知的方法，存在相对简单的目标，它们循环或表现出不同于收敛到一个点的其他不期望的行为，更不用说收敛到一些博弈理论上有意义的点了。唯一已知的收敛保证在初始化非常接近局部最小-最大均衡的强假设下成立。此外，上述挑战不仅仅是理论上的好奇心。所有已知的方法在实践中都是不稳定的，即使在简单的设置中。我们提出了第一种方法，保证收敛到一个局部的最小-最大平衡光滑非凸非凹目标。我们的方法是二阶和可证明的逃逸极限环，只要它是在一个容易找到的初始点初始化。我们的方法的定义和它的收敛性分析的动机是由问题的拓扑性质。特别是，我们的方法不是设计来减少一些潜在的功能，如距离的地方最小-最大平衡或投影梯度的目标，但设计满足拓扑性质，保证避免循环，并暗示其收敛。
Min-max optimization problems involving nonconvex-nonconcave objectives have found important applications in adversarial training and other multi-agent learning settings. Yet, no known gradient descent-based method is guaranteed to converge to (even local notions of) min-max equilibrium in the nonconvex-nonconcave setting. For all known methods, there exist relatively simple objectives for which they cycle or exhibit other undesirable behavior different from converging to a point, let alone to some game-theoretically meaningful one~\cite{flokas2019poincare,hsieh2021limits}. The only known convergence guarantees hold under the strong assumption that the initialization is very close to a local min-max equilibrium~\cite{wang2019solving}. Moreover, the afore-described challenges are not just theoretical curiosities. All known methods are unstable in practice, even in simple settings. We propose the first method that is guaranteed to converge to a local min-max equilibrium for smooth nonconvex-nonconcave objectives. Our method is second-order and provably escapes limit cycles as long as it is initialized at an easy-to-find initial point. Both the definition of our method and its convergence analysis are motivated by the topological nature of the problem. In particular, our method is not designed to decrease some potential function, such as the distance of its iterate from the set of local min-max equilibria or the projected gradient of the objective, but is designed to satisfy a topological property that guarantees the avoidance of cycles and implies its convergence.