Lemma 1 — θ_k ≤ (1−α_k)θ_{k−1} + η_k implies θ_k ≤ Γ_k Σ_{i≤k} η_i/Γ_i
ProvedNonconvexAG.Smooth.lemma_1accelerated-gradientnonconvex-optimizationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let satisfy and for , and let be defined by (2.6): , for . Let and be real sequences with
Then for every ,
This unrolling of a damped linear recursion is used twice in the proof of Theorem 1: with equality, to express through the past gradients, and with to sum the one-step bound (2.23).
Formalization Note The sequences are functions ℕ → ℝ; is arbitrary (its coefficient vanishes).
Preamble
import Mathlib import Definitions.Def_ConvexOptAlg_SmoothGD_Defs import Definitions.Def_NonconvexAG_Smooth_AGRun
Formal statement
namespace NonconvexAG.Smooth
/-- 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 ≤ Gamma α k * ∑ i ∈ Finset.Icc 1 k, η i / Gamma α i := by sorry
end NonconvexAG.Smooth
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.