Lemma 16, p. 29 — gradient variation along a smoothed solution
ProvedNesterovODE.WellPosed.lemma_16convex-optimizationnesterov-odep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1singular-ode
Let , let solve the smoothed equation (31) from , and let . Write . Then
This controls the change in the gradient through the initial velocity growth.
Formalization Note The statement uses any upper bound on every quotient for , and concludes the same inequality with . This pointwise form represents the supremum without a default value on an unbounded set.
Preamble
import Mathlib import Definitions.Def_NesterovODE_WellPosed_Setting
Formal statement
namespace NesterovODE.WellPosed
/-- Lemma 16, p. 29: gradient variation along a smoothed trajectory. -/
theorem lemma_16 {n : ℕ} (f : E n → ℝ) (L : NNReal) (x₀ : E n)
(δ : ℝ) (X V : ℝ → E n) (u B : ℝ)
(hf : IsFL f L) (hX : IsSmoothedSolution f δ x₀ X V)
(hu : 0 < u) (hB : ∀ v : ℝ, 0 < v → v ≤ u → ‖V v‖ / v ≤ B) :
‖gradient f (X u) - gradient f x₀‖ ≤
(1 / 2 : ℝ) * (L : ℝ) * B * u ^ 2 := by sorry
end NesterovODE.WellPosed
Source
Su, Boyd, Candès, A Differential Equation for Modeling Nesterov's Accelerated Gradient Method, arXiv:1503.01243v2, p. 29, Lemma 16
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.