(2.47) — the L_f-corrected convexity gap at x^md_k, along Algorithm 4
ProvedNonconvexAG.StochComposite.eq_2_47accelerated-gradientnonconvex-optimizationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be as in Lemma 5 and run Algorithm 4 along any realization of the oracle samples. Then for every and every ,
This is where the possible nonconvexity of enters the analysis, through the constant only.
Formalization Note Pathwise. , and are given with the identities , , . Restated from mission 2 of this series (there along Algorithm 2) because drafts cannot import one another; only (2.2) is used, so it holds along Algorithm 4 as well.
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.47), p. 12 (outer ends of the chain), along Algorithm 4 on `Ψ = f + h`, for every
realization `ω`, every `k ≥ 1` and every `x ∈ ℝⁿ`. -/
theorem eq_2_47 {n : ℕ} (f h : E n → ℝ) (gf gh : E n → E n) (Lf Lh : ℝ)
(hf : IsBetaSmooth f gf Lf) (hh : IsBetaSmooth h gh Lh) (hhc : ConvexOn ℝ Set.univ h)
(Ψ : E n → ℝ) (gΨ : E n → E n) (LΨ : ℝ) (hΨ : Ψ = fun x => f x + h x)
(hgΨ : gΨ = fun x => gf x + gh x) (hLΨ : LΨ = Lf + Lh)
(P : E n → E n → ℝ → E n) {Ξ : Type*} (G : E n → Ξ → E n)
(α β lam : ℕ → ℝ) (m : ℕ → ℕ) (hstep : RSAGStepsizes α β lam m) (x0 : E n)
{Ω : Type*} (ξ : ℕ → Ω → Ξ) :
let xk : ℕ → Ω → E n := xSeq G P α β lam m x0 ξ
let xag : ℕ → Ω → E n := xagSeq G P α β lam m x0 ξ
let xmd : ℕ → Ω → E n := xmdSeq G P α β lam m x0 ξ
∀ ω : Ω, ∀ k, 1 ≤ k → ∀ x : E n,
Ψ (xmd k ω) - ((1 - α k) * Ψ (xag (k - 1) ω) + α k * Ψ x) ≤
inner ℝ (gΨ (xmd k ω)) (xmd k ω - α k • x - (1 - α k) • xag (k - 1) ω) +
Lf * α k / 2 * ‖xmd k ω - x‖ ^ 2 +
Lf * α k ^ 2 * (1 - α k) / 2 * ‖xag (k - 1) ω - xk (k - 1) ω‖ ^ 2 := by sorry
end NonconvexAG.StochComposite
Source
Ghadimi & Lan, Accelerated Gradient Methods for Nonconvex Nonlinear and Stochastic Programming, arXiv:1310.3787v1, p. 12, (2.47)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.