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 language||English (US)|
|Number of pages||9|
|Journal||Proceedings of Machine Learning Research|
|State||Published - 2021|
|Event||24th International Conference on Artificial Intelligence and Statistics, AISTATS 2021 - Virtual, Online, United States|
Duration: Apr 13 2021 → Apr 15 2021
Bibliographical noteFunding Information:
M. Hong and I. Tsaknakis are supported by NSF Award CIF-1910385.
Copyright © 2021 by the author(s)