Finding Nash equilibria in two-player zero-sum continuous games is a central problem in machine learning, e.g. for training both GANs and robust models. The existence of pure Nash equilibria requires strong conditions which are not typically met in practice. Mixed Nash equilibria exist in greater generality and may be found using mirror descent. Yet this approach does not scale to high dimensions. To address this limitation, we parametrize mixed strategies as mixtures of particles, whose positions and weights are updated using gradient descent-ascent. We study this dynamics as an interacting gradient flow over measure spaces endowed with the Wasserstein-Fisher-Rao metric. We establish global convergence to an approximate equilibrium for the related Langevin gradient-ascent dynamic. We prove a law of large numbers that relates particle dynamics to mean-field dynamics. Our method identifies mixed equilibria in high dimensions and is demonstrably effective for training mixtures of GANs.
翻译:在双玩者零和连续游戏中找到纳什平衡是机器学习的一个中心问题,例如培训GANs和稳健模型。纯纳什平衡的存在要求有通常无法满足的严格条件。混合的纳什平衡存在更为普遍,可能使用镜状下沉。然而,这一方法没有达到高度。为了解决这一限制,我们把混合策略作为粒子混合物,其位置和重量通过梯度下沉来更新。我们研究这种动态,把它作为具有瓦瑟斯坦-菲舍尔-拉奥指标的测量空间的交互梯度流动。我们建立全球趋同,为相关的Langevin梯度-斜度动态建立近似平衡。我们证明这是一个将粒子动态与中位场动态联系起来的大量法律。我们的方法在高维度上确定了混合的平衡,对于培训GAN混合物非常有效。