Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 3, p. 635 — stochastic gradient method with zero-mean noise: a.s. f(x_t) → −∞, or f(x_t) converges and ∇f(x_t) → 0

Proved
GradErrors.Stochastic.proposition_3

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

almost-sure-convergencediminishing-stepsizenonconvex-optimizationp2o-batch-pfp1ap2o-gran-per-chapterp2o-plan-paperp2o-v1stochastic-gradient

Let f:Rn→Rf:\mathbb R^n\to\mathbb Rf:Rn→R be continuously differentiable with an LLL-Lipschitz gradient, ∥∇f(x)−∇f(xˉ)∥≤L∥x−xˉ∥\|\nabla f(x)-\nabla f(\bar x)\|\le L\|x-\bar x\|∥∇f(x)−∇f(xˉ)∥≤L∥x−xˉ∥ for all x,xˉx,\bar xx,xˉ. Let (Ω,F,P)(\Omega,\mathcal F,P)(Ω,F,P) be a probability space with an increasing sequence of σ\sigmaσ-fields F0⊆F1⊆⋯⊆F\mathcal F_0\subseteq\mathcal F_1\subseteq\cdots\subseteq\mathcal FF0​⊆F1​⊆⋯⊆F. Let xtx_txt​, sts_tst​, wtw_twt​ be random vectors in Rn\mathbb R^nRn and γt\gamma_tγt​ a deterministic positive stepsize, generated by the method

xt+1=xt+γt(st+wt),x_{t+1}=x_t+\gamma_t(s_t+w_t),xt+1​=xt​+γt​(st​+wt​),

where sts_tst​ is a descent direction and wtw_twt​ a random noise term. Assume:

  1. (a) xtx_txt​ and sts_tst​ are Ft\mathcal F_tFt​-measurable;
  2. (b) there are positive scalars c1,c2c_1,c_2c1​,c2​ such that for all ttt
c1∥∇f(xt)∥2≤−∇f(xt)′st,∥st∥≤c2(1+∥∇f(xt)∥);c_1\|\nabla f(x_t)\|^2\le-\nabla f(x_t)'s_t,\qquad\|s_t\|\le c_2\bigl(1+\|\nabla f(x_t)\|\bigr);c1​∥∇f(xt​)∥2≤−∇f(xt​)′st​,∥st​∥≤c2​(1+∥∇f(xt​)∥);
  1. (c) for all ttt, with probability 1,
E[wt∣Ft]=0,E[∥wt∥2∣Ft]≤A(1+∥∇f(xt)∥2),E[w_t\mid\mathcal F_t]=0,\qquad E\bigl[\|w_t\|^2\mid\mathcal F_t\bigr]\le A\bigl(1+\|\nabla f(x_t)\|^2\bigr),E[wt​∣Ft​]=0,E[∥wt​∥2∣Ft​]≤A(1+∥∇f(xt​)∥2),

where AAA is a positive deterministic constant; 4. (d) ∑t=0∞γt=∞\sum_{t=0}^\infty\gamma_t=\infty∑t=0∞​γt​=∞ and ∑t=0∞γt2<∞\sum_{t=0}^\infty\gamma_t^2<\infty∑t=0∞​γt2​<∞.

Then, with probability 1, either f(xt)→−∞f(x_t)\to-\inftyf(xt​)→−∞, or else f(xt)f(x_t)f(xt​) converges to a finite value and lim⁡t→∞∇f(xt)=0\lim_{t\to\infty}\nabla f(x_t)=0limt→∞​∇f(xt​)=0. Furthermore, with probability 1, every limit point of xtx_txt​ is a stationary point of fff.

This is the stochastic counterpart of the paper's Proposition 1. It covers stochastic gradient descent and its variants for nonconvex objectives without assuming that fff is bounded below or that the iterates stay bounded, and with a noise variance allowed to grow quadratically in ∥∇f(xt)∥\|\nabla f(x_t)\|∥∇f(xt​)∥.

