§A.5 Step 2, pp. 22–23 —
ProvedSAG.SmallStep.lyapunov_dominateslyapunov-functionp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1quadratic-form
Let , let , and , and let be the Lyapunov function of §A.5 with step size . Then for every SAG state ,
Equivalently, is positive semidefinite.
This domination converts the linear convergence of into the convergence of in Proposition 1.
Formalization Note The page shows it for and writes "≻ 0 for " at the end of its Schur-complement computation; its exact expression is positive definite for every , and neither it nor the claim depends on the value of . The statement is therefore made for every and every . No hypothesis on or is needed.
Preamble
import Mathlib import Definitions.Def_SAG_SmallStep_blockForm import Definitions.Def_SAG_SmallStep_lyapunov
Formal statement
namespace SAG.SmallStep
/-- §A.5 Step 2 (arXiv:1202.6258v4, pp. 22–23): the Lyapunov function of §A.5 dominates
`⅓‖x − x*‖²`, `Q(θ) ≥ ⅓‖x − x*‖²` for every state `θ = (y, x)` and every step size `α > 0`. -/
theorem lyapunov_dominates {p n : ℕ} (hn : 0 < n)
(f' : Fin n → EuclideanSpace ℝ (Fin p) → EuclideanSpace ℝ (Fin p))
(xstar : EuclideanSpace ℝ (Fin p)) (α : ℝ) (hα : 0 < α)
(θ : (Fin n → EuclideanSpace ℝ (Fin p)) × EuclideanSpace ℝ (Fin p)) :
(1 / 3) * ‖θ.2 - xstar‖ ^ 2 ≤ lyapunov f' α xstar θ := by sorry
end SAG.SmallStep
Source
Le Roux, Schmidt & Bach, A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets, arXiv:1202.6258v4, pp. 22–23, §A.5 Step 2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.