Potentiality-Based Smoothed Randomized Stochastic Gradient Schemes for Solving Nonconvex Nonsmooth Games under Uncertainty

Abstract

We develop a potentiality-based gradient-response framework for computing Clarke-Nash equilibria (CNE) in stochastic $N$-player nonconvex nonsmooth potential games. The key observation is that under smoothness and potentiality, the concatenated vector of player-specific gradients coincides with the gradient of the potential function, thereby providing a synchronous gradient-response framework whose dynamics are subsequently analyzed. In the smooth regime, we introduce a randomized stochastic gradient (RSG) scheme and establish the optimal sample complexity $\mathcal{O}(N^2{\epsilon }^{-4})$ for computing a point with expected residual norm at most $\epsilon$. When the potential function is pseudoconvex, this guarantee can be strengthened to Nash equilibrium (NE) convergence. We then incorporate player-wise randomized smoothing and propose a randomized smoothed RSG (RS-RSG) scheme for Lipschitz continuous objectives, deriving complexity guarantees for the smoothed game and an approximation guarantee for CNE of the original nonsmooth game. Finally, biased variants of these schemes are developed to accommodate hierarchical settings with inexact lower-level solutions.

37 pages, 3 figures