Theorem 6, p. 10 — randomized proximal coordinate descent (16) satisfies E[F(x_k) − F*] ≤ (1 − μ/(dL))^k [F(x_0) − F*] under proximal-PL
ProvedKarimiPL.ProxCD.theorem_6Consider with , where
- is differentiable and its gradient is -Lipschitz, : ;
- is separable, each convex;
- has a minimizer , and ;
- satisfies the proximal-PL inequality with constant : for all , , where .
Run the coordinate-wise proximal-gradient method from : at step draw uniformly from , independently of the past, and set with
Then for every ,
This extends the linear rate of randomized coordinate descent under PL (Theorem 3) and of proximal-gradient under proximal-PL (Theorem 5) to the proximal coordinate method, without strong convexity.
Formalization Note The expectation is the exact average over all index words , each of probability . The update is any step selection satisfying (16); since the one-dimensional minimizer is unique there is exactly one. Equation (16) as printed assigns the minimizing step to ; the iterate (Appendix H) is encoded. The are real-valued; extended-valued such as box indicators (§4.4) are outside this formalization. The minimum in is a real infimum, attained for convex and .
import Mathlib import Definitions.Def_KarimiPL_ProxCD_Setting open InnerProductSpace
namespace KarimiPL.ProxCD
theorem theorem_6 {d : ℕ} (hd : 0 < d) (f : KarimiPL.Rel.E d → ℝ) (hdiff : Differentiable ℝ f)
(L : ℝ) (hL : 0 < L) (hLip : ∀ x y : KarimiPL.Rel.E d, ‖gradient f x - gradient f y‖ ≤ L * ‖x - y‖)
(gs : Fin d → ℝ → ℝ) (hgs : ∀ i, ConvexOn ℝ Set.univ (gs i))
(xstar : KarimiPL.Rel.E d) (hxstar : ∀ y, f xstar + sepSum gs xstar ≤ f y + sepSum gs y)
(μ : ℝ) (hμ : 0 < μ) (hPPL : ProxPL f (sepSum gs) L μ (f xstar + sepSum gs xstar))
(sel : KarimiPL.Rel.E d → Fin d → KarimiPL.Rel.E d) (hsel : ∀ x i, IsProxCoordStep f gs L x i (sel x i))
(x0 : KarimiPL.Rel.E d) :
∀ k : ℕ, expectedGap (fun x => f x + sepSum gs x) sel x0 (f xstar + sepSum gs xstar) k
≤ (1 - μ / (d * L)) ^ k * ((f x0 + sepSum gs x0) - (f xstar + sepSum gs xstar)) := by sorry
end KarimiPL.ProxCD
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.