App. B.8.2, p. 48 — centered table: ‖y⁰ − f′(x*)‖² ≤ 8nL(g(x⁰) − g(x*))
ProvedSAGFiniteSum.Rate.centered_init_norm_boundp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1sagsmoothnessstochastic-average-gradient
Assume the standing assumptions of §3. Let be the centered initial table. Then
This bounds the table part of the Lyapunov function at the centered initialization.
Formalization Note The page's fourth line writes for ; the initial point is meant. suffices (no ). The inequality cited as "[Nesterov, 2004, Equations 2.17]" (Nesterov's (2.1.7)) is a consequence of convexity and -Lipschitz gradients, both standing assumptions.
Preamble
import Mathlib import Definitions.Def_SAGFiniteSum_Rate_Model open scoped RealInnerProductSpace
Formal statement
namespace SAGFiniteSum.Rate
/-- B.8.2, norm bound (arXiv:1309.2388v2, p. 48). Under the standing assumptions, the centered
table `y⁰ᵢ = f'ᵢ(x⁰) − g'(x⁰)` satisfies
`‖y⁰ − f'(x*)‖² = ∑ᵢ ‖y⁰ᵢ − f'ᵢ(x*)‖² ≤ 8nL(g(x⁰) − g(x*))`. -/
theorem centered_init_norm_bound {p n : ℕ} (f : Fin n → EuclideanSpace ℝ (Fin p) → ℝ)
(f' : Fin n → EuclideanSpace ℝ (Fin p) → EuclideanSpace ℝ (Fin p)) (L : ℝ)
(xstar : EuclideanSpace ℝ (Fin p)) (hA : SAGAssumptions f f' L xstar)
(x0 : EuclideanSpace ℝ (Fin p)) :
∑ i, ‖centeredTable f' x0 i - f' i xstar‖ ^ 2
≤ 8 * (n : ℝ) * L * (SAGA.Convex.fAvg f x0 - SAGA.Convex.fAvg f xstar) := by sorry
end SAGFiniteSum.Rate
Source
Schmidt, Le Roux & Bach, arXiv:1309.2388v2, App. B.8.2, display on p. 48
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.