Proof of Theorem 4, p. 9 — quadratic under-approximation (13) implies quadratic functional growth (22) with the same κ
ProvedNecoaraNG.Chain.quadUnder_imp_funGrowthp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1quadratic-growth
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
then
In class notation: , the last link of (23).
Formalization Note is written . The paper's standing assumptions are kept as hypotheses; the implication only needs the first-order optimality condition at .
Preamble
import Mathlib import Definitions.Def_NecoaraNG_Chain_Setting
Formal statement
namespace NecoaraNG.Chain
open scoped InnerProductSpace
/-- Proof of Theorem 4, p. 9: inequality (13) implies inequality (22), with the same constant `κ`. -/
theorem quadUnder_imp_funGrowth {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 < κ) :
QuadUnder X f κ → QuadFunGrowth 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. 9, proof of Theorem 4, first two sentences
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.