Proof of Theorem 3, p. 5 — one coordinate step decreases f
ProvedKarimiPL.RCD.cdStep_decreasecoordinate-descentdescent-inequalityp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let . Suppose obeys the coordinate-wise upper bound (5) with . For any point and coordinate , take the step . Then
This is the one-coordinate decrease stated at the start of the proof of Theorem 3. It applies to every chosen coordinate, before averaging over random choices.
Preamble
import Mathlib import Definitions.Def_KarimiPL_RCD_Setting
Formal statement
namespace KarimiPL.RCD
/-- First displayed inequality in the proof of Theorem 3, p. 5. -/
theorem cdStep_decrease {d : ℕ} (hd : 0 < d) (f : KarimiPL.Rel.E d → ℝ) (L : ℝ)
(hL : 0 < L) (hcoord : CoordLipschitz f L) :
∀ (x : KarimiPL.Rel.E d) (i : Fin d),
f (cdStep f L x i) ≤ f x - 1 / (2 * L) * (gradient f x i) ^ 2 := by sorry
end KarimiPL.RCD
Source
Karimi, Nutini, Schmidt, arXiv:1608.04636v4, proof of Theorem 3, first displayed inequality, p. 5
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.