Theorem 6, p. 24 — NAG-C: min_{0≤i≤k}‖∇f(xᵢ)‖² ≤ 8568‖x₀ − x⋆‖²/(s²(k + 1)³) and f(xₖ) − f(x⋆) ≤ 119‖x₀ − x⋆‖²/(s(k + 1)²)
ProvedHighResODE.NAGC.theorem_6accelerated-gradientgradient-normnesterovp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1smooth-convex
Let be convex with -Lipschitz gradient, , and let be a minimizer of . Let and let be the iterates of NAG-C,
Then for every
With the first bound is : NAG-C, without modification, minimizes the squared gradient norm at an inverse cubic rate, faster than the that follows from the function-value rate and -smoothness.
Formalization Note Both claims of the theorem are one conjunction. The minimum over is Finset.inf' over Finset.range (k + 1). The minimizer is a hypothesis: the paper presupposes its existence for a merely convex . The algorithm is a predicate on the two sequences, which determines them from ; the momentum is a real quotient.
Preamble
import Mathlib import Definitions.Def_HighResODE_NAGC_Setting
Formal statement
namespace HighResODE.NAGC
open scoped InnerProductSpace
/-- Theorem 6, p. 24. -/
theorem theorem_6 {n : ℕ} (f : HighResODE.NAGSC.E n → ℝ) (L s : ℝ) (hf : HighResODE.NAGSC.IsF1 f L) (xs : HighResODE.NAGSC.E n)
(hmin : ∀ z : HighResODE.NAGSC.E n, f xs ≤ f z) (hs : 0 < s) (hsL : s ≤ 1 / (3 * L))
(x y : ℕ → HighResODE.NAGSC.E n) (hrun : IsNAGC f s x y) :
(∀ k : ℕ, (Finset.range (k + 1)).inf' Finset.nonempty_range_add_one
(fun i => ‖gradient f (x i)‖ ^ 2)
≤ 8568 * ‖x 0 - xs‖ ^ 2 / (s ^ 2 * ((k : ℝ) + 1) ^ 3)) ∧
(∀ k : ℕ, f (x k) - f xs ≤ 119 * ‖x 0 - xs‖ ^ 2 / (s * ((k : ℝ) + 1) ^ 2)) := by sorry
end HighResODE.NAGC
Source
Shi, Du, Jordan & Su, Understanding the Acceleration Phenomenon via High-Resolution Differential Equations, arXiv:1810.08907v3, p. 24, Theorem 6
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.