论文标题
两尺度的梯度下降上升动力学发现连续游戏的纳什平衡混合：平均场视角
Two-Scale Gradient Descent Ascent Dynamics Finds Mixed Nash Equilibria of Continuous Games: A Mean-Field Perspective
论文作者
论文摘要
在机器学习中，找到两人零和连续游戏的混合纳什均衡（MNE）是一个重要且充满挑战的问题。找到MNE的规范算法是嘈杂的梯度下降方法，在无限的粒子极限中，在概率测量空间上产生了{\ em em平均场梯度下降}（GDA）动力学。在本文中，我们首先研究了一个二尺度平均GDA动力学的收敛，以找到熵登记的物镜的MNE。更准确地说，我们表明，对于每个有限温度（或正则化参数），具有合适{\ em有限}比率比的两尺度平均场GDA将指数收敛于唯一的MNE，而无需假设相互作用势的凸度或凹度。我们证明的关键要素在于构建新的Lyapunov函数，这些功能沿平均场GDA呈指数式消散。我们进一步研究了平均场GDA动力学的模拟退火。我们表明，随着时间的流逝，温度时间表会随着时间的流逝而衰减，退火的平均场GDA会收敛到原始未注册物镜的MNE。
Finding the mixed Nash equilibria (MNE) of a two-player zero sum continuous game is an important and challenging problem in machine learning. A canonical algorithm to finding the MNE is the noisy gradient descent ascent method which in the infinite particle limit gives rise to the {\em Mean-Field Gradient Descent Ascent} (GDA) dynamics on the space of probability measures. In this paper, we first study the convergence of a two-scale Mean-Field GDA dynamics for finding the MNE of the entropy-regularized objective. More precisely we show that for each finite temperature (or regularization parameter), the two-scale Mean-Field GDA with a suitable {\em finite} scale ratio converges exponentially to the unique MNE without assuming the convexity or concavity of the interaction potential. The key ingredient of our proof lies in the construction of new Lyapunov functions that dissipate exponentially along the Mean-Field GDA. We further study the simulated annealing of the Mean-Field GDA dynamics. We show that with a temperature schedule that decays logarithmically in time the annealed Mean-Field GDA converges to the MNE of the original unregularized objective.
