Linearly Convergent Variable Sample-Size Schemes for Stochastic Nash Games: Best-Response Schemes and Distributed Gradient-Response Schemes
Jinlong Lei, Uday V. Shanbhag · 2018
This paper considers an N-player stochastic Nash game in which the i th player minimizes a composite objective fi(x)+ri(xi), where fi is expectation-valued and ri has an efficient prox-evaluation. In this context, we make the following contributions. (i) Under a strong monotonicity assumption on the concatenated gradient map, we derive (optimal) rate statements and oracle complexity bounds for the proposed variable sample-size proximal stochastic gradient-response (VS-PGR) scheme; (ii) We overlay (VS-PGR) with a consensus phase with a view towards developing distributed protocols for aggregative stochastic Nash games. Notably, when the sample-size and the number of consensus steps at each iteration grow at a suitable rate, a linear rate of convergence can be achieved; (iii) Finally, under a suitable contractive property associated with the proximal best-response (BR) map, we design a variable sample-size proximal BR (VS-PBR) scheme, where the proximal BR is computed by solving a sample-average problem. If the batch-size for computing the sample-average is raised at a suitable rate, we show that the resulting iterates converge at a linear rate and derive the oracle complexity.