(2.50) — the combined prox inequality under α_kλ_k ≤ β_k
ProvedNonconvexAG.Composite.eq_2_50accelerated-gradientcomposite-optimizationnonconvex-optimizationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
In the setting of (2.48)–(2.49) ( convex on its domain , a prox map, Algorithm 2 with , for , ), let satisfy . Then for every
It combines the two prox inequalities with the convexity of ; the condition (the first half of (2.9)) removes the term in .
Formalization Note Only the outer ends of the printed chain are stated. At the term vanishes because , so no assumption is made.
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.50), p. 12 (outer ends of the chain), for every `k ≥ 1` with `αₖλₖ ≤ βₖ` and every `x` in
the domain `K` of `𝒳`. -/
theorem eq_2_50 {n : ℕ} (gΨ : NonconvexAG.Smooth.E n → NonconvexAG.Smooth.E n) (K : Set (NonconvexAG.Smooth.E n)) (X : NonconvexAG.Smooth.E n → ℝ)
(hX : ConvexOn ℝ K X) (P : NonconvexAG.Smooth.E n → NonconvexAG.Smooth.E n → ℝ → NonconvexAG.Smooth.E n) (hP : IsProxMap K X P)
(α β lam : ℕ → ℝ) (hstep : NonconvexAG.Smooth.AGStepsizes α β lam) (x0 : NonconvexAG.Smooth.E n) :
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 → α k * lam k ≤ β k → ∀ x ∈ K,
inner ℝ (gΨ (xmd k)) (xag k - α k • x - (1 - α k) • xag (k - 1)) + X (xag k) ≤
(1 - α k) * X (xag (k - 1)) + α k * X x +
α k / (2 * lam k) * (‖xk (k - 1) - x‖ ^ 2 - ‖xk k - x‖ ^ 2) -
1 / (2 * β k) * ‖xag k - xmd k‖ ^ 2 := by sorry
end NonconvexAG.Composite
Source
Ghadimi & Lan, Accelerated Gradient Methods for Nonconvex Nonlinear and Stochastic Programming, arXiv:1310.3787v1, p. 12, (2.50)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.