Lemma 3 — the SA inner loop (SA_{i,k}) reaches
ProvedLeiBR.Sync.lemma_3Assume Assumption 1 and , and let be the Euclidean projection onto . Run Algorithm 1 with the inner loop (SA) from a deterministic , with any step counts and measurable samples ; the sampled gradient map is measurable. Fix a major iteration and a player , and suppose that for every the sampled gradient satisfies ,
Let . Then for every ,
This is the standard rate of stochastic approximation for a -strongly convex problem, applied to each player's proximal BR problem; it tells how many SA steps achieve the accuracy (8).
Formalization Note Two repairs of the printed hypotheses. (i) The paper writes where it means the sampled gradient . (ii) Its second hypothesis, read literally, says , which would force zero sampling noise; the proof (p. 11) uses only the bound , which is what is assumed here. It follows from the literal hypothesis, Assumption 1(d) and Jensen, so the statement is no weaker than the printed one. and are generated by the samples; .
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
/-- Lemma 3, p. 10 (hypotheses repaired, see the statement): in Algorithm 1 with the inner loop
(SA_{i,k}), fix a major iteration `k` and a player `i`, and suppose that for every
`t = 1, …, j_{i,k}` the sampled gradient `G = ∇_{x_i}ψ_i(z_{i,t}, y_{-i,k}; ξ^t_{i,k})` has
`E‖G‖² < ∞`, `E[G | σ{F_k, ξ^{[t-1]}_{i,k}}] = ∇_{x_i} f_i(z_{i,t}, y_{-i,k})` a.s. and
`E[‖G‖² | σ{F_k, ξ^{[t-1]}_{i,k}}] ≤ M_i²` a.s. Then
`E[‖z_{i,t} - x̂_i(y_k)‖² | F_k] ≤ Q_i/(t+1)` a.s. for every `t = 1, …, j_{i,k}`, where
`Q_i = 2M_i²/μ² + 2D²_{X_i}`. -/
theorem lemma_3
{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 < μ)
(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)
(k : ℕ) (i : Fin N)
(hint : ∀ 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 : ∀ 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 : ∀ 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) :
∀ t : ℕ, 1 ≤ t → t ≤ j i k →
P[fun ω => ‖saZ proj gψ μ j ξs x0 k i t ω - xhat (syncSA proj gψ μ j ξs x0 k ω) i‖ ^ 2 |
infoField j ξs k] ≤ᵐ[P] fun _ => Qconst X M μ i / ((t : ℝ) + 1) := by sorry
end LeiBR.Sync
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.