(2.19) — Ψ(x_N) ≤ Ψ(x_0) − Σ_{k=1}^N λ_kC_k‖∇Ψ(x^md_k)‖²
ProvedNonconvexAG.Smooth.eq_2_19accelerated-gradientnonconvex-optimizationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be differentiable with -Lipschitz gradient, , and let be generated by Algorithm 1 from with step sizes , (), , . For a horizon let , , be defined by (2.7). Then
No sign condition on is needed here; under (2.7) the bound yields Theorem 1 a).
Formalization Note The statement is the outer ends of the chain (2.19) and is stated for every (at it reads ).
Preamble
import Mathlib import Definitions.Def_ConvexOptAlg_SmoothGD_Defs import Definitions.Def_NonconvexAG_Smooth_AGRun
Formal statement
namespace NonconvexAG.Smooth
/-- (2.19), p. 6 (outer ends of the chain), for every horizon `N`. -/
theorem eq_2_19 {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) (N : ℕ) :
Ψ (xSeq g α β lam x0 N) ≤
Ψ x0 - ∑ k ∈ Finset.Icc 1 N, lam k * C LΨ α β lam N 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. 6, (2.19)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.