Theorem 10, p. 22 — for f ∈ S_µ,L the speed restarted ODE satisfies f(Xˢʳ(t)) − f⋆ ≤ (c₁L‖x₀ − x⋆‖²/2) e^{−c₂t√L}
ProvedNesterovODE.Restart.theorem_10There exist positive constants and , depending only on the condition number , with the following property. Let , let on with minimizer and , let , and let be the speed restarted trajectory from , the solution of (29). Then for every ,
Resetting the friction of the Nesterov ODE whenever the speed stops increasing yields linear convergence for strongly convex objectives without knowledge of , in contrast with the polynomial rates of the unrestarted ODE.
Formalization Note and are functions of the condition number, , chosen before the dimension, , , , and the trajectory; this is "only depend on the condition number ". The statement covers every curve satisfying the speed-restart predicate of the Setting definition; in particular it covers , where the trajectory stays at . The predicate does not assume that the restart times tend to infinity: that is a consequence of Lemma 25.
import Mathlib import Definitions.Def_NesterovODE_Restart_Setting
namespace NesterovODE.Restart
open scoped RealInnerProductSpace
/-- Theorem 10 (p. 22): there are positive constants `c₁, c₂` depending only on the condition
number `L/μ` (functions of `L/μ`, chosen before the dimension, `f`, `μ`, `L`, `x₀`) such that
every speed restarted trajectory satisfies
`f(Xˢʳ(t)) − f⋆ ≤ (c₁L‖x₀ − x⋆‖²/2) e^{−c₂ t √L}` for all `t ≥ 0`. -/
theorem theorem_10 :
∃ c₁ c₂ : ℝ → ℝ, (∀ κ : ℝ, 0 < c₁ κ ∧ 0 < c₂ κ) ∧
∀ (n : ℕ) (f : NesterovODE.WellPosed.E n → ℝ) (μ : ℝ) (L : NNReal),
0 < μ → μ ≤ L → NesterovODE.StrongCvx.InSMuL μ L f →
∀ (x₀ xstar : NesterovODE.WellPosed.E n), (∀ y, f xstar ≤ f y) →
∀ Xsr : ℝ → NesterovODE.WellPosed.E n, IsSpeedRestarted f x₀ Xsr →
∀ t : ℝ, 0 ≤ t →
f (Xsr t) - f xstar ≤
c₁ (L / μ) * L * ‖x₀ - xstar‖ ^ 2 / 2 *
Real.exp (-(c₂ (L / μ)) * t * Real.sqrt L) := by sorry
end NesterovODE.Restart
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.