(2.13) — ‖∇Ψ(x_{k−1}) − ∇Ψ(x^md_k)‖ ≤ L_Ψ(1 − α_k)‖x^ag_{k−1} − x_{k−1}‖
ProvedNonconvexAG.Smooth.eq_2_13accelerated-gradientnonconvex-optimizationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be differentiable with for all , where . Run Algorithm 1 from with step sizes , (), , . Then for every , with ,
It bounds the discrepancy between the gradient at the previous iterate and at the middle point, which enters the one-step descent estimate (2.15).
Formalization Note The statement is the outer ends of the chain (2.13). The gradient is the map g with IsBetaSmooth Ψ g LΨ.
Preamble
import Mathlib import Definitions.Def_ConvexOptAlg_SmoothGD_Defs import Definitions.Def_NonconvexAG_Smooth_AGRun
Formal statement
namespace NonconvexAG.Smooth
/-- (2.13), p. 5 (outer ends of the chain). -/
theorem eq_2_13 {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) :
∀ k, 1 ≤ k →
‖g (xSeq g α β lam x0 (k - 1)) - g (xmdSeq g α β lam x0 k)‖ ≤
LΨ * (1 - α k) * ‖xagSeq g α β lam x0 (k - 1) - xSeq g α β lam x0 (k - 1)‖ := by sorry
end NonconvexAG.Smooth
Source
Ghadimi & Lan, Accelerated Gradient Methods for Nonconvex Nonlinear and Stochastic Programming, arXiv:1310.3787v1, p. 5, (2.13)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.