Lemma 4.2 — geometric decay of a delayed nonnegative recursion ([1, Lemma 1])
ProvedPLIAG.lemma_4_2bregman-distanceconvex-optimizationincremental-gradientp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let and be nonnegative sequences of real numbers satisfying
where , , , , and for . Assume moreover
Then for all .
The lemma, due to Aytekin, Feyzmahdavian and Johansson, turns a one-step contraction perturbed by the last increments into a clean geometric rate, provided the penalty dominates the accumulated perturbation.
Differences from the source:
- encoding: w_k = 0 for k < 0 and Σ_{j=k−k_0}^k → sequences indexed by ℕ, Σ over Finset.Icc (k − k_0) k with truncated subtraction; reason: for k < k_0 the range is {0, …, k}, exactly the paper’s nonzero terms; each index counted once
Preamble
import Mathlib
Formal statement
namespace PLIAG
/-- **Lemma 4.2** (Zhang–Dai–Guo–Peng, arXiv:1711.01136v3, p.12; Aytekin–Feyzmahdavian–Johansson
[1, Lemma 1]). Let `{V_k}`, `{w_k}` be nonnegative sequences with
`V_{k+1} ≤ a V_k − b w_k + c Σ_{j=k−k_0}^k w_j` for all `k ≥ 0`, where `a ∈ (0, 1)`, `b ≥ 0`,
`c ≥ 0`, `k_0 ≥ 0`, `w_k = 0` for `k < 0`, and `(c/(1−a)) · (1 − a^{k_0+1})/a^{k_0} ≤ b` (4.4).
Then `V_k ≤ a^k V_0` for all `k ≥ 0`.
**Formalization Note.** Real sequences indexed by `ℕ`. The convention `w_k = 0` for `k < 0` is
encoded by summing over `Finset.Icc (k − k_0) k` with truncated subtraction: for `k < k_0` this
is `{0, …, k}`, exactly the paper's nonzero terms. -/
theorem lemma_4_2 (V wseq : ℕ → ℝ) (a b c : ℝ) (k₀ : ℕ)
(hV : ∀ k, 0 ≤ V k) (hw : ∀ k, 0 ≤ wseq k)
(ha0 : 0 < a) (ha1 : a < 1) (hb : 0 ≤ b) (hc : 0 ≤ c)
(hrec : ∀ k, V (k + 1) ≤ a * V k - b * wseq k + c * ∑ j ∈ Finset.Icc (k - k₀) k, wseq j)
(hcond : c / (1 - a) * ((1 - a ^ (k₀ + 1)) / a ^ k₀) ≤ b) :
∀ k, V k ≤ a ^ k * V 0 := by sorry
end PLIAG
Source
Zhang, Dai, Guo, Peng, Proximal-Like Incremental Aggregated Gradient Method with Linear Convergence under Bregman Distance Growth Conditions, arXiv:1711.01136v3, Lemma 4.2, p.12
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.