Approaching the Global Nash Equilibrium of Non-Convex Multi-Player Games
- 19 August 2024
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Pattern Analysis and Machine Intelligence
- Vol. 46 (12) , 10797-10813
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 .
Keywords
Funding Information
- University of Edinburgh
- ECFI Major Initiatives Fund
- Smart Data Foundry
- Excellence Initiative-Research University
- AGH University (UMO- 2021/01/2/ST6/00004, ARTIQ/0004/2021)
This publication has 58 references indexed in Scilit:
- Understanding the acceleration phenomenon via high-resolution differential equationsMathematical Programming, 2021
- An operator splitting approach for distributed generalized Nash equilibria computationAutomatica, 2019
- Piecewise affine parameterized value-function based bilevel non-cooperative gamesMathematical Programming, 2018
- Learning in games with continuous action sets and unknown payoff functionsMathematical Programming, 2018
- Canonical Duality Theory2017
- Canonical duality for solving general nonconvex constrained problemsOptimization Letters, 2015
- On zero duality gap in nonconvex quadratic programming problemsJournal of Global Optimization, 2011
- Adaptive Game Playing Using Multiplicative WeightsGames and Economic Behavior, 1999
- Finite-dimensional variational inequality and nonlinear complementarity problems: A survey of theory, algorithms and applicationsMathematical Programming, 1990
- Problem complexity and method efficiency in optimization : A.S. Nemirovsky and D.B. Yudin: Wiley, New York, 1983, 388 pages, £26.00, ISBN 0-471-10345-4Mathematics and Computers in Simulation, 1984