Formalization Note Rn\mathbb R^nRn is EuclideanSpace ℝ (Fin n), ∇f\nabla f∇f is gradient f, and LLL is L : ℝ≥0. The recursion and the conditions (b) hold on every sample path, as on the page. The conditional expectations in (c) are encoded through set integrals rather than Mathlib's condExp: Mathlib's conditional expectation of a non-integrable function is 000, and the page assumes no integrability of wtw_twt​ (the bound A(1+∥∇f(xt)∥2)A(1+\|\nabla f(x_t)\|^2)A(1+∥∇f(xt​)∥2) need not be integrable). The encoding is: for every Ft\mathcal F_tFt​-measurable set SSS, ∫S∥wt∥2 dP≤∫SA(1+∥∇f(xt)∥2) dP\int_S\|w_t\|^2\,dP\le\int_S A(1+\|\nabla f(x_t)\|^2)\,dP∫S​∥wt​∥2dP≤∫S​A(1+∥∇f(xt​)∥2)dP as [0,∞][0,\infty][0,∞]-valued integrals, and ∫Swt dP=0\int_S w_t\,dP=0∫S​wt​dP=0 whenever ∫S∥wt∥ dP<∞\int_S\|w_t\|\,dP<\infty∫S​∥wt​∥dP<∞. These are exactly the generalized conditional-expectation statements E[∥wt∥2∣Ft]≤A(1+∥∇f(xt)∥2)E[\|w_t\|^2\mid\mathcal F_t]\le A(1+\|\nabla f(x_t)\|^2)E[∥wt​∥2∣Ft​]≤A(1+∥∇f(xt​)∥2) and E[wt∣Ft]=0E[w_t\mid\mathcal F_t]=0E[wt​∣Ft​]=0 a.s. No measurability of wtw_twt​ is assumed; it follows from the recursion. ∑γt=∞\sum\gamma_t=\infty∑γt​=∞ is divergence of the partial sums to +∞+\infty+∞, and ∑γt2<∞\sum\gamma_t^2<\infty∑γt2​<∞ is Summable. "Limit point" is MapClusterPt. The almost-sure quantifier is outside the dichotomy: different sample paths may take different branches.

Preamble
import Mathlib

open Filter Topology NNReal ENNReal MeasureTheory ProbabilityTheory InnerProductSpace
Formal statement
namespace GradErrors.Stochastic

theorem proposition_3 {n : ℕ} {Ω : Type*} {m0 : MeasurableSpace Ω} (P : Measure Ω)
    [IsProbabilityMeasure P] (ℱ : Filtration ℕ m0)
    (f : EuclideanSpace ℝ (Fin n) → ℝ) (hf : ContDiff ℝ 1 f)
    (L : ℝ≥0) (hL : LipschitzWith L (gradient f))
    (x s w : ℕ → Ω → EuclideanSpace ℝ (Fin n)) (γ : ℕ → ℝ) (hγ : ∀ t, 0 < γ t)
    (hx : ∀ t ω, x (t + 1) ω = x t ω + γ t • (s t ω + w t ω))
    (hxm : ∀ t, StronglyMeasurable[ℱ t] (x t)) (hsm : ∀ t, StronglyMeasurable[ℱ t] (s t))
    (c₁ c₂ : ℝ) (hc₁ : 0 < c₁) (hc₂ : 0 < c₂)
    (h41a : ∀ t ω, c₁ * ‖gradient f (x t ω)‖ ^ 2 ≤ -⟪gradient f (x t ω), s t ω⟫_ℝ)
    (h41b : ∀ t ω, ‖s t ω‖ ≤ c₂ * (1 + ‖gradient f (x t ω)‖))
    (A : ℝ) (hA : 0 < A)
    (h42 : ∀ t (S : Set Ω), MeasurableSet[ℱ t] S → ∫⁻ ω in S, ‖w t ω‖ₑ ∂P < ∞ →
      ∫ ω in S, w t ω ∂P = 0)
    (h43 : ∀ t (S : Set Ω), MeasurableSet[ℱ t] S →
      ∫⁻ ω in S, ‖w t ω‖ₑ ^ 2 ∂P ≤
        ∫⁻ ω in S, ENNReal.ofReal (A * (1 + ‖gradient f (x t ω)‖ ^ 2)) ∂P)
    (hsum : Tendsto (fun T => ∑ t ∈ Finset.range T, γ t) atTop atTop)
    (hsq : Summable (fun t => γ t ^ 2)) :
    ∀ᵐ ω ∂P,
      (Tendsto (fun t => f (x t ω)) atTop atBot ∨
        ((∃ l : ℝ, Tendsto (fun t => f (x t ω)) atTop (𝓝 l)) ∧
          Tendsto (fun t => gradient f (x t ω)) atTop (𝓝 0))) ∧
      ∀ xbar, MapClusterPt xbar atTop (fun t => x t ω) → gradient f xbar = 0 := by sorry

end GradErrors.Stochastic
Source
Bertsekas and Tsitsiklis, Gradient Convergence in Gradient Methods with Errors, SIAM J. Optim. 10 (2000), https://doi.org/10.1137/S1052623497331063, p. 635, Proposition 3, displays (4.1)–(4.3), with Remark (b) ("with probability 1") and the standing assumption (2.1), p. 629
Human review
  • Endorsed by Shuze Chen · Oct 4, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 4, 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