(2.16) — Σ_{τ=1}^k α_τ/Γ_τ = 1/Γ_k
ProvedNonconvexAG.Composite.eq_2_16accelerated-gradientnonconvex-optimizationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let , for , and let be given by (2.6). Then for every
The identity follows from for . In Theorem 2 it gives the last inequality of (2.53).
Formalization Note Only the outer ends of the printed chain are stated. Restated from mission 1 of this series.
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.16), p. 6 (outer ends of the chain). -/
theorem eq_2_16 (α : ℕ → ℝ) (hα1 : α 1 = 1) (hα : ∀ k, 2 ≤ k → 0 < α k ∧ α k < 1) :
∀ k, 1 ≤ k → ∑ τ ∈ Finset.Icc 1 k, α τ / NonconvexAG.Smooth.Gamma α τ = 1 / NonconvexAG.Smooth.Gamma α k := by sorry
end NonconvexAG.Composite
Source
Ghadimi & Lan, Accelerated Gradient Methods for Nonconvex Nonlinear and Stochastic Programming, arXiv:1310.3787v1, p. 6, (2.16)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.