Lemma 3.3(iii), pp. 541–542 — weighted telescoping estimate
ProvedChenTeboullePMD.Rate.lemma_3_3_iiibregman-functionconvergence-rateconvex-optimizationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1proximal-point
Under Lemma 3.2's standing assumptions, let . For every and ,
This is the weighted estimate that gives Theorem 3.4's rate after the nonnegative terms are removed.
Formalization Note The weights are exactly ; the sum uses a zero-based Lean range with as the paper index. The real inequality covers in the effective domain, where the page's extended objective is finite. The space is finite dimensional and the run predicate supplies existing zone-valued iterates.
Preamble
import Mathlib import Definitions.Def_BeckTeboulleMD_EMDA_Setting import Definitions.Def_ChenTeboullePMD_Rate_Setting
Formal statement
namespace ChenTeboullePMD.Rate
open BeckTeboulleMD.EMDA
/-- Lemma 3.3(iii), pp. 541–542. -/
theorem lemma_3_3_iii {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E]
[FiniteDimensional ℝ E]
(S : Set E) (ψ : E → ℝ) (hψ : IsBregmanFunction S ψ)
(C : Set E) (hCne : C.Nonempty) (hCconv : Convex ℝ C)
(f : E → ℝ) (hf : ConvexOn ℝ C f)
(hlsc : LowerSemicontinuous (extendTop C f))
(hri : intrinsicInterior ℝ C ⊆ S)
(lam : ℕ → ℝ) (hlam : ∀ k, 1 ≤ k → 0 < lam k)
(x : ℕ → E) (hrun : IsPMDRun S C ψ f lam x) :
∀ n, 1 ≤ n → ∀ u ∈ C, u ∈ closure S →
sigma lam n * (f (x n) - f u) ≤
bregman ψ u (x 0) - bregman ψ u (x n) -
∑ k ∈ Finset.range n,
(lam (k + 1))⁻¹ * sigma lam (k + 1) *
bregman ψ (x (k + 1)) (x k) := by sorry
end ChenTeboullePMD.Rate
Source
Chen & Teboulle, Convergence analysis of a proximal-like minimization algorithm using Bregman functions, SIAM J. Optim. 3 (1993), pp. 541–542, Lemma 3.3(iii)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.