Theorem 2 — randomized inexact BR reaches an -NE in at most expected SG steps per player
ProvedLeiBR.Rand.theorem_2iteration-complexityp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1randomized-algorithmsstochastic-nash-game
Consider the -player stochastic Nash game, , under Assumptions 1, 2 and 3, with , and a Nash equilibrium . Run Algorithm 2 from a starting point with . When , player computes its inexact best response by
steps of the projected stochastic gradient scheme (SA), for some . This realizes the inexactness .
Let and . Let and
and assume . Let . Then:
- is an -NE: ;
- for every player , the expected number of projected stochastic gradient steps it takes in iterations satisfies
This is the overall iteration complexity of the randomized scheme. Its exponent exceeds the synchronous one of Theorem 1 by the cost of randomization, and it reduces to Theorem 1(a) when every .
Formalization Note
- The starting point is deterministic: the paper's is read as .
- is assumed. The paper uses it implicitly; otherwise and the ceiling in (34) can be negative.
- The run is
IsAlg2SARun. Samples are i.i.d. with the law of and independent of . The coin is independent of and of player 's round- samples. - Statement (35), the case , is not part of this item.
Preamble
import Mathlib import Definitions.Def_SpectralProjGrad_Shared_IsProjOnto import Definitions.Def_LeiBR_Rand_Game import Definitions.Def_LeiBR_Rand_ProxBR import Definitions.Def_LeiBR_Rand_Assumption1 import Definitions.Def_LeiBR_Rand_SA import Definitions.Def_LeiBR_Rand_Algorithm2 import Definitions.Def_LeiBR_Rand_Constants open MeasureTheory ProbabilityTheory
Formal statement
namespace LeiBR.Rand
/-- Theorem 2, (34), pp. 15–16. Let `x_k` be generated by Algorithm 2 with `α_{i,k} = η^{β_{i,k}+1}`,
`η ∈ (0,1)`, `‖x_{i,0} − x*_i‖ ≤ C`, where each update is computed by
`j_{i,k} = ⌈Q_i/η^{2(β_{i,k}+1)}⌉` steps of (SA_{i,k}), under Assumptions 1–3. Let `q̃ ∈ (c̃, 1)`,
`ϵ̃ = ϵ/((N p_max)^{1/2}(C̃ + D̃)) ∈ (0, 1)` and `K = ⌈ln(1/ϵ̃)/ln(1/q̃)⌉`. Then `x_K` is an
`ϵ`-NE₂, and the expected number of projected gradient steps of player `i` is at most
`ℓ̃_i(η) = p_i Q_i/(η² η̃₀² ln(1/η̃₀²)) (1/ϵ̃)^{ln(1/η̃₀²)/ln(1/q̃)} + ⌈ln(1/ϵ̃)/ln(1/q̃)⌉`. -/
theorem theorem_2 {N : ℕ} {n : Fin N → ℕ} {d : ℕ} (G : Game N n)
(μξ : Measure (EuclideanSpace ℝ (Fin d)))
(ψ : Fin N → LeiBR.Sync.Profile n → EuclideanSpace ℝ (Fin d) → ℝ)
(gψ : ∀ i, LeiBR.Sync.Profile n → EuclideanSpace ℝ (Fin d) → LeiBR.Sync.Strat n i) (M : Fin N → ℝ)
(hA1 : Assumption1 G μξ ψ gψ M) (mu : ℝ) (hmu : 0 < mu)
(xhat : LeiBR.Sync.Profile n → LeiBR.Sync.Profile n) (hxhat : IsProxBR G mu xhat)
(hA2 : Assumption2 G mu) (xstar : LeiBR.Sync.Profile n) (hNE : G.IsNE xstar) (hN : 0 < N)
(proj : ∀ i, LeiBR.Sync.Strat n i → LeiBR.Sync.Strat n i)
(hproj : ∀ i, SpectralProjGrad.Shared.IsProjOnto (G.X i) (proj i))
{Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω) [IsProbabilityMeasure P]
(F : Filtration ℕ (inferInstance : MeasurableSpace Ω)) (p : Fin N → ℝ)
(χ : Fin N → ℕ → Ω → ℕ) (ξs : Fin N → ℕ → ℕ → Ω → EuclideanSpace ℝ (Fin d))
(x0 : LeiBR.Sync.Profile n) (x : ℕ → Ω → LeiBR.Sync.Profile n) (η : ℝ) (hη0 : 0 < η) (hη1 : η < 1)
(C : ℝ) (hC : ∀ i, ‖x0 i - xstar i‖ ≤ C)
(q : ℝ) (hq : ctil p (contrFactor G mu) η < q) (hq1 : q < 1)
(hrun : IsAlg2SARun G proj gψ mu μξ P F p χ ξs
(fun i k ω => ⌈Qconst G M mu i / η ^ (2 * (beta χ i k ω + 1))⌉₊) x0 x)
(ε : ℝ) (hε : 0 < ε)
(hεtil : ε / (Real.sqrt (N * pmax p) * (Ctil p C + Dtil p (contrFactor G mu) η q)) < 1) :
let εt := ε / (Real.sqrt (N * pmax p) * (Ctil p C + Dtil p (contrFactor G mu) η q))
let K := ⌈Real.log (1 / εt) / Real.log (1 / q)⌉₊
(∫ ω, blockNorm (x K ω - xstar) ∂P ≤ ε) ∧
∀ i, ∫ ω, ∑ k ∈ Finset.range K,
(⌈Qconst G M mu i / η ^ (2 * (beta χ i k ω + 1))⌉₊ : ℝ) * (χ i k ω : ℝ) ∂P ≤
p i * Qconst G M mu i / (η ^ 2 * etatil0 p η ^ 2 * Real.log (1 / etatil0 p η ^ 2)) *
(1 / εt) ^ (Real.log (1 / etatil0 p η ^ 2) / Real.log (1 / q)) + (K : ℝ) := by sorry
end LeiBR.Rand
Source
Lei, Shanbhag, Pang & Sen, On Synchronous, Asynchronous, and Randomized Best-Response Schemes for Stochastic Nash Games, arXiv:1704.04578v2, pp. 15–16, Theorem 2, (34) (proof p. 16)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.