Theorem 1 — gradient descent under PL converges at rate (1 − μ/L)^k
ProvedKarimiPL.GD.theorem_1gradient-descentlinear-convergencep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1polyak-lojasiewicz
Let be differentiable with an -Lipschitz gradient, where . Suppose is a global minimizer and satisfies the Polyak–Łojasiewicz inequality for every . Starting from any , define . Then, for every ,
This is the global function-value rate of Theorem 1. It applies without convexity and fixes the reference value to an attained global minimum.
Formalization Note The Lean statement permits and does not add . Its gradient denotes the derivative because differentiability is explicit. The minimizer hypothesis prevents the PL reference value from being chosen freely.
Preamble
import Mathlib import Definitions.Def_ShiOptrates_FunctionClass open scoped InnerProductSpace
Formal statement
namespace KarimiPL.GD
theorem theorem_1 {d : ℕ}
(f : EuclideanSpace ℝ (Fin d) → ℝ)
(hdiff : Differentiable ℝ f)
(L : ℝ) (hL : 0 < L)
(hLip : ∀ x y, ‖gradient f x - gradient f y‖ ≤ L * ‖x - y‖)
(xstar : EuclideanSpace ℝ (Fin d)) (hxstar : ∀ y, f xstar ≤ f y)
(mu : ℝ) (hmu : 0 < mu)
(hPL : ShiOptRates.PolyakLojasiewicz f (gradient f) mu (f xstar))
(x : ℕ → EuclideanSpace ℝ (Fin d))
(hx : ∀ k, x (k + 1) = x k - (1 / L) • gradient f (x k)) :
∀ k : ℕ, f (x k) - f xstar ≤ (1 - mu / L) ^ k * (f (x 0) - f xstar) := by sorry
end KarimiPL.GD
Source
Karimi, Nutini, Schmidt, arXiv:1608.04636v4, Theorem 1, equations (1)–(4), p. 2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.