Proof of Theorem 3, p. 5 — uniform expected decrease
ProvedKarimiPL.RCD.expected_cdStep_decreasecoordinate-descentdescent-inequalityexpectationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let and suppose obeys (5) with . Draw one coordinate uniformly from the coordinates and set . For every ,
The averaged decrease relates a random coordinate update to the full gradient norm. It is the middle displayed chain in the proof of Theorem 3.
Formalization Note The expectation is a finite average; makes the uniform distribution well defined.
Preamble
import Mathlib import Definitions.Def_KarimiPL_RCD_Setting
Formal statement
namespace KarimiPL.RCD
/-- Uniformly averaged decrease in the proof of Theorem 3, p. 5. -/
theorem expected_cdStep_decrease {d : ℕ} (hd : 0 < d) (f : KarimiPL.Rel.E d → ℝ) (L : ℝ)
(hL : 0 < L) (hcoord : CoordLipschitz f L) :
∀ x : KarimiPL.Rel.E d,
(1 / (d : ℝ)) * ∑ i : Fin d, f (cdStep f L x i) ≤
f x - 1 / (2 * (d : ℝ) * L) * ‖gradient f x‖ ^ 2 := by sorry
end KarimiPL.RCD
Source
Karimi, Nutini, Schmidt, arXiv:1608.04636v4, proof of Theorem 3, expected-decrease display, p. 5
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.