§2, equation (2) — an L-Lipschitz gradient gives the quadratic upper bound
ProvedKarimiPL.GD.quadUpper_of_lipschitzgradient-descentlinear-convergencep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1polyak-lojasiewicz
Let be differentiable and let its gradient be -Lipschitz: for all . Then, for all ,
This is the smoothness inequality (2) used in the rate proof. It relates the paper's Lipschitz-gradient assumption to the quadratic upper-bound predicate reused by the one-step results.
Formalization Note The statement does not require : the implication from a Lipschitz bound to the displayed inequality also covers the degenerate point space . The main theorem assumes because its step size divides by .
Preamble
import Mathlib import Definitions.Def_ShiOptrates_FunctionClass open scoped InnerProductSpace
Formal statement
namespace KarimiPL.GD
theorem quadUpper_of_lipschitz {d : ℕ}
(f : EuclideanSpace ℝ (Fin d) → ℝ)
(hdiff : Differentiable ℝ f)
(L : ℝ) (hLip : ∀ x y, ‖gradient f x - gradient f y‖ ≤ L * ‖x - y‖) :
ShiOptRates.QuadUpper f (gradient f) L := by sorry
end KarimiPL.GD
Source
Karimi, Nutini, Schmidt, arXiv:1608.04636v4, §2, equation (2) and preceding sentence, p. 2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.