Lemma 1 — W(t+1) = (1 − α(t))W(t) + α(t)w(t) converges to 0 w.p.1 for martingale-difference noise with bounded conditional variance
ProvedAsyncSA.Monotone.lemma1Let be a probability space and an increasing sequence of σ-fields. For each let , and be -measurable scalar random variables, and let be a deterministic constant. Suppose that, with probability 1,
- for all ;
- for all ;
- for all ;
- ;
- ;
and that the sequence is bounded with probability 1. Let satisfy
with arbitrary. Then
This is the scalar stochastic approximation result on which the convergence analysis of the asynchronous algorithm rests: in §5 it is applied, component by component, to the accumulated noise .
Formalization Note The conditional expectations are generalized: (1) means for every on which is integrable, and (2) means in for every ; no integrability of is assumed, as in the paper. (4) is divergence of the partial sums to and (5) bounds every partial sum by . " is -measurable" is written as " is -measurable". The boundedness of is on almost every sample path, with a bound that may depend on the path. The recursion holds on every sample path, and is an arbitrary (not necessarily measurable) function.
import Mathlib import Definitions.Def_AsyncSA_Monotone_Model
namespace AsyncSA.Monotone
open MeasureTheory Filter Topology
theorem lemma1 {Ω : Type*} [m0 : MeasurableSpace Ω] (P : Measure Ω) [IsProbabilityMeasure P]
(𝓕 : Filtration ℕ m0) (α w B W : ℕ → Ω → ℝ) (C : ℝ)
(hα_meas : ∀ t, Measurable[𝓕 t] (α t))
(hw_meas : ∀ t, Measurable[𝓕 (t + 1)] (w t))
(hB_meas : ∀ t, Measurable[𝓕 t] (B t))
(ha : ∀ t, CondMeanZero (𝓕 t) P (w t))
(hb : ∀ t, CondSqLe (𝓕 t) P (w t) (B t))
(hc : ∀ᵐ ω ∂P, ∀ t, α t ω ∈ Set.Icc (0 : ℝ) 1)
(hd : ∀ᵐ ω ∂P, Tendsto (fun T => ∑ t ∈ Finset.range T, α t ω) atTop atTop)
(he : ∀ᵐ ω ∂P, ∀ T, ∑ t ∈ Finset.range T, α t ω ^ 2 ≤ C)
(hB_bdd : ∀ᵐ ω ∂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.Monotone
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.