Proof of Theorem 5, p. 9 — a proximal-gradient step gives
ProvedKarimiPL.Prox.descent_Dgdescentp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1proximal-gradient
Let be differentiable with an -Lipschitz continuous gradient, , let be convex, and write . Let and let be a proximal-gradient step from with step size , i.e. a minimizer over of
Then
This is the first part of the chain of inequalities in the proof of Theorem 5: the decrease of one proximal-gradient step is measured by , as the decrease of a gradient step is measured by in the smooth case.
Preamble
import Mathlib import Definitions.Def_KarimiPL_Prox_Setting open InnerProductSpace
Formal statement
namespace KarimiPL.Prox
theorem descent_Dg {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) :
∀ x y : EuclideanSpace ℝ (Fin d), (∀ z, proxModel f g x L y ≤ proxModel f g x L z) →
f y + g y ≤ f x + g x - 1 / (2 * L) * Dg f g x L := by sorry
end KarimiPL.Prox
Source
Karimi, Nutini, Schmidt, arXiv:1608.04636v4, proof of Theorem 5, first three lines of the display, p. 9
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.