(63), Appendix H, p. 23 — E[F(x_{k+1})] ≤ F(x_k) − (1/(2Ld)) D_g(x_k, L) under uniform coordinate choice
ProvedKarimiPL.ProxCD.expected_descent_63coordinate-descentexpected-descentp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1proximal-gradient
Let , let be differentiable and satisfy the coordinate-wise -Lipschitz upper bound (5), , let with each convex, and . Let be any coordinate proximal-gradient step (16) from along coordinate , i.e. with a minimizer of . Then for every ,
The left side is given when is uniform on .
This expected-descent inequality, combined with the proximal-PL inequality, gives the contraction factor of Theorem 6.
Formalization Note The conditional expectation over a uniform coordinate is written as the average over the coordinates. The page writes for and for .
Preamble
import Mathlib import Definitions.Def_KarimiPL_ProxCD_Setting open InnerProductSpace
Formal statement
namespace KarimiPL.ProxCD
theorem expected_descent_63 {d : ℕ} (hd : 0 < d) (f : KarimiPL.Rel.E d → ℝ) (hdiff : Differentiable ℝ f)
(L : ℝ) (hL : 0 < L)
(hCoord : ∀ (x : KarimiPL.Rel.E d) (i : Fin d) (t : ℝ),
f (x + t • EuclideanSpace.single i (1 : ℝ)) ≤ f x + t * gradient f x i + L / 2 * t ^ 2)
(gs : Fin d → ℝ → ℝ) (hgs : ∀ i, ConvexOn ℝ Set.univ (gs i))
(sel : KarimiPL.Rel.E d → Fin d → KarimiPL.Rel.E d) (hsel : ∀ x i, IsProxCoordStep f gs L x i (sel x i)) :
∀ x : KarimiPL.Rel.E d, (1 / (d : ℝ)) * ∑ i, (f (sel x i) + sepSum gs (sel x i))
≤ (f x + sepSum gs x) - 1 / (2 * L * d) * Dg f (sepSum gs) x L := by sorry
end KarimiPL.ProxCD
Source
Karimi, Nutini, Schmidt, arXiv:1608.04636v4, Appendix H, (63), p. 23
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.