Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 6, p. 640 — a.s. f(x_t) converges to a finite value or to −∞, and if not −∞ then lim sup ‖∇f(x_t)‖ ≤ δ

Proved
GradErrors.Stochastic.lemma_6

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

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

Assume the setting of Proposition 3. Thus f:Rn→Rf:\mathbb R^n\to\mathbb Rf:Rn→R is continuously differentiable with an LLL-Lipschitz gradient; (Ω,F,P)(\Omega,\mathcal F,P)(Ω,F,P) is a probability space with a filtration (Ft)(\mathcal F_t)(Ft​); xt,st,wtx_t,s_t,w_txt​,st​,wt​ are random vectors in Rn\mathbb R^nRn and γt>0\gamma_t>0γt​>0 are deterministic stepsizes with

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

on every sample path; and

  1. xtx_txt​ and sts_tst​ are Ft\mathcal F_tFt​-measurable;
  2. there are c1,c2>0c_1,c_2>0c1​,c2​>0 with c1∥∇f(xt)∥2≤−∇f(xt)′stc_1\|\nabla f(x_t)\|^2\le-\nabla f(x_t)'s_tc1​∥∇f(xt​)∥2≤−∇f(xt​)′st​ and ∥st∥≤c2(1+∥∇f(xt)∥)\|s_t\|\le c_2(1+\|\nabla f(x_t)\|)∥st​∥≤c2​(1+∥∇f(xt​)∥) for all ttt (on every sample path);
  3. for all ttt, with probability 1, E[wt∣Ft]=0E[w_t\mid\mathcal F_t]=0E[wt​∣Ft​]=0 and 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), where A>0A>0A>0 is deterministic;
  4. ∑tγt=∞\sum_t\gamma_t=\infty∑t​γt​=∞ and ∑tγt2<∞\sum_t\gamma_t^2<\infty∑t​γt2​<∞.

Let δ>0\delta>0δ>0. Then for almost every sample path, f(xt)f(x_t)f(xt​) converges to a finite value or to −∞-\infty−∞, and if lim⁡t→∞f(xt)≠−∞\lim_{t\to\infty}f(x_t)\ne-\inftylimt→∞​f(xt​)=−∞ then

lim sup⁡t→∞∥∇f(xt)∥≤δ.\limsup_{t\to\infty}\|\nabla f(x_t)\|\le\delta .t→∞limsup​∥∇f(xt​)∥≤δ.

Since δ>0\delta>0δ>0 is arbitrary, this lemma yields the gradient part of Proposition 3: on paths where f(xt)f(x_t)f(xt​) does not diverge to −∞-\infty−∞, ∇f(xt)→0\nabla f(x_t)\to0∇f(xt​)→0.

Formalization Note The conditional expectations in 3 are encoded through set integrals rather than Mathlib's condExp, which is 000 for non-integrable functions and would make the hypotheses vacuous; the page assumes no integrability of wtw_twt​. Precisely: 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 of the page. "lim sup⁡≤δ\limsup\le\deltalimsup≤δ" is written as "for every δ′>δ\delta'>\deltaδ′>δ, eventually ∥∇f(xt)∥≤δ′\|\nabla f(x_t)\|\le\delta'∥∇f(xt​)∥≤δ′", because ∥∇f(xt)∥\|\nabla f(x_t)\|∥∇f(xt​)∥ may be unbounded. Convergence to −∞-\infty−∞ is Tendsto · atTop atBot. ∑tγt=∞\sum_t\gamma_t=\infty∑t​γt​=∞ is divergence of the partial sums to +∞+\infty+∞. The Lipschitz constant is L : ℝ≥0.

Preamble
import Mathlib

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

theorem lemma_6 {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))
    (δ : ℝ) (hδ : 0 < δ) :
    ∀ᵐ ω ∂P,
      (Tendsto (fun t => f (x t ω)) atTop atBot ∨
        ∃ l : ℝ, Tendsto (fun t => f (x t ω)) atTop (𝓝 l)) ∧
      (¬ Tendsto (fun t => f (x t ω)) atTop atBot →
        ∀ δ' > δ, ∀ᶠ t in atTop, ‖gradient f (x t ω)‖ ≤ δ') := 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. 640, Lemma 6 (in the setting of Proposition 3, p. 635; δ > 0 as fixed on p. 636)
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