2023/01/19 by Guanpu Chen, Gehui Xu, Chen, Guanpu +9
Computer Science · #Adaptive Dynamic Programming Control #Computer Science and Game Theory (cs.GT) #Distributed Control Multi-Agent Systems #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC) #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2301.08015
openalex publication_date 2023/01/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Wide machine learning tasks can be formulated as non-convex multi-player games, where Nash equilibrium (NE) is an acceptable solution to all players, since no one can benefit from changing its strategy unilaterally. Attributed to the non-convexity, obtaining the existence condition of global NE is challenging, let alone designing theoretically guaranteed realization algorithms. This paper takes conjugate transformation to the formulation of non-convex multi-player games, and casts the complementary problem into a variational inequality (VI) problem with a continuous pseudo-gradient mapping. We then prove the existence condition of global NE: the solution to the VI problem satisfies a duality relation. Based on this VI formulation, we design a conjugate-based ordinary differential equation (ODE) to approach global NE, which is proved to have an exponential convergence rate. To make the dynamics more implementable, we further derive a discretized algorithm. We apply our algorithm to two typical scenarios: multi-player generalized monotone game and multi-player potential game. In the two settings, we prove that the step-size setting is required to be O(1/k) and O(1/√ k) to yield the convergence rates of O(1/ k) and O(1/√ k), respectively. Extensive experiments in robust neural network training and sensor localization are in full agreement with our theory.