p. 402, after (14) — from (5) d_n ≥ 0, and from (4) 0 ≤ e_n ≤ [C + |α|]²
ProvedRobbinsMonroSA.Conv.dSeq_nonneg_eSeq_boundp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1robbins-monrostochastic-approximation
Under the boundedness condition (4) with constant , condition (5) on the regression function , and the process (7)–(8), for every ,
where and .
These sign and size facts turn the identity (14) into a supermartingale-type recursion for .
Formalization Note Indices are 0-based. All standing assumptions of §3 used by the claim, (4), (5) and (7)–(8), are hypotheses; (6) is not needed.
Preamble
import Mathlib import Definitions.Def_RobbinsMonroSA_Conv_Setting open MeasureTheory ProbabilityTheory Filter Topology
Formal statement
namespace RobbinsMonroSA.Conv
/-- p. 402, after (14). From (5), `d_n ≥ 0`; from (4), `0 ≤ e_n ≤ [C + |α|]²`. -/
theorem dSeq_nonneg_eSeq_bound {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω) [IsProbabilityMeasure P]
(H : Kernel ℝ ℝ) [IsMarkovKernel H] (C : ℝ) (h4 : BoundedResponse H C) (α θ : ℝ)
(a : ℕ → ℝ) (x1 : ℝ) (x y : ℕ → Ω → ℝ) (hxy : IsRMProcess P H a α x1 x y)
(h5 : CrossesAt (regressionFn H) α θ) :
∀ n, 0 ≤ dSeq P H α θ x n ∧ 0 ≤ eSeq P H α x n ∧ eSeq P H α x n ≤ (C + |α|) ^ 2 := by sorry
end RobbinsMonroSA.Conv
Source
Robbins and Monro, A stochastic approximation method, Ann. Math. Statist. 22 (1951), p. 402, after (14)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.