Text
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(∙,x−i)+ri(∙), 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 \redpseudogradient map, we derive optimal rate statements and oracle complexity bounds for the proposed variable sample-size proximal stochastic gradient-response (VS-PGR) 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 ϵ-Nash equilibrium (ϵ-NE) are O(1/ϵ1/v) and O(1/ϵ1+1/v), respectively. \redWhen 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 \bf VS-PGR with a consensus phase with a view towards developing distributed protocols for aggregative stochastic NEPs. In the resulting \bf d-VS-PGR 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 ϵ-NE requires similar iteration and oracle complexities to \bf VS-PGR with a communication complexity of O(ln2(1/ϵ)). 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 (VS-PBR) 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, O(ln(1/ϵ)) and O(1/ϵ). 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 O(1/ϵ1/v) and O(1/ϵ1+1/v), respectively. (IV) Akin to (II), the distributed variant \bf d-VS-PBR achieves similar iteration and oracle complexities to the centralized VS-PBR with a communication complexity of O(ln2(1/ϵ)) 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.
Barcode | Tipe Koleksi | Nomor Panggil | Lokasi | Status | |
---|---|---|---|---|---|
art142441 | null | Artikel | Gdg9-Lt3 | Tersedia namun tidak untuk dipinjamkan - No Loan |
Tidak tersedia versi lain