(93), p. 22 — on a run of (91) + (73), ℒ̂_k − ℒ_k ≤ −α_kℒ̂_k + (α_k²/(2γ_k))‖∇f(y_k)‖²
ProvedNAGFlow.GradCorr.eq_93accelerated-gradientlyapunov-functionode-discretizationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a real Hilbert space, with , and let be a global minimiser of . Let satisfy (73) with and step sizes , and let be a run of the corrected scheme (91) for some constant . With (74) and
for every ,
This is (82) of Lemma 5.1 for the first two lines of (91), which form a Gauss–Seidel step (80) with in place of . It is the first step of the proof of Theorem 5.2.
Formalization Note. Only the first two lines of (91) and (73) are used; the correction step and the value of play no role, and only is assumed. No step-size rule is assumed. is the norm of (Riesz).
Preamble
import Mathlib import Definitions.Def_NAGFlow_GradCorr_Setting
Formal statement
namespace NAGFlow.GradCorr
/-- Inequality (93) in the proof of Theorem 5.2 (Luo & Chen, arXiv:1909.03145v4, p. 22). Let
`f ∈ S¹_μ`, `x*` a global minimiser of `f`, and `(x, y, v)` a run of the corrected scheme (91) with
parameters `(α, γ)` from (73) (`γ₀ > 0`, any step sizes `α_k > 0`). With
`ℒ̂_k = f(y_k) − f(x*) + (γ_{k+1}/2)‖v_{k+1} − x*‖²` (84), for every `k`
`ℒ̂_k − ℒ_k ≤ −α_kℒ̂_k + (α_k²/(2γ_k))‖∇f(y_k)‖²`. -/
theorem eq_93 {V : Type*} [NormedAddCommGroup V] [InnerProductSpace ℝ V] [CompleteSpace V]
(f : V → ℝ) (gradf : V → V) (μ L : ℝ) (hf : NAGFlow.PredCorr.IsS1 f gradf μ)
(xstar : V) (hxstar : ∀ y, f xstar ≤ f y)
(α γ : ℕ → ℝ) (hγ : NAGFlow.PredCorr.IsGammaRun μ α γ)
(x y v : ℕ → V) (hrun : IsGCRun gradf μ L α γ x y v) (k : ℕ) :
NAGFlow.PredCorr.lyapHat f xstar y v γ k - NAGFlow.PredCorr.lyap f xstar x v γ k ≤
-α k * NAGFlow.PredCorr.lyapHat f xstar y v γ k + α k ^ 2 / (2 * γ k) * ‖gradf (y k)‖ ^ 2 := by sorry
end NAGFlow.GradCorr
Source
Luo & Chen, arXiv:1909.03145v4, proof of Theorem 5.2, Eq. (93), p. 22; (84) p. 20
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.