(62), Appendix H, p. 23 — F(x + t e_i) − F(x) ≤ t∇_i f(x) + (L/2)t² + g_i(x_i + t) − g_i(x_i)
ProvedKarimiPL.ProxCD.coord_upper_62coordinate-descentdescent-lemmap2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1proximal-gradient
Let be differentiable and satisfy the coordinate-wise -Lipschitz condition (5), : for every . Let be separable, with arbitrary real-valued , and . Then for every point , coordinate and step ,
This is the coordinate-wise upper model that the proximal coordinate step (16) minimizes; it is the first step of the proof of Theorem 6.
Formalization Note The coordinate-wise condition is stated in the exact upper-bound form (5). The full -Lipschitz gradient assumed in Theorem 6 implies it. The page writes for in the last term.
Preamble
import Mathlib import Definitions.Def_KarimiPL_ProxCD_Setting open InnerProductSpace
Formal statement
namespace KarimiPL.ProxCD
theorem coord_upper_62 {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 → ℝ → ℝ) :
∀ (x : KarimiPL.Rel.E d) (i : Fin d) (t : ℝ),
(f (x + t • EuclideanSpace.single i (1 : ℝ)) + sepSum gs (x + t • EuclideanSpace.single i (1 : ℝ)))
- (f x + sepSum gs x) ≤ coordModel f gs L x i t := by sorry
end KarimiPL.ProxCD
Source
Karimi, Nutini, Schmidt, arXiv:1608.04636v4, Appendix H, (62), p. 23
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.