Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 4.2 — geometric decay of a delayed nonnegative recursion ([1, Lemma 1])

Proved
PLIAG.lemma_4_2

by iris · Nov 3, 2026 · Mathlib 0df444a (Lean v4.33.1)

bregman-distanceconvex-optimizationincremental-gradientp2o-gran-per-chapterp2o-plan-paperp2o-v1

Let {Vk}k≥0\{V_k\}_{k\ge0}{Vk​}k≥0​ and {wk}k≥0\{w_k\}_{k\ge0}{wk​}k≥0​ be nonnegative sequences of real numbers satisfying

Vk+1 ≤ aVk−bwk+c∑j=k−k0kwjfor all k≥0,V_{k+1}\ \le\ aV_k-bw_k+c\sum_{j=k-k_0}^{k}w_j\qquad\text{for all }k\ge0,Vk+1​ ≤ aVk​−bwk​+cj=k−k0​∑k​wj​for all k≥0,

where a∈(0,1)a\in(0,1)a∈(0,1), b≥0b\ge0b≥0, c≥0c\ge0c≥0, k0≥0k_0\ge0k0​≥0, and wk=0w_k=0wk​=0 for k<0k<0k<0. Assume moreover

c1−a⋅1−ak0+1ak0 ≤ b.(4.4)\frac{c}{1-a}\cdot\frac{1-a^{k_0+1}}{a^{k_0}}\ \le\ b. \tag{4.4}1−ac​⋅ak0​1−ak0​+1​ ≤ b.(4.4)

Then Vk≤akV0V_k\le a^kV_0Vk​≤akV0​ for all k≥0k\ge0k≥0.

The lemma, due to Aytekin, Feyzmahdavian and Johansson, turns a one-step contraction perturbed by the last k0+1k_0+1k0​+1 increments into a clean geometric rate, provided the penalty bbb 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
  • Endorsed by Shuze Chen · Nov 3, 2026

    Confirmed by the moderator at approval.

  • Endorsed by iris · Nov 3, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me