Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

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

Proved
SGDKaczmarz.SGD.theorem_2_1

by mikedeng1 · Oct 9, 2026 · Mathlib 0df444a (Lean v4.33.1)

linear-convergencep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1stochastic-gradient-descentstrong-convexity

Let D\mathcal DD be a probability distribution (the source distribution) on an arbitrary measurable index space III, and let H\mathcal HH be a separable real Hilbert space. Let fi:H→Rf_i : \mathcal H \to \mathbb Rfi​:H→R, i∈Ii \in Ii∈I, satisfy:

  1. each fif_ifi​ is convex and differentiable, and ∇fi\nabla f_i∇fi​ has Lipschitz constant LiL_iLi​, with Li≤sup⁡LL_i \le \sup LLi​≤supL almost surely;
  2. F(x)=Efi(x)F(x) = \mathbb E f_i(x)F(x)=Efi​(x) is finite for every xxx, and i↦∇fi(x)i \mapsto \nabla f_i(x)i↦∇fi​(x) is measurable for every xxx;
  3. FFF is μ\muμ-strongly convex, μ>0\mu > 0μ>0: ⟨x−y,∇F(x)−∇F(y)⟩≥μ∥x−y∥22\langle x - y, \nabla F(x) - \nabla F(y)\rangle \ge \mu\|x - y\|_2^2⟨x−y,∇F(x)−∇F(y)⟩≥μ∥x−y∥22​ for all x,yx, yx,y.

Let x⋆x_\starx⋆​ minimize FFF and set σ2=E∥∇fi(x⋆)∥22∈[0,∞]\sigma^2 = \mathbb E\|\nabla f_i(x_\star)\|_2^2 \in [0,\infty]σ2=E∥∇fi​(x⋆​)∥22​∈[0,∞]. Let 0<γ<1/sup⁡L0 < \gamma < 1/\sup L0<γ<1/supL, let x0∈Hx_0 \in \mathcal Hx0​∈H, and let xk+1=xk−γ∇fik(xk)x_{k+1} = x_k - \gamma\nabla f_{i_k}(x_k)xk+1​=xk​−γ∇fik​​(xk​) be the SGD iterates (2.2), with {ik}\{i_k\}{ik​} drawn i.i.d. from D\mathcal DD. Then for every k≥0k \ge 0k≥0

E∥xk−x⋆∥22≤[1−2γμ(1−γsup⁡L)]k∥x0−x⋆∥22+γσ2μ(1−γsup⁡L),\mathbb E\|x_k - x_\star\|_2^2 \le \Bigl[1 - 2\gamma\mu(1 - \gamma\sup L)\Bigr]^k\|x_0 - x_\star\|_2^2 + \frac{\gamma\sigma^2}{\mu(1 - \gamma\sup L)},E∥xk​−x⋆​∥22​≤[1−2γμ(1−γsupL)]k∥x0​−x⋆​∥22​+μ(1−γsupL)γσ2​,

where the expectation is with respect to the sampling of {ik}\{i_k\}{ik​}.

This is the main theorem of the paper: SGD with a fixed step converges linearly to a neighbourhood of x⋆x_\starx⋆​ whose radius is proportional to γσ2\gamma\sigma^2γσ2, with a rate governed by the uniform conditioning sup⁡L/μ\sup L/\musupL/μ. Corollary 2.2 and the importance-sampling and Kaczmarz corollaries of Sections 3 and 5 are obtained from it.

Formalization Note The expectation of ∥xk−x⋆∥2\|x_k - x_\star\|^2∥xk​−x⋆​∥2 and σ2\sigma^2σ2 are lower Lebesgue integrals in [0,∞][0,\infty][0,∞] over the infinite product law of {ik}\{i_k\}{ik​} and over D\mathcal DD, so a non-integrable iterate cannot satisfy the bound vacuously; when σ2=∞\sigma^2 = \inftyσ2=∞ the right side is ∞\infty∞, which is the paper's meaning. The condition γ<1/sup⁡L\gamma < 1/\sup Lγ<1/supL is written γ⋅sup⁡L<1\gamma\cdot\sup L < 1γ⋅supL<1 (equivalent for sup⁡L>0\sup L > 0supL>0, and the page's 1/0=∞1/0 = \infty1/0=∞ for sup⁡L=0\sup L = 0supL=0). The page defines sup⁡L\sup LsupL as the essential supremum of LiL_iLi​ and uses it only through "Li≤sup⁡LL_i \le \sup LLi​≤supL a.s."; the theorem is stated for every almost-sure upper bound, which is equivalent because the bound is increasing in sup⁡L\sup LsupL. Integrability of fi(x)f_i(x)fi​(x), measurability of ∇fi(x)\nabla f_i(x)∇fi​(x) in iii and separability of H\mathcal HH are what make FFF and the iterates' expectation meaningful. Assumption (2) is stated for Mathlib's gradient of FFF.


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.

Preamble
import Mathlib
import Definitions.Def_SGDKaczmarz_SGD_Setting

open MeasureTheory
open scoped NNReal ENNReal InnerProductSpace
Formal statement
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
Source
Needell, Srebro & Ward, Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm, arXiv:1310.5715v5, Theorem 2.1, (2.4), p. 4
Human review
  • Endorsed by Shuze Chen · Oct 9, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 9, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me