Lemma 1 — the Γ_k-weighted recursion bound θ_k ≤ Γ_k Σ_{i≤k} η_i/Γ_i
ProvedNonconvexAG.Stoch.lemma_1accelerated-gradientnonconvex-optimizationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let satisfy and for , and let , (), as in (2.6). If real sequences and satisfy
then for every
This unrolls the one-step recursion of the convex part of the analysis; in the proof of Theorem 3 b) it is applied to .
Formalization Note Sequences are functions on with 1-based indexing; is arbitrary (it is multiplied by ). is the product of the mission's definition file. This statement restates the paper's Lemma 1 locally in this mission, as in the companion missions of the series.
Preamble
import Mathlib import Definitions.Def_ConvexOptAlg_SmoothGD_Defs import Definitions.Def_GhadimiLan_RSG_Model import Definitions.Def_NonconvexAG_Stoch_RSAG open MeasureTheory ProbabilityTheory open scoped InnerProductSpace
Formal statement
namespace NonconvexAG.Stoch
open GhadimiLan.RSG (E)
/-- Lemma 1 (Ghadimi–Lan, arXiv:1310.3787v1, p. 4): if `α₁ = 1`, `αₖ ∈ (0, 1)` for `k ≥ 2`, and
`θₖ ≤ (1 − αₖ) θₖ₋₁ + ηₖ` for `k ≥ 1` (2.5), then `θₖ ≤ Γₖ Σ_{i=1}^{k} ηᵢ / Γᵢ` for `k ≥ 1`,
with `Γ` as in (2.6). -/
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.Stoch
Source
Ghadimi & Lan, Accelerated Gradient Methods for Nonconvex Nonlinear and Stochastic Programming, arXiv:1310.3787v1, p. 4, Lemma 1 (2.5)–(2.6)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.