(2.5), p. 11 — phase-space representation of NAG-SC
ProvedHighResODE.NAGSC.eq_2_5accelerated-gradientnesterovp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1phase-space
Let , let and , and let be a run of NAG-SC (1.3): , , . With the velocity , for every ,
and the initial velocity is
This rewriting of NAG-SC as explicit position and velocity updates is what suggests the discrete Lyapunov function (2.6).
Formalization Note The two updates are stated for in place of (so for every ), avoiding natural-number subtraction. The page uses implicitly (it divides by ); it is an explicit hypothesis here, together with . No assumption on is needed: the identities are algebraic consequences of (1.3).
Preamble
import Mathlib import Definitions.Def_HighResODE_NAGSC_FunctionClass import Definitions.Def_HighResODE_NAGSC_Setting
Formal statement
namespace HighResODE.NAGSC
open scoped InnerProductSpace
/-- (2.5), p. 11: the phase-space representation of NAG-SC. With `v_k = (x_{k+1} − x_k)/√s`,
for every `k ≥ 1`: `x_k − x_{k−1} = √s v_{k−1}` and
`v_k − v_{k−1} = −(2√(μs)/(1 − √(μs))) v_k − √s(∇f(x_k) − ∇f(x_{k−1}))
− ((1 + √(μs))/(1 − √(μs))) √s∇f(x_k)`; the initial velocity is
`v₀ = −(2√s/(1 + √(μs)))∇f(x₀)`. Stated with `k + 1` in place of `k`. -/
theorem eq_2_5 {n : ℕ} (f : E n → ℝ) (μ s : ℝ) (x y : ℕ → E n)
(hrun : IsNAGSC f μ s x y) (hs : 0 < s) (hμs : μ * s < 1) :
(∀ k : ℕ, x (k + 1) - x k = Real.sqrt s • vel s x k ∧
vel s x (k + 1) - vel s x k =
-(2 * Real.sqrt (μ * s) / (1 - Real.sqrt (μ * s))) • vel s x (k + 1)
- Real.sqrt s • (gradient f (x (k + 1)) - gradient f (x k))
- ((1 + Real.sqrt (μ * s)) / (1 - Real.sqrt (μ * s))) •
(Real.sqrt s • gradient f (x (k + 1)))) ∧
vel s x 0 = -(2 * Real.sqrt s / (1 + Real.sqrt (μ * s))) • gradient f (x 0) := by sorry
end HighResODE.NAGSC
Source
Shi, Du, Jordan & Su, Understanding the Acceleration Phenomenon via High-Resolution Differential Equations, arXiv:1810.08907v3, p. 11, (2.5) and the initial velocity
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.