Lemma 4, pp. 764–765 — u_n = λγ_n^β satisfies u_{n+1} ≥ (1 − 2δγ_n)u_n + Cγ_n^{β+1} for n > n_0
DisprovedAdaptiveProtection.Convergence.lemma4_rate_recursionp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1ratesstep-sizesstochastic-approximation
Let with constants and , and let and . Then there exist , a finite and an index such that satisfies
In the proof of Theorem 1 this deterministic comparison sequence turns the recursion into the mean-square rate (10).
Formalization Note Powers are real powers of the positive numbers (; guarantees ). The constant is named lam.
Preamble
import Mathlib import Definitions.Def_NestedSeatAlloc_ProbCond_Model import Definitions.Def_AdaptiveProtection_Convergence_Setting open MeasureTheory Filter Topology
Formal statement
namespace AdaptiveProtection.Convergence
/-- Lemma 4 (pp. 764–765): with `γ_n = A/(n + B)`, there are `β > 0`, a finite `λ ≥ 0` and `n₀`
such that `u_n = λ γ_n^β` satisfies `u_{n+1} ≥ (1 − 2δγ_n) u_n + C γ_n^{β+1}` for all `n > n₀`. -/
theorem lemma4_rate_recursion
(A B δ C : ℝ) (hA : 0 < A) (hB : 0 ≤ B) (hδ : 0 < δ) (hC : 0 < C) :
∃ β > 0, ∃ lam : ℝ, 0 ≤ lam ∧ ∃ n₀ : ℕ, ∀ n : ℕ, n₀ < n →
(1 - 2 * δ * stepSize A B n) * (lam * stepSize A B n ^ β) + C * stepSize A B n ^ (β + 1)
≤ lam * stepSize A B (n + 1) ^ β := by sorry
end AdaptiveProtection.Convergence
Source
van Ryzin & McGill, Management Science 46(6), 2000, p. 764, Lemma 4 (adapted from Benveniste et al. 1990, Lemma 23); proof pp. 764–765
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.