Lemma 5 — −(L_f/2)‖y − x‖² ≤ Ψ(y) − Ψ(x) − ⟨∇Ψ(x), y − x⟩ ≤ (L_Ψ/2)‖y − x‖²
ProvedNonconvexAG.StochComposite.lemma_5composite-optimizationnonconvex-optimizationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let , where is differentiable with -Lipschitz gradient (possibly nonconvex) and is convex and differentiable with -Lipschitz gradient, and let . Then for all
The lower bound measures how far is from convex in terms of alone; it is what makes the final bound of Theorem 4 depend on rather than on in its non-convexity term.
Formalization Note is written out. Restated from mission 2 of this series because drafts cannot import one another.
Preamble
import Mathlib import Definitions.Def_ConvexOptAlg_SmoothGD_Defs import Definitions.Def_GhadimiLan_RSG_Model import Definitions.Def_NonconvexAG_StochComposite_ProxMap import Definitions.Def_NonconvexAG_StochComposite_RSAG open MeasureTheory ProbabilityTheory open scoped InnerProductSpace
Formal statement
namespace NonconvexAG.StochComposite
open GhadimiLan.RSG (E)
open ConvexOptAlg.SmoothGD
/-- Lemma 5 (p. 11), (2.43): `Ψ = f + h` with `f ∈ C^{1,1}_{L_f}`, `h ∈ C^{1,1}_{L_h}` convex,
`∇Ψ = ∇f + ∇h` and `L_Ψ = L_f + L_h`. -/
theorem lemma_5 {n : ℕ} (f h : E n → ℝ) (gf gh : E n → E n) (Lf Lh : ℝ)
(hf : IsBetaSmooth f gf Lf) (hh : IsBetaSmooth h gh Lh) (hhc : ConvexOn ℝ Set.univ h) :
∀ x y : E n,
-(Lf / 2) * ‖y - x‖ ^ 2 ≤ (f y + h y) - (f x + h x) - inner ℝ (gf x + gh x) (y - x) ∧
(f y + h y) - (f x + h x) - inner ℝ (gf x + gh x) (y - x) ≤
(Lf + Lh) / 2 * ‖y - x‖ ^ 2 := by sorry
end NonconvexAG.StochComposite
Source
Ghadimi & Lan, Accelerated Gradient Methods for Nonconvex Nonlinear and Stochastic Programming, arXiv:1310.3787v1, p. 11, Lemma 5, (2.43)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.