Theorem 5, p. 8 — under the proximal-PL inequality, proximal gradient with step gives
ProvedKarimiPL.Prox.theorem_5composite-optimizationlinear-convergencep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1polyak-lojasiewiczproximal-gradient
Consider problem (11), minimizing over , where:
- is differentiable and its gradient is -Lipschitz continuous, , with ;
- is convex;
- has a non-empty solution set: there is with for all ; write ;
- satisfies the proximal-PL inequality (12) with some : for all , where
Let be generated by the proximal-gradient method with step size from an arbitrary :
Then for every ,
This is the paper's linear convergence result for the proximal-gradient method without strong convexity. When is constant it reduces to Theorem 1 for gradient descent under the PL inequality.
Formalization Note is real-valued, so the indicator functions mentioned on p. 8 as examples of are outside the formal scope. The update (14) is encoded by requiring each to be a minimizer; the minimizer is unique for convex , but uniqueness is not used. No relation between and is assumed, as on the page.
Preamble
import Mathlib import Definitions.Def_KarimiPL_Prox_Setting open InnerProductSpace
Formal statement
namespace KarimiPL.Prox
theorem theorem_5 {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 : ℕ → EuclideanSpace ℝ (Fin d)) (hrun : IsProxGradRun f g L x) :
∀ k : ℕ, (f (x k) + g (x k)) - (f xstar + g xstar)
≤ (1 - μ / L) ^ k * ((f (x 0) + g (x 0)) - (f xstar + g xstar)) := by sorry
end KarimiPL.Prox
Source
Karimi, Nutini, Schmidt, arXiv:1608.04636v4, Theorem 5, p. 8
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.