Theorem 2, p. 405 — steps of type 1/n, (4), M nondecreasing with M(θ) = α and M′(θ) > 0 imply E(x_n − θ)² → 0
ProvedRobbinsMonroSA.Conv.theorem_2Let be the distribution functions of the responses , with regression function , and suppose that there is a constant with
Let be a sequence of type : positive constants with and . Suppose that is nondecreasing, and . Let be an arbitrary constant and
Then
This is the main theorem of Robbins and Monro (1951): the stochastic approximation iterates converge in mean square to the root of , no matter what the initial value .
Formalization Note Indices are 0-based (x 0 is ). is a Markov kernel (IsMarkovKernel); (8) is the joint-law equation of the process (see the Setting definition). Condition (5) follows from (33)–(34) and (6) is part of "type ", so neither is a separate hypothesis. is HasDerivAt (regressionFn H) M' θ with 0 < M'. No Markov property beyond (8) is assumed.
import Mathlib import Definitions.Def_RobbinsMonroSA_Conv_Setting open MeasureTheory ProbabilityTheory Filter Topology
namespace RobbinsMonroSA.Conv
/-- Theorem 2, p. 405. If `{a_n}` is of type `1/n`, if (4) holds, and if `M(x)` satisfies
(33) nondecreasing, (34) `M(θ) = α` and (35) `M′(θ) > 0`, then `lim b_n = 0`, whatever `x₁`. -/
theorem theorem_2 {Ω : 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)
(ha : IsTypeOneOverN a) (h33 : Monotone (regressionFn H)) (h34 : regressionFn H θ = α)
(M' : ℝ) (h35 : HasDerivAt (regressionFn H) M' θ) (h35pos : 0 < M') :
Tendsto (fun n => msd P x θ n) atTop (𝓝 0) := by sorry
end RobbinsMonroSA.Conv
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.