Exponential Convergence of Gradient Methods in Concave Network Zero-sum Games
Motivated by Generative Adversarial Networks, we study the computation of Nash equilibrium in concave network zero-sum games (NZSGs), a multiplayer generalization of two-player zero-sum games first proposed with linear payoffs. Extending previous results, we show that various game theoretic properties of convex-concave two-player zero-sum games are preserved in this generalization. We then generalize last iterate convergence results obtained previously in two-player zero-sum games. We analyze convergence rates when players update their strategies using Gradient Ascent, and its variant, Optimistic Gradient Ascent, showing last iterate convergence in three settings -- when the payoffs of players are linear, strongly concave and Lipschitz, and strongly concave and smooth. We provide experimental results that support these theoretical findings.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Competitive Gradient Descent
We introduce a new algorithm for the numerical computation of Nash equilibria of competitive two-player games. Our method is a natural generalization of gradient descent to the two-player setting where the update is give…
Zeroth-Order Non-Log-Concave Sampling with Variance Reduction and Applications to Inverse Problems
Sampling from high-dimensional, non-log-concave distributions with unnormalized densities remains a fundamental challenge in machine learning, particularly in black-box settings where gradient information is inaccessible…
Solving Min-Max Optimization with Hidden Structure via Gradient Descent Ascent
Many recent AI architectures are inspired by zero-sum games, however, the behavior of their dynamics is still not well understood. Inspired by this, we study standard gradient descent ascent (GDA) dynamics in a specific …
Policy-based Primal-Dual Methods for Concave CMDP with Variance Reduction
We study Concave Constrained Markov Decision Processes (Concave CMDPs) where both the objective and constraints are defined as concave functions of the state-action occupancy measure. We propose the Variance-Reduced Prim…
Last iterate convergence in no-regret learning: constrained min-max optimization for convex-concave landscapes
In a recent series of papers it has been established that variants of Gradient Descent/Ascent and Mirror Descent exhibit last iterate convergence in convex-concave zero-sum games. Specifically, \cite{DISZ17, LiangS18} sh…