(2.16) — Σ_{τ=1}^k α_τ/Γ_τ = 1/Γ_k
ProvedNonconvexAG.StochComposite.eq_2_16accelerated-gradientp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let , for , and as in (2.6). Then for every
In the proof of Theorem 4 this identity collects the -terms of the summed inequality into .
Formalization Note Restated from mission 1 of this series because drafts cannot import one another.
Preamble
import Mathlib import Definitions.Def_ConvexOptAlg_SmoothGD_Defs import Definitions.Def_GhadimiLan_RSG_Model import Definitions.Def_NonconvexAG_StochComposite_ProxMap import Definitions.Def_NonconvexAG_StochComposite_RSAG open MeasureTheory ProbabilityTheory open scoped InnerProductSpace
Formal statement
namespace NonconvexAG.StochComposite
open GhadimiLan.RSG (E)
open ConvexOptAlg.SmoothGD
/-- (2.16), p. 6 (outer ends of the chain): `Σ_{τ=1}^k α_τ/Γ_τ = 1/Γ_k` for every `k ≥ 1`. -/
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.StochComposite
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.