Lemma 8 (horizon-restricted measurability) — the SA inner loop (43) reaches conditional mean-square error
OpenLeiBR.Async.lemma_8_uptoLet Assumption 1(a)–(b) hold and , let be the proximal best-response map, and let be the Euclidean projection onto . Fix a player , a major iteration , a horizon , and a sub--algebra . Let be an -measurable outdated profile, and run (43) from with samples . The -algebras increase with , satisfy (they play the role of ), and are sub--algebras of the ambient one for ; the samples that enter the iterates , i.e. those with , are -measurable; and the sampled-gradient map is jointly measurable. Assume that for the sampled gradient satisfies
(with integrable). Then for ,
This is Lemma 8 with the measurability requirements restricted to the indices the iterates actually use. It is the form needed in the proof of Theorem 3, whose hypotheses only guarantee for ; and it implies LeiBR.Async.lemma_8 directly.
Formalization Note Same repairs as LeiBR.Async.lemma_8: the page writes for , and its literal second-moment hypothesis (an equality with ) is replaced by the bound that the proof uses. Compared with lemma_8, the hypotheses (ambient -algebra) are assumed only for , and the measurability of only for (the last sample only feeds ).
import Mathlib import Definitions.Def_SpectralProjGrad_Shared_IsProjOnto import Definitions.Def_LeiBR_Async_Game import Definitions.Def_LeiBR_Async_Model import Definitions.Def_LeiBR_Async_Algorithm
namespace LeiBR.Async
open MeasureTheory
/-- Lemma 8 (§5.3, p. 19), error of the stochastic approximation inner loop (43), with the
measurability hypotheses required only up to the horizon `j`. In major iteration `k`, player `i`
starts (43) from its own coordinate of the `F_k`-measurable outdated profile `y = y^i_k ∈ X`
(so `z_1 = y_i = x_{i,k}`). The σ-algebras `G_t ⊇ F_k` play the role of `σ{F_k, ξ^{[t−1]}_{i,k}}`; they
are sub-σ-algebras of the ambient one for `t ≤ j`, and the samples `ξ^t` used by the iterates
`z_2, …, z_j` (that is, `t < j`) are `G_{t+1}`-measurable. If for `t = 1, …, j` the sampled gradients
are conditionally unbiased with conditional second moment at most `M_i²` (`IsSAOracle`), then for
`t = 1, …, j`, `E[‖z_t − x̂_i(y)‖² | F_k] ≤ Q_i/(t + 1)` a.s., with `Q_i = 2M_i²/μ² + 2D²_{X_i}`.
Formalization Note: identical to `LeiBR.Async.lemma_8` except that `G t ≤ mΩ` is assumed only for
`t ≤ j` and `ξ t` is assumed `G (t+1)`-measurable only for `t < j` (the last sample `ξ^j` only feeds
`z_{j+1}`); this is the form in which Theorem 3's hypotheses supply the inner-loop σ-algebras. -/
theorem lemma_8_upto {Ω : Type*} (Fk : MeasurableSpace Ω) [mΩ : MeasurableSpace Ω] (P : Measure Ω) [IsProbabilityMeasure P]
{N d : ℕ} {n : Fin N → ℕ} (X : ∀ i, Set (LeiBR.Sync.Strat n i)) (f : Fin N → LeiBR.Sync.Profile n → ℝ)
(hA1 : Assumption1ab X f) (μ : ℝ) (hμ : 0 < μ) (xhat : LeiBR.Sync.Profile n → LeiBR.Sync.Profile n)
(hxhat : LeiBR.Sync.IsProxBR X f μ xhat) (M : Fin N → ℝ)
(gψ : ∀ i, LeiBR.Sync.Profile n → EuclideanSpace ℝ (Fin d) → LeiBR.Sync.Strat n i)
(hgψ : ∀ i, Measurable (Function.uncurry (gψ i)))
(proj : ∀ i, LeiBR.Sync.Strat n i → LeiBR.Sync.Strat n i)
(hproj : ∀ i, SpectralProjGrad.Shared.IsProjOnto (X i) (proj i))
(i : Fin N) (j : ℕ) (hFk : Fk ≤ mΩ) (G : ℕ → MeasurableSpace Ω)
(hG : ∀ t, t ≤ j → G t ≤ mΩ) (hFG : Fk ≤ G 1) (hGmono : ∀ t, G t ≤ G (t + 1))
(y : Ω → LeiBR.Sync.Profile n) (hy : Measurable[Fk] y) (hyX : ∀ ω, y ω ∈ profileSet X)
(ξ : ℕ → Ω → EuclideanSpace ℝ (Fin d))
(hξ : ∀ t, t < j → Measurable[G (t + 1)] (ξ t))
(horacle : IsSAOracle P f gψ proj μ M i y ξ G j) :
∀ t, 1 ≤ t → t ≤ j →
P[fun ω => ‖saPath proj gψ μ i (y ω) (fun s => ξ s ω) t - xhat (y ω) i‖ ^ 2 | Fk]
≤ᵐ[P] fun _ => LeiBR.Sync.Qconst X M μ i / ((t : ℝ) + 1) := by sorry
end LeiBR.Async