Theorem 1, p. 6 — quasi-strong convexity (10) implies quadratic under-approximation (13) with the same κ
ProvedNecoaraNG.Chain.theorem_1p2o-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 write for a nearest point of to and for the optimal value. If
then
In class notation: (14). Convexity of is essential: (10) alone does not even imply convexity.
Formalization Note is written ; both inequalities are required for every nearest point (which is unique here).
Preamble
import Mathlib import Definitions.Def_NecoaraNG_Chain_Setting
Formal statement
namespace NecoaraNG.Chain
open scoped InnerProductSpace
/-- Theorem 1, p. 6: inequality (10) implies inequality (13), with the same constant `κ`. -/
theorem theorem_1 {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 κ → QuadUnder 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. 6, Theorem 1, (14)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.