(2.25) — Σ_{k≤N} (α_k/(λ_kΓ_k))[‖x_{k−1} − x‖² − ‖x_k − x‖²] ≤ ‖x_0 − x‖²/λ_1
ProvedNonconvexAG.Smooth.eq_2_25accelerated-gradientnonconvex-optimizationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be generated by Algorithm 1 from with step sizes , (), , , using an arbitrary map ; as in (2.6). Let and suppose (2.10) holds on : for . Then for every ,
This weighted telescoping bound is the second inequality in (2.24).
Formalization Note The statement is the outer ends of (2.25) (the middle term is and ). It is stated for any map g.
Preamble
import Mathlib import Definitions.Def_ConvexOptAlg_SmoothGD_Defs import Definitions.Def_NonconvexAG_Smooth_AGRun
Formal statement
namespace NonconvexAG.Smooth
/-- (2.25), p. 7 (outer ends), under (2.10) for `k = 1, …, N`, for every `x ∈ ℝⁿ`. -/
theorem eq_2_25 {n : ℕ} (g : E n → E n) (α β lam : ℕ → ℝ) (hstep : AGStepsizes α β lam) (x0 : E n) (N : ℕ) (hN : 1 ≤ N)
(h210 : ∀ k ∈ Finset.Icc 1 N, 2 ≤ k →
α k / (lam k * Gamma α k) ≤ α (k - 1) / (lam (k - 1) * Gamma α (k - 1))) :
∀ x : E n,
∑ k ∈ Finset.Icc 1 N,
α k / (lam k * Gamma α k) * (‖xSeq g α β lam x0 (k - 1) - x‖ ^ 2 - ‖xSeq g α β lam x0 k - x‖ ^ 2) ≤
‖x0 - x‖ ^ 2 / lam 1 := by sorry
end NonconvexAG.Smooth
Source
Ghadimi & Lan, Accelerated Gradient Methods for Nonconvex Nonlinear and Stochastic Programming, arXiv:1310.3787v1, p. 7, (2.25)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.