Lemma E.1 — growth of sequences with
ProvedAnchoredEP.lemma_E_1higher-order-methodsmonotone-inclusionoptimizationp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a positive, nondecreasing sequence of real numbers, and let and . If
then for every ,
Applied with , it turns the stability estimate into polynomial growth of the cumulative step size.
Differences from the source:
- encoding: a sequence {B_k}_{k≥1} → B : ℕ → ℝ with every hypothesis and the conclusion for k ≥ 1; reason: the value B 0 is unused
Preamble
import Mathlib
Formal statement
namespace AnchoredEP
/-- **Lemma E.1 (sequence growth, [BJLLS19, Lemma 12]).** Jiang–Yoon, arXiv:2609.30212,
Lemma E.1, p.27: "Let `{B_k}_{k≥1}` be a positive, nondecreasing sequence. If there exist
constants `α > 1` and `c > 0` such that `B_k^α ≥ c ∑_{j=1}^k B_j` for every `k ≥ 1`, then
`B_k ≥ ((α − 1)/α · c k)^{1/(α−1)}`."
**Formalization Note.** The sequence is `B : ℕ → ℝ`, of which only the indices `k ≥ 1` matter; the
powers `B_k^α` and `(…)^{1/(α−1)}` are real powers (`Real.rpow`), with `α` real. -/
theorem lemma_E_1 (B : ℕ → ℝ) (hpos : ∀ k, 1 ≤ k → 0 < B k)
(hmono : ∀ k, 1 ≤ k → B k ≤ B (k + 1)) (α c : ℝ) (hα : 1 < α) (hc : 0 < c)
(hrec : ∀ k, 1 ≤ k → c * ∑ j ∈ Finset.Icc 1 k, B j ≤ B k ^ α) :
∀ k, 1 ≤ k → ((α - 1) / α * c * k) ^ (1 / (α - 1)) ≤ B k := by sorry
end AnchoredEP
Source
Jiang–Yoon, Anchored Extra-Proximal Methods: Optimal Higher-Order Methods for Monotone Inclusion Problems, arXiv:2609.30212, Lemma E.1 ([BJLLS19, Lemma 12]), p.27
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.