(36)–(42), pp. 404–405 — under (33)–(35), (M(x) − α)/(x − θ) ≥ δM′(θ)/2A_n for 0 < |x − θ| ≤ A_n
ProvedRobbinsMonroSA.Conv.eq_42p2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1robbins-monrostochastic-approximation
Let be nondecreasing (33), with (34) and with derivative at (35). Then there is a constant such that for every with ,
Applied with (which tends to infinity), this gives (25) with , so Lemma 2 applies under (33)–(35).
Formalization Note This is a deterministic statement about any function . The paper's "we may assume without loss of generality that " is the hypothesis ; differentiability at is HasDerivAt M M' θ.
Preamble
import Mathlib import Definitions.Def_RobbinsMonroSA_Conv_Setting open MeasureTheory ProbabilityTheory Filter Topology
Formal statement
namespace RobbinsMonroSA.Conv
/-- (36)–(42), pp. 404–405. If `M` is nondecreasing with `M(θ) = α` and `M′(θ) > 0`, there is
`δ > 0` such that for every `A ≥ δ`, `(M(z) - α)/(z - θ) ≥ δ M′(θ) / 2A` on `0 < |z - θ| ≤ A`. -/
theorem eq_42 (M : ℝ → ℝ) (α θ M' : ℝ) (h33 : Monotone M) (h34 : M θ = α)
(h35 : HasDerivAt M M' θ) (h35pos : 0 < M') :
∃ δ : ℝ, 0 < δ ∧ ∀ A : ℝ, δ ≤ A → ∀ z : ℝ, 0 < |z - θ| → |z - θ| ≤ A →
δ * M' / (2 * A) ≤ (M z - α) / (z - θ) := by sorry
end RobbinsMonroSA.Conv
Source
Robbins and Monro, A stochastic approximation method, Ann. Math. Statist. 22 (1951), pp. 404–405, (33)–(42)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.