(2.24) — (Ψ(x^ag_N) − Ψ(x))/Γ_N ≤ ‖x_0 − x‖²/(2λ_1) − Σ_{k≤N} (β_k/(2Γ_k))(1 − L_Ψβ_k)‖∇Ψ(x^md_k)‖²
ProvedNonconvexAG.Smooth.eq_2_24accelerated-gradientnonconvex-optimizationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be convex and differentiable with -Lipschitz gradient, , and let be generated by Algorithm 1 from with step sizes , (), , ; as in (2.6). Let , and suppose that for
Then for every ,
With this gives both conclusions (2.11) and (2.12) of Theorem 1 b).
Formalization Note The statement is the outer ends of the chain (2.24). Conditions (2.9) and (2.10) are imposed only on , the indices the proof uses.
Preamble
import Mathlib import Definitions.Def_ConvexOptAlg_SmoothGD_Defs import Definitions.Def_NonconvexAG_Smooth_AGRun
Formal statement
namespace NonconvexAG.Smooth
/-- (2.24), p. 7 (outer ends of the chain), for convex `Ψ`, under (2.9) and (2.10)
for `k = 1, …, N`, for every `x ∈ ℝⁿ`. -/
theorem eq_2_24 {n : ℕ} (Ψ : E n → ℝ) (g : E n → E n) (LΨ : ℝ)
(hΨ : ConvexOptAlg.SmoothGD.IsBetaSmooth Ψ g LΨ) (hL : 0 < LΨ)
(α β lam : ℕ → ℝ) (hstep : AGStepsizes α β lam) (x0 : E n) (hconv : ConvexOn ℝ Set.univ Ψ) (N : ℕ) (hN : 1 ≤ N)
(h29 : ∀ k ∈ Finset.Icc 1 N, α k * lam k ≤ β k ∧ β k < 1 / LΨ)
(h210 : ∀ k ∈ Finset.Icc 1 N, 2 ≤ k →
α k / (lam k * Gamma α k) ≤ α (k - 1) / (lam (k - 1) * Gamma α (k - 1))) :
∀ x : E n,
(Ψ (xagSeq g α β lam x0 N) - Ψ x) / Gamma α N ≤
‖x0 - x‖ ^ 2 / (2 * lam 1)
- ∑ k ∈ Finset.Icc 1 N, β k / (2 * Gamma α k) * (1 - LΨ * β k) * ‖g (xmdSeq g α β lam x0 k)‖ ^ 2 := by sorry
end NonconvexAG.Smooth
Source
Ghadimi & Lan, Accelerated Gradient Methods for Nonconvex Nonlinear and Stochastic Programming, arXiv:1310.3787v1, p. 7, (2.24)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.