(23)–(24), p. 403 — d_n ≥ k̄_n b_n, k̄_n = inf (M(x) − α)/(x − θ) over 0 < |x − θ| ≤ A_n
ProvedRobbinsMonroSA.Conv.eq_24p2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1robbins-monrostochastic-approximation
Under (4) with constant , (5), positive step sizes , and the process (7)–(8), let
Then for every ,
Hence the particular sequence satisfies the first part of (19) in Lemma 1.
Formalization Note Indices are 0-based (bigA … n is the paper's ). The infimum is not formed in Lean: the statement says that every lower bound of on satisfies . Since is the greatest such lower bound, this is equivalent to (24) (with ), and it also covers the case of an empty range (, where the infimum is and Lean's real infimum would be ).
Preamble
import Mathlib import Definitions.Def_RobbinsMonroSA_Conv_Setting open MeasureTheory ProbabilityTheory Filter Topology
Formal statement
namespace RobbinsMonroSA.Conv
/-- (23)–(24), p. 403, in lower-bound form. If `k` bounds `(M(z) - α)/(z - θ)` from below on
`0 < |z - θ| ≤ A_n` (so `k ≤ k̄_n`, the infimum of (23)), then `d_n ≥ k b_n`. -/
theorem eq_24 {Ω : 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) α θ) (hpos : ∀ n, 0 < a n) :
∀ n, ∀ k : ℝ,
(∀ z : ℝ, 0 < |z - θ| → |z - θ| ≤ bigA x1 θ C α a n →
k ≤ (regressionFn H z - α) / (z - θ)) →
k * msd P x θ n ≤ dSeq P H α θ x n := by sorry
end RobbinsMonroSA.Conv
Source
Robbins and Monro, A stochastic approximation method, Ann. Math. Statist. 22 (1951), p. 403, (23)–(24)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.