Theorem 1(a) — synchronous inexact proximal BR reaches an -NE within projected SG steps per player
ProvedLeiBR.Sync.theorem_1aConsider the -player stochastic Nash game under Assumptions 1 and 2, with , a Nash equilibrium , and . Run Algorithm 1 from a deterministic with , computing each inexact proximal BR by the inner loop (SA) with
projected stochastic gradient steps at major iteration , for some (so that (8) holds with ). The sampled gradients satisfy the hypotheses of Lemma 3 at every with , and the sampled gradient map and the samples are measurable.
Let , , , , , and run
major iterations. Then:
- is an -NE in the sense of (26): ;
- for every player , the number of projected stochastic gradient steps used, , is at most
This is the paper's overall iteration complexity of the synchronous scheme: an -Nash equilibrium is reached with a number of sampled gradients per player that is explicit in , , and the game's constants.
Formalization Note The theorem states exactly what the proof establishes, (29) and the bound after (31), for the step counts and the iteration count used there. Statement repairs: the initial point is deterministic (Algorithm 1), so reads ; is assumed, since otherwise the ceiling in (27) can be non-positive while no step is taken; the second-moment hypothesis of Lemma 3 is the bound ; Assumption 1(b) is joint . .
import Mathlib import Definitions.Def_SpectralProjGrad_Shared_IsProjOnto import Definitions.Def_LeiBR_Sync_NashGame import Definitions.Def_LeiBR_Sync_StochGame import Definitions.Def_LeiBR_Sync_Algorithm1 open MeasureTheory
namespace LeiBR.Sync
/-- Theorem 1(a), p. 11 (overall iteration complexity of the synchronous scheme). Run Algorithm 1
with the inner loop (SA_{i,k}), `j_{i,k} = ⌈Q_i/η^{2(k+1)}⌉` projected stochastic-gradient steps
for player `i` at major iteration `k` (so `α_{i,k} = η^{k+1}`, `η ∈ (0, 1)`), from a
deterministic `x_0 ∈ X` with `‖x_{i,0} - x*_i‖ ≤ C`, for
`K = ⌈ln(√N(C+D)/ϵ)/ln(1/q)⌉` major iterations, where `a = ‖Γ‖`, `c = max{a, η}`,
`q ∈ (c, 1)`, `D = 1/ln((q/c)^e)` and `0 < ϵ < √N(C+D)`. Then `x_K` is an `ϵ`-NE₂,
`E‖(‖x_{i,K} - x*_i‖)_i‖ ≤ ϵ`, and for every player the total number of steps
`∑_{k<K} j_{i,k}` is at most
`ℓ_i(η) = Q_i/(η⁴ ln(1/η²)) · (√N(C+D)/ϵ)^{ln(1/η²)/ln(1/q)} + ⌈ln(√N(C+D)/ϵ)/ln(1/q)⌉`. -/
theorem theorem_1a
{N : ℕ} {n : Fin N → ℕ} {Ω : Type*} [mΩ : MeasurableSpace Ω] (P : Measure Ω)
[IsProbabilityMeasure P] {d : ℕ} (ξ : Ω → EuclideanSpace ℝ (Fin d))
(X : ∀ i : Fin N, Set (Strat n i)) (ψ : Fin N → Profile n → EuclideanSpace ℝ (Fin d) → ℝ)
(gψ : ∀ i : Fin N, Profile n → EuclideanSpace ℝ (Fin d) → Strat n i) (M : Fin N → ℝ)
(hA1 : Assumption1 P ξ X ψ gψ M) (μ : ℝ) (hμ : 0 < μ)
(hA2 : Assumption2 X (payoff P ξ ψ) μ)
(xhat : Profile n → Profile n) (hxhat : IsProxBR X (payoff P ξ ψ) μ xhat)
(proj : ∀ i : Fin N, Strat n i → Strat n i)
(hproj : ∀ i : Fin N, SpectralProjGrad.Shared.IsProjOnto (X i) (proj i))
(hgψ : ∀ i : Fin N,
Measurable (fun p : Profile n × EuclideanSpace ℝ (Fin d) => gψ i p.1 p.2))
(j : Fin N → ℕ → ℕ) (ξs : ℕ → Fin N → ℕ → Ω → EuclideanSpace ℝ (Fin d))
(hξs : ∀ k (i : Fin N) t, Measurable (ξs k i t))
(x0 : Profile n) (hx0 : x0 ∈ stratSet X)
(xs : Profile n) (hxs : IsNashEq X (payoff P ξ ψ) xs)
(η : ℝ) (hη0 : 0 < η) (hη1 : η < 1)
(hj : ∀ (i : Fin N) (k : ℕ), j i k = ⌈Qconst X M μ i / η ^ (2 * (k + 1))⌉₊)
(hint : ∀ k (i : Fin N) (t : ℕ), 1 ≤ t → t ≤ j i k →
Integrable (fun ω => ‖gψ i (Function.update (syncSA proj gψ μ j ξs x0 k ω) i
(saZ proj gψ μ j ξs x0 k i t ω)) (ξs k i t ω)‖ ^ 2) P)
(hunb : ∀ k (i : Fin N) (t : ℕ), 1 ≤ t → t ≤ j i k →
P[fun ω => gψ i (Function.update (syncSA proj gψ μ j ξs x0 k ω) i
(saZ proj gψ μ j ξs x0 k i t ω)) (ξs k i t ω) | innerField j ξs k i t]
=ᵐ[P] fun ω => partialGrad (payoff P ξ ψ) i
(Function.update (syncSA proj gψ μ j ξs x0 k ω) i (saZ proj gψ μ j ξs x0 k i t ω)))
(hvar : ∀ k (i : Fin N) (t : ℕ), 1 ≤ t → t ≤ j i k →
P[fun ω => ‖gψ i (Function.update (syncSA proj gψ μ j ξs x0 k ω) i
(saZ proj gψ μ j ξs x0 k i t ω)) (ξs k i t ω)‖ ^ 2 | innerField j ξs k i t]
≤ᵐ[P] fun _ => M i ^ 2)
(C : ℝ) (hC : ∀ i : Fin N, ‖x0 i - xs i‖ ≤ C)
(q : ℝ) (hcq : max (specNorm (Gamma X (payoff P ξ ψ) μ)) η < q) (hq1 : q < 1)
(D : ℝ) (hD : D = 1 / (Real.exp 1 *
Real.log (q / max (specNorm (Gamma X (payoff P ξ ψ) μ)) η)))
(ϵ : ℝ) (hϵ0 : 0 < ϵ) (hϵ1 : ϵ < Real.sqrt N * (C + D))
(K : ℕ) (hK : K = ⌈Real.log (Real.sqrt N * (C + D) / ϵ) / Real.log (1 / q)⌉₊) :
∫ ω, blockDist (syncSA proj gψ μ j ξs x0 K ω) xs ∂P ≤ ϵ ∧
∀ i : Fin N, ∑ k ∈ Finset.range K, (j i k : ℝ) ≤
Qconst X M μ i / (η ^ 4 * Real.log (1 / η ^ 2)) *
(Real.sqrt N * (C + D) / ϵ) ^ (Real.log (1 / η ^ 2) / Real.log (1 / q)) +
(⌈Real.log (Real.sqrt N * (C + D) / ϵ) / Real.log (1 / q)⌉₊ : ℝ) := by sorry
end LeiBR.Sync
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.