Research on Neighboring Gradient Response and Best-Response Schemes in Stochastic Nash Games

本文研究了一个N人随机纳什博弈，其中第i个参与者最小化的目标函数为 f i ( x )+ r i ( x i ) ，其中 f i 是期望值，且 r i 具有高效的近邻评估。在此背景下，本文做出以下结果：1) 在串联梯度映射的强单调性假设条件下，为所提出的可变样本规模近邻随机梯度响应方案推导出最优收敛速率以及神谕复杂度界；2) 在与近邻最佳响应映射相关的合适压缩性质下，设计了一个可变样本规模近邻最佳响应方案，其中近邻最佳响应是通过求解一个样本平均问题来计算的。如果用于计算样本平均的批量大小以合适的速率增加，可以证明所得迭代以线性速率收敛，并推导出神谕复杂度。This paper studies an N-player stochastic Nash game, where the objective function minimized by the i-th player is f i ( x )+ r i ( x i ) , where f i is the expected value and r i has an efficient proximal evaluation. In this context, this paper obtains the following results: 1) Under the strong monotonic assumption of the concatenated gradient mapping, the optimal convergence rate and the oracle complexity bound are derived for the proposed variable sample size stochastic gradient response scheme; 2) Under the appropriate contraction property related to the proximal best-response mapping, a variable sample size proximal best-response scheme is designed, where the proximal best-response is computed by solving a sample average problem. If the batch size used for computing the sample average increases at an appropriate rate, it can be shown that the resulting iterations converge at a linear rate, and the oracle complexity is derived.