Proof of Theorem 3, p. 5 — one-step expected gap contraction
ProvedKarimiPL.RCD.expected_cdStep_contractioncoordinate-descentexpectationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1polyak-lojasiewicz
Let , , and let obey the coordinate-wise upper bound (5). Suppose is a global minimizer, , and satisfies the Polyak–Łojasiewicz (PL) inequality for some . If is uniform over the coordinates, then for every ,
This is the conditional one-step contraction used in Theorem 3. The minimizer fixes the optimal value; it is not an independently chosen lower bound.
Formalization Note The published PL predicate is written with both sides multiplied by two. The expectation is an explicit finite average.
Preamble
import Mathlib import Definitions.Def_KarimiPL_RCD_Setting import Definitions.Def_ShiOptrates_FunctionClass
Formal statement
namespace KarimiPL.RCD
/-- Conditional expected contraction in the proof of Theorem 3, p. 5. -/
theorem expected_cdStep_contraction {d : ℕ} (hd : 0 < d)
(f : KarimiPL.Rel.E d → ℝ) (L : ℝ) (hL : 0 < L) (hcoord : CoordLipschitz f L)
(xstar : KarimiPL.Rel.E d) (hxstar : ∀ y, f xstar ≤ f y)
(mu : ℝ) (hmu : 0 < mu)
(hPL : ShiOptRates.PolyakLojasiewicz f (gradient f) mu (f xstar)) :
∀ x : KarimiPL.Rel.E d,
(1 / (d : ℝ)) * ∑ i : Fin d, (f (cdStep f L x i) - f xstar) ≤
(1 - mu / ((d : ℝ) * L)) * (f x - f xstar) := by sorry
end KarimiPL.RCD
Source
Karimi, Nutini, Schmidt, arXiv:1608.04636v4, proof of Theorem 3, final displayed inequality, p. 5
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.