Theorem 2.1, (2.4), p. 4 — E‖x_k − x⋆‖² ≤ [1 − 2γµ(1 − γ sup L)]^k ‖x_0 − x⋆‖² + γσ²/(µ(1 − γ sup L)) for γ < 1/sup L
ProvedSGDKaczmarz.SGD.theorem_2_1Let be a probability distribution (the source distribution) on an arbitrary measurable index space , and let be a separable real Hilbert space. Let , , satisfy:
- each is convex and differentiable, and has Lipschitz constant , with almost surely;
- is finite for every , and is measurable for every ;
- is -strongly convex, : for all .
Let minimize and set . Let , let , and let be the SGD iterates (2.2), with drawn i.i.d. from . Then for every
where the expectation is with respect to the sampling of .
This is the main theorem of the paper: SGD with a fixed step converges linearly to a neighbourhood of whose radius is proportional to , with a rate governed by the uniform conditioning . Corollary 2.2 and the importance-sampling and Kaczmarz corollaries of Sections 3 and 5 are obtained from it.
Formalization Note The expectation of and are lower Lebesgue integrals in over the infinite product law of and over , so a non-integrable iterate cannot satisfy the bound vacuously; when the right side is , which is the paper's meaning. The condition is written (equivalent for , and the page's for ). The page defines as the essential supremum of and uses it only through " a.s."; the theorem is stated for every almost-sure upper bound, which is equivalent because the bound is increasing in . Integrability of , measurability of in and separability of are what make and the iterates' expectation meaningful. Assumption (2) is stated for Mathlib's gradient of .
Retired 2026-10-27: a Lean-vs-paper fidelity audit found this statement weaker than, or narrower than, the cited result. A corrected statement will be resubmitted.
import Mathlib import Definitions.Def_SGDKaczmarz_SGD_Setting open MeasureTheory open scoped NNReal ENNReal InnerProductSpace
namespace SGDKaczmarz.SGD
/-- Theorem 2.1, (2.4), p. 4 (Needell–Srebro–Ward, arXiv:1310.5715v5): for `γ < 1/sup L` the SGD
iterates (2.2) satisfy
`E‖x_k − x⋆‖² ≤ [1 − 2γμ(1 − γ sup L)]^k ‖x_0 − x⋆‖² + γσ²/(μ(1 − γ sup L))`, the expectation being
over the i.i.d. sampling of `{i_k}`. -/
theorem theorem_2_1 {I : Type*} [MeasurableSpace I] (D : Measure I) [IsProbabilityMeasure D]
{H : Type*} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H]
[MeasurableSpace H] [BorelSpace H] [SecondCountableTopology H]
(f : I → H → ℝ) (L : I → ℝ≥0)
(hdiff : ∀ i, Differentiable ℝ (f i))
(hlip : ∀ i, LipschitzWith (L i) (gradient (f i)))
(hconv : ∀ i, ConvexOn ℝ Set.univ (f i))
(supL : ℝ) (hsup : ∀ᵐ i ∂D, (L i : ℝ) ≤ supL)
(hint : ∀ x, Integrable (fun i => f i x) D)
(hmeas : ∀ x, Measurable (fun i => gradient (f i) x))
(μ : ℝ) (hμ : 0 < μ)
(hF : ∀ x y, μ * ‖x - y‖ ^ 2 ≤
⟪x - y, gradient (objective D f) x - gradient (objective D f) y⟫_ℝ)
(xstar : H) (hxstar : ∀ x, objective D f xstar ≤ objective D f x)
(γ : ℝ) (hγ : 0 < γ) (hγL : γ * supL < 1) (x0 : H) (k : ℕ) :
∫⁻ ω, ENNReal.ofReal (‖sgdIter f γ x0 k ω - xstar‖ ^ 2) ∂(iidLaw D)
≤ ENNReal.ofReal ((1 - 2 * γ * μ * (1 - γ * supL)) ^ k * ‖x0 - xstar‖ ^ 2)
+ ENNReal.ofReal (γ / (μ * (1 - γ * supL))) * residual D f xstar := by sorry
end SGDKaczmarz.SGD
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.