Approaching the Global Nash Equilibrium of Non-Convex Multi-Player Games
Lists
Only you see this
Abstract
Many machine learning problems can be formulated as non-convex multi-player games. Due to non-convexity, it is challenging to obtain the existence condition of the global Nash equilibrium (NE) and design theoretically guaranteed algorithms. This paper studies a class of non-convex multi-player games, where players’ payoff functions consist of canonical functions and quadratic operators. We leverage conjugate properties to transform the complementary problem into a variational inequality (VI) problem using a continuous pseudo-gradient mapping. We prove the existence condition of the global NE as the solution to the VI problem satisfies a duality relation. We then design an ordinary differential equation to approach the global NE with an exponential convergence rate. For practical implementation, we derive a discretized algorithm and apply it to two scenarios: multi-player games with generalized monotonicity and multi-player potential games. In the two settings, step sizes are required to be $\mathcal {O}(1/k)$ and $\mathcal {O}(1/\sqrt{k})$ to yield the convergence rates of $\mathcal {O}(1/ k)$ and $\mathcal {O}(1/\sqrt{k})$, respectively. Extensive experiments on robust neural network training and sensor network localization validate our theory. Our code is available at https://github.com/GuanpuChen/Global-NE.
BibTeX
@article{chen2024approaching,
author = {Guanpu Chen and Gehui Xu and Fengxiang He and Yiguang Hong and Leszek Rutkowski and Dacheng Tao},
title = {{Approaching the Global Nash Equilibrium of Non-Convex Multi-Player Games}},
journal = {IEEE Trans. Pattern Anal. Mach. Intell.},
year = {2024},
doi = {10.1109/tpami.2024.3445666},
}