§A.5 Step 2, p. 23 — with :
ProvedSAG.SmallStep.lyapunov_initlyapunov-functionp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let , , let be differentiable with gradients , and let be a minimizer of . Let be the Lyapunov function of §A.5 with and put . For the initial state with all ,
This evaluates the starting value of the Lyapunov function and produces the constant of Proposition 1.
Formalization Note The page's computation uses , which follows from minimizing ; the theorem assumes the minimality, not the gradient identity. (The page's intermediate display writes where the definition of gives ; that term vanishes at .)
Preamble
import Mathlib import Definitions.Def_SAGA_Convex_finiteSum import Definitions.Def_SAG_SmallStep_blockForm import Definitions.Def_SAG_SmallStep_lyapunov
Formal statement
namespace SAG.SmallStep
/-- §A.5 Step 2 (arXiv:1202.6258v4, p. 23): with `α = 1/(2nL)` and the table initialized to
`y⁰ = 0`, `Q(θ⁰) = 3σ²/(4L²) + ‖x⁰ − x*‖²`, where `σ² = (1/n) ∑ᵢ ‖f'ᵢ(x*)‖²` and `x*` minimizes
`g`. -/
theorem lyapunov_init {p n : ℕ} (hn : 0 < n)
(f : Fin n → EuclideanSpace ℝ (Fin p) → ℝ)
(f' : Fin n → EuclideanSpace ℝ (Fin p) → EuclideanSpace ℝ (Fin p)) (L : ℝ) (hL : 0 < L)
(hgrad : ∀ i x, HasGradientAt (f i) (f' i x) x)
(xstar : EuclideanSpace ℝ (Fin p))
(hmin : ∀ x, SAGA.Convex.fAvg f xstar ≤ SAGA.Convex.fAvg f x)
(x0 : EuclideanSpace ℝ (Fin p)) :
lyapunov f' (1 / (2 * (n : ℝ) * L)) xstar (fun _ => 0, x0)
= 3 * ((1 / (n : ℝ)) * ∑ i, ‖f' i xstar‖ ^ 2) / (4 * L ^ 2) + ‖x0 - xstar‖ ^ 2 := 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, p. 23, §A.5 Step 2, "Initializing all the y_i^0 to 0, we get"
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.