(18), p. 13 — derivative of the high-friction energy
ProvedNesterovODE.StrongCvx.eq_18convex-optimizationlyapunov-energynesterov-odep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let , let , and let minimize . For a solution of (17), the high-friction energy has, at every , derivative
This is the differential estimate used to obtain Theorem 5. The inequality follows from the stated convexity class.
Formalization Note The paper works in here. An explicit positive Lipschitz constant witnesses that membership. Solutions are quantified rather than selected by uniqueness.
Preamble
import Mathlib import Definitions.Def_NesterovODE_StrongCvx_Setting
Formal statement
namespace NesterovODE.StrongCvx
/-- Equation (18), including the exact energy derivative and its convexity bound. -/
theorem eq_18 (n : ℕ) (f : NesterovODE.WellPosed.E n → ℝ) (L : NNReal) (r : ℝ)
(x₀ xstar : NesterovODE.WellPosed.E n) (X V : ℝ → NesterovODE.WellPosed.E n)
(hL : 0 < L) (hf : InFL L f) (hr : 1 < r)
(hmin : ∀ y, f xstar ≤ f y)
(hX : IsSolution f r x₀ X V)
(t : ℝ) (ht : 0 < t) :
HasDerivAt (fun u => energy5 f r xstar X V u)
(4 * t / (r - 1) * (f (X t) - f xstar) -
2 * t * inner ℝ (X t - xstar) (gradient f (X t))) t ∧
4 * t / (r - 1) * (f (X t) - f xstar) -
2 * t * inner ℝ (X t - xstar) (gradient f (X t)) ≤
-(2 * (r - 3) * t / (r - 1)) * (f (X t) - f xstar) := by sorry
end NesterovODE.StrongCvx
Source
Su, Boyd, Candès, A Differential Equation for Modeling Nesterov's Accelerated Gradient Method, arXiv:1503.01243v2, p. 13, (18)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.