Lemma 5 — −(L_f/2)‖y−x‖² ≤ Ψ(y) − Ψ(x) − ⟨∇Ψ(x), y−x⟩ ≤ (L_Ψ/2)‖y−x‖²
ProvedNonconvexAG.Composite.lemma_5nonconvex-optimizationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1smooth-optimization
Let as in (1.3): is differentiable with -Lipschitz gradient (possibly nonconvex), is convex and differentiable with -Lipschitz gradient, and . Then for all
The upper bound is the usual quadratic bound for an -smooth function; the lower bound improves the constant from to , because the convex part contributes only a nonnegative term. This is what lets the analysis of Algorithm 2 depend on , and reduce to the convex rate when .
Formalization Note Smoothness is IsBetaSmooth f gf Lf (differentiable with gradient map gf, Lf ≥ 0, gradient Lf-Lipschitz), and likewise for h; and are written out as f y + h y and gf x + gh x.
Preamble
import Mathlib import Definitions.Def_ConvexOptAlg_SmoothGD_Defs import Definitions.Def_NonconvexAG_Composite_ProxMap import Definitions.Def_NonconvexAG_Composite_AGRun
Formal statement
namespace NonconvexAG.Composite
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 : NonconvexAG.Smooth.E n → ℝ) (gf gh : NonconvexAG.Smooth.E n → NonconvexAG.Smooth.E n) (Lf Lh : ℝ)
(hf : IsBetaSmooth f gf Lf) (hh : IsBetaSmooth h gh Lh) (hhc : ConvexOn ℝ Set.univ h) :
∀ x y : NonconvexAG.Smooth.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.Composite
Source
Ghadimi & Lan, Accelerated Gradient Methods for Nonconvex Nonlinear and Stochastic Programming, arXiv:1310.3787v1, p. 11, Lemma 5 (2.43); the setting is (1.3), p. 2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.