Proposition 4.1, proof, p. 13 — the affine and piecewise constant interpolations differ by at most 2Δ(t − 1, T + 1) + K sup γ̄
ProvedStochApproxDyn.Interpolation.interpAffine_sub_interpConst_lep2o-batch-pfp1ap2o-gran-per-chapterp2o-plan-paperp2o-v1stochastic-approximation
Let be continuous, let the step sizes satisfy , , , and let follow the scheme . Suppose for all . Then there is such that for all and all ,
In the proof of Proposition 4.1 this estimate shows that uniformly on windows of length once A1 holds, so that may be replaced by in Eq. (9).
Formalization Note "For large enough" is the existential threshold , chosen independently of ; makes a quantity on . The bound is a hypothesis on the iterates; in the paper it comes from A2 and the continuity of (A2′ also yields it). Both suprema are real suprema over bounded nonempty sets: takes finitely many values on .
Preamble
import Mathlib import Definitions.Def_StochApproxDyn_Interpolation_Scheme open scoped NNReal Topology open Filter
Formal statement
namespace StochApproxDyn.Interpolation
/-- Benaïm 1999, proof of Proposition 4.1, p. 13: if `‖F(x_n)‖ ≤ K` for all `n`, then for all `t`
large enough (with `t ≥ 1`) and every `T > 0`,
`sup_{t≤u≤t+T} ‖X(u) − X̄(u)‖ ≤ 2Δ(t − 1, T + 1) + sup_{t≤u≤t+T} K γ̄(u)`.
The threshold does not depend on `T`. -/
theorem interpAffine_sub_interpConst_le {d : ℕ}
(F : EuclideanSpace ℝ (Fin d) → EuclideanSpace ℝ (Fin d)) (hF : Continuous F)
(γ : ℕ → ℝ) (hγ : IsStepSizeSeq γ) (x U : ℕ → EuclideanSpace ℝ (Fin d))
(hx : SatisfiesScheme F γ x U) (K : ℝ) (hK : ∀ n : ℕ, ‖F (x n)‖ ≤ K) :
∃ t₀ : ℝ, 1 ≤ t₀ ∧ ∀ t : ℝ, t₀ ≤ t → ∀ T : ℝ, 0 < T → ∀ u ∈ Set.Icc t (t + T),
‖interpAffine γ x u - interpConst γ x u‖ ≤
2 * Delta γ U (t - 1) (T + 1) +
sSup ((fun v => K * stepInterp γ v) '' Set.Icc t (t + T)) := by sorry
end StochApproxDyn.Interpolation
Source
Benaïm, Dynamics of Stochastic Approximation Algorithms, Séminaire de Probabilités XXXIII, LNM 1709 (1999), p. 13, proof of Proposition 4.1 (display following "Thus")
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.