Theorem 3, p. 16 — NAG-SC with s = 1/(4L): f(xₖ) − f(x⋆) ≤ 5L‖x₀ − x⋆‖²/(1 + √(μ/L)/12)ᵏ
ProvedHighResODE.NAGSC.theorem_3Theorem 3 (Convergence of NAG-SC). Let , that is, is differentiable and convex with an -Lipschitz gradient () and is -strongly convex with , and let be its minimizer. Run Nesterov's accelerated gradient method NAG-SC (1.3) with step size from an arbitrary :
Then, for all ,
The bound says , the optimal accelerated rate for first-order methods on smooth strongly convex functions; the paper obtains it from a single discrete Lyapunov function derived from the high-resolution ODE of NAG-SC.
Formalization Note is EuclideanSpace ℝ (Fin n) and is Mathlib's gradient f. The minimizer is a point xs with ∀ z, f xs ≤ f z. The NAG-SC run is the predicate IsNAGSC f μ (1 / (4 * L)) x y, which fixes both sequences from ; iterates are indexed from , and the bound is claimed for every , including . The step size is exactly , as in the theorem.
import Mathlib import Definitions.Def_HighResODE_NAGSC_FunctionClass import Definitions.Def_HighResODE_NAGSC_Setting
namespace HighResODE.NAGSC
open scoped InnerProductSpace
/-- Theorem 3 (Convergence of NAG-SC), p. 16: for `f ∈ S¹_{μ,L}(ℝⁿ)` and step size
`s = 1/(4L)`, the NAG-SC iterates satisfy
`f(x_k) − f(x⋆) ≤ 5L‖x₀ − x⋆‖² / (1 + (1/12)√(μ/L))^k` for all `k ≥ 0`. -/
theorem theorem_3 {n : ℕ} (f : E n → ℝ) (μ L : ℝ) (hf : IsS1 f μ L) (xs : E n)
(hmin : ∀ z : E n, f xs ≤ f z) (x y : ℕ → E n)
(hrun : IsNAGSC f μ (1 / (4 * L)) x y) :
∀ k : ℕ, f (x k) - f xs ≤
5 * L * ‖x 0 - xs‖ ^ 2 / (1 + 1 / 12 * Real.sqrt (μ / L)) ^ k := by sorry
end HighResODE.NAGSC
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.