(2.42) — 𝒢(x^md_k, ∇Ψ(x^md_k), β_k) = (x^md_k − x^ag_k)/β_k
ProvedNonconvexAG.Composite.eq_2_42accelerated-gradientcomposite-optimizationnonconvex-optimizationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Consider Algorithm 2 with any gradient map , any prox map , any step sizes and any starting point. For every , the gradient mapping (2.38) at the middle iterate with step is the scaled difference of the middle and the aggregated iterates:
This identity, immediate from (2.38) and (2.41), converts the bound on obtained in the proof of Theorem 2 into the bound (2.44) on the gradient mapping, the termination criterion of the method.
Preamble
import Mathlib import Definitions.Def_ConvexOptAlg_SmoothGD_Defs import Definitions.Def_NonconvexAG_Composite_ProxMap import Definitions.Def_NonconvexAG_Composite_AGRun
Formal statement
namespace NonconvexAG.Composite
open ConvexOptAlg.SmoothGD
/-- (2.42), p. 11: along Algorithm 2, the gradient mapping at `x^md_k` with step `βₖ` is
`(x^md_k − x^ag_k)/βₖ`. -/
theorem eq_2_42 {n : ℕ} (gΨ : NonconvexAG.Smooth.E n → NonconvexAG.Smooth.E n) (P : NonconvexAG.Smooth.E n → NonconvexAG.Smooth.E n → ℝ → NonconvexAG.Smooth.E n) (α β lam : ℕ → ℝ) (x0 : NonconvexAG.Smooth.E n) :
∀ k, 1 ≤ k →
gradMap P (xmdSeq gΨ P α β lam x0 k) (gΨ (xmdSeq gΨ P α β lam x0 k)) (β k) =
(1 / β k) • (xmdSeq gΨ P α β lam x0 k - xagSeq gΨ P α β lam x0 k) := by sorry
end NonconvexAG.Composite
Source
Ghadimi & Lan, Accelerated Gradient Methods for Nonconvex Nonlinear and Stochastic Programming, arXiv:1310.3787v1, p. 11, (2.42)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.