Lemma 20, p. 31 — gradient difference for two local solutions
ProvedNesterovODE.WellPosed.lemma_20convex-optimizationnesterov-odep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1singular-ode
Suppose , and are two solutions of (3) with the same initial position and zero initial velocity on . Let . Then for ,
This controls the difference in the forcing terms near the initial time.
Formalization Note Any that bounds the velocity difference at every replaces the supremum in Lean. The local solution predicate includes the common initial data and the one-sided regularity at zero.
Preamble
import Mathlib import Definitions.Def_NesterovODE_WellPosed_Setting
Formal statement
namespace NesterovODE.WellPosed
/-- Lemma 20, p. 31: gradient variation between two local solutions. -/
theorem lemma_20 {n : ℕ} (f : E n → ℝ) (L : NNReal) (x₀ : E n)
(a t B : ℝ) (X V Y W : ℝ → E n)
(hf : IsFL f L) (hX : IsLocalSolution f x₀ a X V)
(hY : IsLocalSolution f x₀ a Y W)
(ht₀ : 0 < t) (hta : t < a)
(hB : ∀ u : ℝ, 0 ≤ u → u < t → ‖V u - W u‖ ≤ B) :
‖gradient f (X t) - gradient f (Y t)‖ ≤ (L : ℝ) * t * B := by sorry
end NesterovODE.WellPosed
Source
Su, Boyd, Candès, A Differential Equation for Modeling Nesterov's Accelerated Gradient Method, arXiv:1503.01243v2, p. 31, Lemma 20
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.