CaltechAUTHORS
  A Caltech Library Service

Competitive Gradient Descent

Schäfer, Florian and Anandkumar, Anima (2019) Competitive Gradient Descent. In: 33rd Conference on Neural Information Processing Systems. Neural Information Processing Systems Foundation, Inc. , Art. No. 8979. https://resolver.caltech.edu/CaltechAUTHORS:20190905-154241002

[img] PDF - Published Version
See Usage Policy.

1MB
[img] PDF - Submitted Version
See Usage Policy.

1MB
[img] Archive (ZIP) - Supplemental Material
See Usage Policy.

99MB

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20190905-154241002

Abstract

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 optimism and 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.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
https://papers.nips.cc/paper/8979-competitive-gradient-descentPublisherArticle
https://arxiv.org/abs/1905.12103arXivDiscussion Paper
Additional Information:© 2019 Neural Information Processing Systems Foundation, Inc. A. Anandkumar is supported in part by Bren endowed chair, Darpa PAI, Raytheon, and Microsoft, Google and Adobe faculty fellowships. F. Schäfer gratefully acknowledges support by the Air Force Office of Scientific Research under award number FA9550-18-1-0271 (Games for Computation and Learning) and by Amazon AWS under the Caltech Amazon Fellows program. We thank the reviewers for their constructive feedback, which has helped us improve the paper.
Group:Center for Autonomous Systems and Technologies (CAST)
Funders:
Funding AgencyGrant Number
Bren Professor of Computing and Mathematical SciencesUNSPECIFIED
Defense Advanced Research Projects Agency (DARPA)UNSPECIFIED
RaytheonUNSPECIFIED
Microsoft Faculty FellowshipUNSPECIFIED
Google Faculty Research AwardUNSPECIFIED
AdobeUNSPECIFIED
Air Force Office of Scientific Research (AFOSR)FA9550-18-1-0271
Amazon Web ServicesUNSPECIFIED
Record Number:CaltechAUTHORS:20190905-154241002
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20190905-154241002
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:98451
Collection:CaltechAUTHORS
Deposited By: George Porter
Deposited On:06 Sep 2019 14:29
Last Modified:09 Jul 2020 20:17

Repository Staff Only: item control page