Lemma 1 — convergence of a scalar stochastic approximation recursion
ProvedAsyncSA.Contraction.lemma1Let be an increasing filtration and let , , and be scalar random variables, with and measurable at time and measurable at time . Suppose has conditional mean zero and conditional second moment at most . Almost surely, let , , for one deterministic , and let the path be bounded. If satisfies
then almost surely. The initial scalar may be any finite random value.
This lemma controls the scalar noise recursion used in both convergence and boundedness arguments.
Formalization Note Conditional moments are generalized measurable-set statements, and both step-size series are encoded by partial sums. The paper's notation says is -measurable; the equivalent nonnegative-index condition is that is -measurable.
import Mathlib import Definitions.Def_AsyncSA_Contraction_Model
namespace AsyncSA.Contraction
open MeasureTheory Filter Topology
/-- Lemma 1, p. 190. The recursion may start from any finite random value. -/
theorem lemma1 {Ω : Type*} [m₀ : MeasurableSpace Ω]
(P : Measure Ω) [IsProbabilityMeasure P]
(𝓕 : Filtration ℕ m₀) (α w B W : ℕ → Ω → ℝ) (C : ℝ)
(hαmeas : ∀ t, Measurable[𝓕 t] (α t))
(hwmeas : ∀ t, Measurable[𝓕 (t + 1)] (w t))
(hBmeas : ∀ t, Measurable[𝓕 t] (B t))
(hmean : ∀ t, CondMeanZero m₀ (𝓕 t) P (w t))
(hsq : ∀ t, CondSqLe m₀ (𝓕 t) P (w t) (B t))
(hαmem : ∀ᵐ ω ∂P, ∀ t, α t ω ∈ Set.Icc (0 : ℝ) 1)
(hdiv : ∀ᵐ ω ∂P,
Tendsto (fun T => ∑ t ∈ Finset.range T, α t ω) atTop atTop)
(hsum : ∀ᵐ ω ∂P,
∀ T, ∑ t ∈ Finset.range T, α t ω ^ 2 ≤ C)
(hBbound : ∀ᵐ ω ∂P, ∃ K : ℝ, ∀ t, |B t ω| ≤ K)
(hW : ∀ t ω, W (t + 1) ω =
(1 - α t ω) * W t ω + α t ω * w t ω) :
∀ᵐ ω ∂P, Tendsto (fun t => W t ω) atTop (𝓝 0) := by sorry
end AsyncSA.Contraction
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.