Lemma 5 — Algorithm 2 converges linearly:
ProvedLeiBR.Rand.lemma_5linear-convergencep2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1randomized-algorithmsstochastic-nash-game
Let Assumptions 1 and 2 hold, , , and let be a Nash equilibrium. Let be generated by Algorithm 2 under Assumption 3, from a starting point with for all . The inexactness is for some , where is the number of updates of player before iteration . Let . Then for every ,
with from (A.2), , and .
This is the geometric rate of the randomized scheme. It reduces to Proposition 4 when every .
Formalization Note The starting point is deterministic, and the paper's is read as . The proof's step needs this. The run is any run of the abstract scheme (IsAlg2Run) with .
Preamble
import Mathlib 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
/-- Lemma 5 (geometric convergence), p. 15. Let `x_k` be generated by Algorithm 2 with
`α_{i,k} = η^{β_{i,k}+1}`, `η ∈ (0,1)`, and `‖x_{i,0} − x*_i‖ ≤ C`, under Assumptions 1–3. Then for
every `q̃ ∈ (c̃, 1)`, `c̃ = max{ã, η̃}`,
`E‖x_k − x*‖_P ≤ √N (C̃ + D̃) q̃^k` for all `k ≥ 0`. -/
theorem lemma_5 {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)
{Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω) [IsProbabilityMeasure P]
(F : Filtration ℕ (inferInstance : MeasurableSpace Ω)) (p : Fin N → ℝ)
(χ : Fin N → ℕ → Ω → ℕ) (w : ∀ i, ℕ → Ω → LeiBR.Sync.Strat n i) (x0 : LeiBR.Sync.Profile n)
(x : ℕ → Ω → LeiBR.Sync.Profile n) (η : ℝ) (hη0 : 0 < η) (hη1 : η < 1)
(C : ℝ) (hC : ∀ i, ‖x0 i - xstar i‖ ≤ C)
(hrun : IsAlg2Run G xhat P F p χ w (fun i k ω => η ^ (beta χ i k ω + 1)) x0 x)
(q : ℝ) (hq : ctil p (contrFactor G mu) η < q) (hq1 : q < 1) (k : ℕ) :
∫ ω, wnorm p (x k ω - xstar) ∂P ≤
Real.sqrt N * (Ctil p C + Dtil p (contrFactor G mu) η q) * 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, p. 15, Lemma 5 (proof: App. B, pp. 32–33)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.