(2.22) — α_k⟨∇Ψ(x^md_k), x_{k−1} − x⟩ = (α_k/(2λ_k))[‖x_{k−1} − x‖² − ‖x_k − x‖²] + (α_kλ_k/2)‖∇Ψ(x^md_k)‖²
ProvedNonconvexAG.Smooth.eq_2_22accelerated-gradientnonconvex-optimizationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be generated by Algorithm 1 from with step sizes , (), , , using an arbitrary map . Then for every and every ,
The identity converts the linear term of (2.21) into a telescoping distance term.
Formalization Note The identity follows from (2.3) alone and 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.22), p. 7, for every `x ∈ ℝⁿ`. -/
theorem eq_2_22 {n : ℕ} (g : E n → E n) (α β lam : ℕ → ℝ) (hstep : AGStepsizes α β lam) (x0 : E n) :
∀ k, 1 ≤ k → ∀ x : E n,
α k * inner ℝ (g (xmdSeq g α β lam x0 k)) (xSeq g α β lam x0 (k - 1) - x) =
α k / (2 * lam k) * (‖xSeq g α β lam x0 (k - 1) - x‖ ^ 2 - ‖xSeq g α β lam x0 k - x‖ ^ 2)
+ α k * lam k / 2 * ‖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.22)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.