(2.23) — the one-step bound for Ψ(x^ag_k) under (2.9), Ψ convex
ProvedNonconvexAG.Smooth.eq_2_23accelerated-gradientnonconvex-optimizationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be convex and differentiable with -Lipschitz gradient, , and let be generated by Algorithm 1 from with step sizes , (), , . Let satisfy (2.9), . Then for every ,
It has the form (2.5) of Lemma 1 with , which is how it is summed into (2.24).
Formalization Note The statement is the outer ends of the chain (2.23); (2.9) is assumed at the index only.
Preamble
import Mathlib import Definitions.Def_ConvexOptAlg_SmoothGD_Defs import Definitions.Def_NonconvexAG_Smooth_AGRun
Formal statement
namespace NonconvexAG.Smooth
/-- (2.23), p. 7 (outer ends of the chain), for convex `Ψ`, under (2.9) at step `k`,
for every `x ∈ ℝⁿ`. -/
theorem eq_2_23 {n : ℕ} (Ψ : E n → ℝ) (g : E n → E n) (LΨ : ℝ)
(hΨ : ConvexOptAlg.SmoothGD.IsBetaSmooth Ψ g LΨ) (hL : 0 < LΨ)
(α β lam : ℕ → ℝ) (hstep : AGStepsizes α β lam) (x0 : E n) (hconv : ConvexOn ℝ Set.univ Ψ) :
∀ k, 1 ≤ k → α k * lam k ≤ β k → β k < 1 / LΨ → ∀ x : E n,
Ψ (xagSeq g α β lam x0 k) ≤ (1 - α k) * Ψ (xagSeq g α β lam x0 (k - 1)) + α k * Ψ x
+ α k / (2 * lam k) * (‖xSeq g α β lam x0 (k - 1) - x‖ ^ 2 - ‖xSeq g α β lam x0 k - x‖ ^ 2)
- β k / 2 * (1 - LΨ * β k) * ‖g (xmdSeq g α β lam x0 k)‖ ^ 2 := by sorry
end NonconvexAG.Smooth
Source
Ghadimi & Lan, Accelerated Gradient Methods for Nonconvex Nonlinear and Stochastic Programming, arXiv:1310.3787v1, p. 7, (2.23)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.