DISTRIBUTED VARIABLE SAMPLE-SIZE GRADIENT-RESPONSE AND BEST-RESPONSE SCHEMES FOR STOCHASTIC NASH EQUILIBRIUM PROBLEMS

This paper considers an n-player stochastic Nash equilibrium problem (NEP) in which the ith player minimizes a composite objective fi(\bullet, x - i) + ri(\bullet ), where fi is an expectation-valued smooth function, x - i is a tuple of rival decisions, and ri is a nonsmooth convex function with an efficient prox-evaluation. In this context, we make the following contributions. (I) Under suitable monotonicity assumptions on the pseudogradient map, we derive optimal rate statements and oracle complexity bounds for the proposed variable sample-size proximal stochastic gradient-response (\bfV \bfS - \bfP \bfG \bfR) scheme when the sample-size increases at a geometric rate. If the sample-size increases at a polynomial rate with degree v > 0, the mean-squared error of the iterates decays at a corresponding polynomial rate; in particular, we prove that the iteration and oracle complexities to obtain an \epsilon -Nash equilibrium (\epsilon -NE) are \scrO (1/\epsilon ^1/v) and \scrO (1/\epsilon ^1+1/v), respectively. When the sample-size is held constant, the iterates converge geometrically to a neighborhood of the Nash equilibrium in an expected-value sense. (II) We then overlay \bfV \bfS -\bfP \bfG \bfR with a consensus phase with a view towards developing distributed protocols for aggregative stochastic NEPs. In the resulting \bfd -\bfV \bfS -\bfP \bfG \bfR scheme, when the sample-size at each iteration grows at a geometric rate while the communication rounds per iteration grow at the rate of k + 1, computing an \epsilon -NE requires similar iteration and oracle complexities to \bfV \bfS -\bfP \bfG \bfR with a communication complexity of \scrO (ln²(1/\epsilon )). Notably, (I) and (II) rely on weaker oracle assumptions in that the conditionally unbiasedness assumption is relaxed while the bound on the conditional second moment may be state-dependent. (III) Under a suitable contractive property associated with the proximal best-response (BR) map, we design a variable sample-size proximal BR (\bfV \bfS -\bfP \bfB \bfR) scheme, where each player solves a sample-average BR problem. When the sample-size increases at a suitable geometric rate, the resulting iterates converge at a geometric rate while the iteration and oracle complexity are, respectively, \scrO (ln(1/\epsilon )) and \scrO (1/\epsilon ). If the sample-size increases at a polynomial rate with degree v, the mean-squared error decays at a corresponding polynomial rate while the iteration and oracle complexities are \scrO (1/\epsilon ^1/v) and \scrO (1/\epsilon ^1+1/v), respectively. (IV) Akin to (II), the distributed variant \bfd -\bfV \bfS -\bfP \bfB \bfR achieves similar iteration and oracle complexities to the centralized \bfV \bfS -\bfP \bfB \bfR with a communication complexity of \scrO (ln²(1/\epsilon )) when the communication rounds per iteration increase at the rate of k + 1. Finally, we present preliminary numerics to provide empirical support for the rate and complexity statements.