Theorem 2, p. 7 — quasi-strong convexity (10) implies quadratic gradient growth (17) with the same κ
ProvedNecoaraNG.Chain.theorem_2p2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1quadratic-growthquasi-strong-convexity
Let be closed and convex, let be convex on , differentiable at every point of , with -Lipschitz gradient on (), and assume the optimal set is nonempty. Let and let . If is quasi-strongly convex with constant ,
then has quadratic gradient growth with the same constant:
In class notation: (18).
Formalization Note is written ; both inequalities are required for every nearest point .
Preamble
import Mathlib import Definitions.Def_NecoaraNG_Chain_Setting
Formal statement
namespace NecoaraNG.Chain
open scoped InnerProductSpace
/-- Theorem 2, p. 7: inequality (10) implies inequality (17), with the same constant `κ`. -/
theorem theorem_2 {n : ℕ} (X : Set (E n)) (hXc : IsClosed X) (hXconv : Convex ℝ X)
(f : E n → ℝ) (hf : ConvexOn ℝ X f) (hdiff : ∀ x ∈ X, DifferentiableAt ℝ f x)
(Lf : ℝ) (hLf : 0 < Lf)
(hL : ∀ x ∈ X, ∀ y ∈ X, ‖gradient f x - gradient f y‖ ≤ Lf * ‖x - y‖)
(xstar : E n) (hxstar : xstar ∈ optSet X f) (κ : ℝ) (hκ : 0 < κ) :
QuasiStrong X f κ → QuadGradGrowth X f κ := by sorry
end NecoaraNG.Chain
Source
Necoara, Nesterov & Glineur, Linear convergence of first order methods for non-strongly convex optimization, arXiv:1504.06298v4, p. 7, Theorem 2, (18)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.