Lemma 3.2, pp. 540–541 — one-step Bregman descent inequality (13)
ProvedChenTeboullePMD.Rate.lemma_3_2Let be a proper lower semicontinuous convex extended-valued objective with effective domain , let be a Bregman function with zone containing the relative interior of , and let be a PMD run with positive steps . For every and ,
This is the one-step estimate from which the weighted telescoping bound follows.
Formalization Note The ambient space is any finite-dimensional real normed space, with gradients represented by covectors. The extended objective is encoded by and real on . The page's outside has and yields a trivial extended-valued comparison; the displayed real inequality covers its nontrivial domain. The PMD run predicate replaces the assumption that is onto, which the page uses to ensure the iterates exist.
import Mathlib import Definitions.Def_BeckTeboulleMD_EMDA_Setting import Definitions.Def_ChenTeboullePMD_Rate_Setting
namespace ChenTeboullePMD.Rate
open BeckTeboulleMD.EMDA
/-- Lemma 3.2, display (13), pp. 540–541. -/
theorem lemma_3_2 {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) :
∀ k : ℕ, ∀ u ∈ C, u ∈ closure S →
lam (k + 1) * (f (x (k + 1)) - f u) ≤
bregman ψ u (x k) - bregman ψ u (x (k + 1)) -
bregman ψ (x (k + 1)) (x k) := by sorry
end ChenTeboullePMD.Rate
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.