(2.47) — the L_f-corrected convexity gap at x^md_k
ProvedNonconvexAG.Composite.eq_2_47accelerated-gradientcomposite-optimizationnonconvex-optimizationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be as in (1.3) and Lemma 5 ( -smooth, convex and -smooth, ), and run Algorithm 2 with step sizes satisfying , (), , any prox map and any starting point . Then for every and every ,
For convex (the case ) this is the familiar convexity step of accelerated methods; the two -terms measure the price of nonconvexity of .
Formalization Note Only the outer ends of the printed chain are stated. The prox map plays no role here beyond defining the iterates.
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
/-- (2.47), p. 12 (outer ends of the chain), for Algorithm 2 on `Ψ = f + h`, every `k ≥ 1` and
every `x ∈ ℝⁿ`. -/
theorem eq_2_47 {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)
(P : NonconvexAG.Smooth.E n → NonconvexAG.Smooth.E n → ℝ → NonconvexAG.Smooth.E n) (α β lam : ℕ → ℝ) (hstep : NonconvexAG.Smooth.AGStepsizes α β lam) (x0 : NonconvexAG.Smooth.E n) :
let Ψ : NonconvexAG.Smooth.E n → ℝ := fun x => f x + h x
let gΨ : NonconvexAG.Smooth.E n → NonconvexAG.Smooth.E n := fun x => gf x + gh x
let xk : ℕ → NonconvexAG.Smooth.E n := xSeq gΨ P α β lam x0
let xag : ℕ → NonconvexAG.Smooth.E n := xagSeq gΨ P α β lam x0
let xmd : ℕ → NonconvexAG.Smooth.E n := xmdSeq gΨ P α β lam x0
∀ k, 1 ≤ k → ∀ x : NonconvexAG.Smooth.E n,
Ψ (xmd k) - ((1 - α k) * Ψ (xag (k - 1)) + α k * Ψ x) ≤
inner ℝ (gΨ (xmd k)) (xmd k - α k • x - (1 - α k) • xag (k - 1)) +
Lf * α k / 2 * ‖xmd k - x‖ ^ 2 +
Lf * α k ^ 2 * (1 - α k) / 2 * ‖xag (k - 1) - xk (k - 1)‖ ^ 2 := by sorry
end NonconvexAG.Composite
Source
Ghadimi & Lan, Accelerated Gradient Methods for Nonconvex Nonlinear and Stochastic Programming, arXiv:1310.3787v1, p. 12, (2.47)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.