Competitive Gradient Descent

By Florian Schäfer, Anima Anandkumar. 2019

119 citations recorded by the source corpus.

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 given by the Nash equilibrium of a regularized bilinear local approximation of the underlying game. It avoids oscillatory and divergent behaviors seen in alternating gradient descent. Using numerical experiments and rigorous analysis, we provide a detailed comparison to methods based on \emph{optimism} and \emph{consensus} and show that our method avoids making any unnecessary changes to the gradient dynamics while achieving exponential (local) convergence for (locally) convex-concave zero sum games. Convergence and stability properties of our method are robust to strong interactions between the players, without adapting the stepsize, which is not the case with previous methods. In our numerical experiments on non-convex-concave problems, existing methods are prone to divergence and instability due to their sensitivity to interactions among the players, whereas we never observe divergence of our algorithm. The ability to choose larger stepsizes furthermore allows our algorithm to achieve faster convergence, as measured by the number of model evaluations.

Subfields: Artificial Intelligence, Modeling and Simulation, Statistics and Probability, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Modeling and Simulation

In Statistics and Probability

In Optimization & Training

Citations in the corpus

Stochastic Hamiltonian Gradient Methods for Smooth Games (2020, background): “…gradient descentascent (and its variance reduction variant) for a subclass of nonconvex-nonconcave objectives satisfying a so-called 3See also Schäfer & Anandkumar (2019) for an efficient approximation of the inverse through a conjugate gradient approach. two-sided Polyak-Lojasiewicz…”
Understanding and mitigating gradient pathologies in physics-informed neural networks (2020, methodology): “From an optimization standpoint, this setting has motivated the development of proximal gradient algorithms [36] that have been successfully applied to ill-posed inverse problems involving stiff regularization terms [37], as well as effective algorithms for finding Nash equilibria in multi-player ga”
A Game Theoretic Framework for Model Based Reinforcement Learning (2020, background): “SGD) are unstable for games due to non-stationarity [13, 14, 18, 30].”
On the distance between two neural networks and the stability of learning (2020, methodology): “It is used in a number of works in the context of deep learning optimisation [12–15], distributed training [16], and generative adversarial networks [17].”