§2.1, display before (2.16) — x^ag_k − x_k = Γ_k Σ_{τ≤k} ((λ_τ − β_τ)/Γ_τ) ∇Ψ(x^md_τ)
ProvedNonconvexAG.Smooth.eq_before_2_16accelerated-gradientnonconvex-optimizationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be generated by Algorithm 1 from with step sizes , (), , , using an arbitrary map in place of the gradient, and let be as in (2.6). Then for every ,
The identity writes the gap between the two sequences of the AG method as a -weighted combination of the past gradients; it is the input to the bound (2.17).
Formalization Note The identity is algebraic: it is stated for any map g (no smoothness of is assumed), which includes the gradient of the paper.
Preamble
import Mathlib import Definitions.Def_ConvexOptAlg_SmoothGD_Defs import Definitions.Def_NonconvexAG_Smooth_AGRun
Formal statement
namespace NonconvexAG.Smooth
/-- The identity displayed before (2.16), p. 6. -/
theorem eq_before_2_16 {n : ℕ} (g : E n → E n) (α β lam : ℕ → ℝ) (hstep : AGStepsizes α β lam) (x0 : E n) :
∀ k, 1 ≤ k →
xagSeq g α β lam x0 k - xSeq g α β lam x0 k =
Gamma α k • ∑ τ ∈ Finset.Icc 1 k, ((lam τ - β τ) / Gamma α τ) • g (xmdSeq g α β lam x0 τ) := by sorry
end NonconvexAG.Smooth
Source
Ghadimi & Lan, Accelerated Gradient Methods for Nonconvex Nonlinear and Stochastic Programming, arXiv:1310.3787v1, p. 6, §2.1, display before (2.16)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.