Eq. (16):
ProvedStochApproxDyn.MartingaleNoise.moment_bound_eq16martingalesp2o-batch-pfp1ap2o-gran-per-chapterp2o-plan-paperp2o-v1stochastic-approximation
Let , given by (7), be a Robbins–Monro algorithm with noise in and step sequence , and suppose that for some
Then for every there is a constant such that for all
where is the noise deviation (10) of the realised noise path and is the step-size process.
This moment bound on the noise deviation over a window of length is what makes the windows summable in Eq. (17).
Formalization Note The moment hypothesis is a bound with on integrals in , and is also an integral in , so no default value of a non-integrable expectation enters. The constant may depend on , , the dimension, the moment bound and the step sequence, but not on .
Preamble
import Mathlib import Definitions.Def_StochApproxDyn_MartingaleNoise_Interpolation import Definitions.Def_StochApproxDyn_MartingaleNoise_AssumptionA1 import Definitions.Def_StochApproxDyn_MartingaleNoise_RobbinsMonro open MeasureTheory ProbabilityTheory Filter Topology open scoped ENNReal
Formal statement
namespace StochApproxDyn.MartingaleNoise
/-- Benaïm 1999, §4.2, proof of Proposition 4.2, Eq. (16), p. 15: for a Robbins–Monro algorithm
with `q ≥ 2` and `sup_n E‖U_{n+1}‖^q < ∞`, for every `T > 0` there is `C(q, T) > 0` (independent
of `t`) with `E(Δ(t, T)^q) ≤ C(q, T) ∫_t^{t+T} γ̄(s)^{q/2} ds` for all `t ≥ 0`. -/
theorem moment_bound_eq16 {d : ℕ} {Ω : Type*} {m0 : MeasurableSpace Ω}
(P : Measure Ω) [IsProbabilityMeasure P] (ℱ : Filtration ℕ m0)
(F : EuclideanSpace ℝ (Fin d) → EuclideanSpace ℝ (Fin d)) (γ : ℕ → ℝ)
(x U : ℕ → Ω → EuclideanSpace ℝ (Fin d)) (hRM : IsRobbinsMonro P ℱ F γ x U)
(q : ℝ) (hq : 2 ≤ q)
(hmom : ∃ M : ℝ≥0∞, M < ⊤ ∧ ∀ n : ℕ, ∫⁻ ω, ‖U (n + 1) ω‖ₑ ^ q ∂P ≤ M) :
∀ T : ℝ, 0 < T → ∃ C : ℝ, 0 < C ∧ ∀ t : ℝ, 0 ≤ t →
∫⁻ ω, noiseDev γ (fun n => U n ω) t T ^ q ∂P ≤
ENNReal.ofReal C * ∫⁻ s in Set.Icc t (t + T), ENNReal.ofReal (stepPath γ s ^ (q / 2)) := by sorry
end StochApproxDyn.MartingaleNoise
Source
Benaïm, Dynamics of Stochastic Approximation Algorithms, Séminaire de Probabilités XXXIII, LNM 1709 (1999), DOI 10.1007/BFb0096509, Section 4.2, proof of Proposition 4.2, p. 15 (PDF p. 16), Eq. (16)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.