Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 2 — uniform smallness of late noise tails

Proved
AsyncSA.Contraction.lemma2

by mikedeng1 · Oct 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

martingalep2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1stochastic-approximation

Under the scalar filtration, step-size, and conditional-noise conditions of Lemma 1, define the zero-start tail W(t;t0)W(t;t_0)W(t;t0​) by W(t0;t0)=0W(t_0;t_0)=0W(t0​;t0​)=0 and W(t+1;t0)=(1−α(t))W(t;t0)+α(t)w(t)W(t+1;t_0)=(1-\alpha(t))W(t;t_0)+\alpha(t)w(t)W(t+1;t0​)=(1−α(t))W(t;t0​)+α(t)w(t) for t≥t0t\ge t_0t≥t0​. Almost surely, for every δ>0\delta>0δ>0, there is a time TTT such that

∣W(t;t0)∣≤δwhenever T≤t0≤t.|W(t;t_0)|\le\delta\qquad\text{whenever }T\le t_0\le t.∣W(t;t0​)∣≤δwhenever T≤t0​≤t.

The uniformity in both the starting and ending times lets later arguments restart the noise recursion after delayed information has become sufficiently recent.

Formalization Note On p. 192 the paper states this for the rescaled noise w~i(t)=wi(t)/G(t)\widetilde w_i(t)=w_i(t)/G(t)wi​(t)=wi​(t)/G(t). The preceding page establishes that the rescaled process satisfies Lemma 1's conditions; this statement records the same conclusion for any scalar process satisfying those conditions. The tail is zero before its start time as well.

Preamble
import Mathlib
import Definitions.Def_AsyncSA_Contraction_Model
Formal statement
namespace AsyncSA.Contraction

open MeasureTheory Filter Topology

/-- Lemma 2, p. 192, for any scalar noise process satisfying Lemma 1's conditions. -/
theorem lemma2 {Ω : Type*} [m₀ : MeasurableSpace Ω]
    (P : Measure Ω) [IsProbabilityMeasure P]
    (𝓕 : Filtration ℕ m₀) (α w B : ℕ → Ω → ℝ) (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) :
    ∀ᵐ ω ∂P, ∀ δ : ℝ, 0 < δ →
      ∃ T : ℕ, ∀ t₀ t : ℕ, T ≤ t₀ → t₀ ≤ t →
        |tailW (fun s => α s ω) (fun s => w s ω) t₀ t| ≤ δ := by sorry

end AsyncSA.Contraction
Source
Tsitsiklis, Asynchronous Stochastic Approximation and Q-Learning, Machine Learning 16 (1994), pp. 191–192, §4, rescaled noise and Lemma 2
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me