Lemma 1 — θ_k ≤ (1−α_k)θ_{k−1} + η_k implies θ_k ≤ Γ_k Σ_{i≤k} η_i/Γ_i
ProvedNonconvexAG.Composite.lemma_1accelerated-gradientnonconvex-optimizationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be step sizes with and for , and let be defined by (2.6): , for . If real sequences , satisfy
then for every
This unrolls the one-step recursion of the AG method into a weighted sum; in the proof of Theorem 2 it turns the one-step bound (2.51) into the summed bound after it.
Formalization Note Sequences are indexed by ℕ, and is arbitrary (at it is multiplied by ). 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_NonconvexAG_Composite_ProxMap import Definitions.Def_NonconvexAG_Composite_AGRun
Formal statement
namespace NonconvexAG.Composite
open ConvexOptAlg.SmoothGD
/-- Lemma 1 (p. 4). -/
theorem lemma_1 (α : ℕ → ℝ) (hα1 : α 1 = 1) (hα : ∀ k, 2 ≤ k → 0 < α k ∧ α k < 1)
(θ η : ℕ → ℝ) (h : ∀ k, 1 ≤ k → θ k ≤ (1 - α k) * θ (k - 1) + η k) :
∀ k, 1 ≤ k → θ k ≤ NonconvexAG.Smooth.Gamma α k * ∑ i ∈ Finset.Icc 1 k, η i / NonconvexAG.Smooth.Gamma α i := by sorry
end NonconvexAG.Composite
Source
Ghadimi & Lan, Accelerated Gradient Methods for Nonconvex Nonlinear and Stochastic Programming, arXiv:1310.3787v1, p. 4, Lemma 1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.