Theorem 3, p. 5 — randomized coordinate descent under PL
ProvedKarimiPL.RCD.theorem_3coordinate-descentlinear-convergencep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1polyak-lojasiewiczrandomized-algorithms
Let . Let be differentiable, obey the coordinate-wise upper bound (5) with , attain its minimum , and satisfy the PL inequality for some . From any , independently draw uniformly from the coordinates at each step and set . Then, for every ,
This is the expected linear rate of Theorem 3. It covers differentiable objectives satisfying PL without requiring convexity.
Formalization Note Independent uniform draws are represented by averaging over all words of length , each with weight . The minimum value is fixed by an explicit global minimizer. The one-sided coordinate bound (5), rather than a full gradient-Lipschitz assumption, is the smoothness hypothesis.
Preamble
import Mathlib import Definitions.Def_KarimiPL_RCD_Setting import Definitions.Def_ShiOptrates_FunctionClass
Formal statement
namespace KarimiPL.RCD
/-- Theorem 3, p. 5: the expected rate of randomized coordinate descent under PL. -/
theorem theorem_3 {d : ℕ} (hd : 0 < d) (f : KarimiPL.Rel.E d → ℝ)
(hdiff : Differentiable ℝ f) (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))
(x0 : KarimiPL.Rel.E d) :
∀ k : ℕ,
expectedGap f L x0 (f xstar) k ≤
(1 - mu / ((d : ℝ) * L)) ^ k * (f x0 - f xstar) := by sorry
end KarimiPL.RCD
Source
Karimi, Nutini, Schmidt, arXiv:1608.04636v4, Theorem 3, p. 5
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.