(15), p. 9 — one proximal-gradient step gives
ProvedKarimiPL.Prox.one_step_15linear-convergencep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1polyak-lojasiewiczproximal-gradient
Let be differentiable with an -Lipschitz continuous gradient, , let be convex, and write . Suppose has a minimizer , write , and suppose satisfies the proximal-PL inequality (12) with :
Let and let minimize . Then
This is the one-step contraction of the proof of Theorem 5; applying it along the iterates gives the theorem.
Preamble
import Mathlib import Definitions.Def_KarimiPL_Prox_Setting open InnerProductSpace
Formal statement
namespace KarimiPL.Prox
theorem one_step_15 {d : ℕ} (f g : EuclideanSpace ℝ (Fin d) → ℝ)
(hdiff : Differentiable ℝ f) (L : ℝ) (hL : 0 < L)
(hLip : ∀ x y, ‖gradient f x - gradient f y‖ ≤ L * ‖x - y‖)
(hg : ConvexOn ℝ Set.univ g)
(xstar : EuclideanSpace ℝ (Fin d)) (hxstar : ∀ y, f xstar + g xstar ≤ f y + g y)
(μ : ℝ) (hμ : 0 < μ) (hPPL : ProxPL f g L μ (f xstar + g xstar)) :
∀ x y : EuclideanSpace ℝ (Fin d), (∀ z, proxModel f g x L y ≤ proxModel f g x L z) →
(f y + g y) - (f xstar + g xstar) ≤ (1 - μ / L) * ((f x + g x) - (f xstar + g xstar)) := by sorry
end KarimiPL.Prox
Source
Karimi, Nutini, Schmidt, arXiv:1608.04636v4, proof of Theorem 5, (15), p. 9
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.