Finding First-Order Nash Equilibria of Zero-Sum Games with the Regularized Nikaido-Isoda Function

Ioannis Tsaknakis, Mingyi Hong

Research output: Contribution to journalConference articlepeer-review

Abstract

Efficiently finding First-order Nash Equilibria (FNE) in zero-sum games can be challenging, even in a two-player setting. This work proposes an algorithm for finding the FNEs of a two-player zero-sum game, in which the local cost functions can be non-convex, and the players only have access to local stochastic gradients. The proposed approach is based on reformulating the problem of interest as minimizing the Regularized Nikaido-Isoda (RNI) function. We show that the global minima of the RNI correspond to the set of FNEs, and that for certain classes of non-convex games the RNI minimization problem becomes convex. Moreover, we introduce a first-order (stochastic) optimization method, and establish its convergence to a neighborhood of a stationary solution of the RNI objective. The key in the analysis is to properly control the bias between the local stochastic gradient and the true one. Although the RNI function has been used in analyzing convex games, to our knowledge, this is the first time that the properties of the RNI formulation have been exploited to find FNEs for non-convex games in a stochastic setting.

Original languageEnglish (US)
Pages (from-to)1189-1197
Number of pages9
JournalProceedings of Machine Learning Research
Volume130
StatePublished - 2021
Event24th International Conference on Artificial Intelligence and Statistics, AISTATS 2021 - Virtual, Online, United States
Duration: Apr 13 2021Apr 15 2021

Bibliographical note

Funding Information:
M. Hong and I. Tsaknakis are supported by NSF Award CIF-1910385.

Publisher Copyright:
Copyright © 2021 by the author(s)

Fingerprint

Dive into the research topics of 'Finding First-Order Nash Equilibria of Zero-Sum Games with the Regularized Nikaido-Isoda Function'. Together they form a unique fingerprint.

Cite this