Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Stochastic gradient model, moment assumptions, and numerical quantities

Definition
BCN_SG_Model

by Minghui · Sep 25, 2026 · Mathlib c5ea003 (Lean v4.30.0)

optimizationprobabilitystochastic-gradient

This definition bundle specifies the objective, stochastic process, moment assumptions, and numerical quantities. Its definitions establish none of the five target estimates.

Notation and probability model

Let d∈Nd\in\mathbb Nd∈N and F:Rd→RF:\mathbb R^d\to\mathbb RF:Rd→R have an actual gradient ∇F\nabla F∇F at every point, with ∥∇F(x)−∇F(y)∥≤L∥x−y∥\|\nabla F(x)-\nabla F(y)\|\le L\|x-y\|∥∇F(x)−∇F(y)∥≤L∥x−y∥ for all x,yx,yx,y, where L>0L>0L>0. On a probability space (Ω,A,P)(\Omega,\mathcal A,\mathbb P)(Ω,A,P), let (Fk)k≥0(\mathcal F_k)_{k\ge0}(Fk​)k≥0​ be an increasing family of sub-σ\sigmaσ-algebras of A\mathcal AA. The initial vector w0w_0w0​ is deterministic. The iterate wkw_kwk​ is strongly Fk\mathcal F_kFk​-measurable, and the sampled direction gkg_kgk​ is strongly Fk+1\mathcal F_{k+1}Fk+1​-measurable with E∥gk∥2<∞\mathbb E\|g_k\|^2<\inftyE∥gk​∥2<∞. For deterministic real step sizes αk>0\alpha_k>0αk​>0, the algorithm is

wk+1=wk−αkgkalmost surely.w_{k+1}=w_k-\alpha_k g_k\quad\text{almost surely}.wk+1​=wk​−αk​gk​almost surely.

An open set U⊆RdU\subseteq\mathbb R^dU⊆Rd contains every iterate almost surely, and a real number Finf⁡F_{\inf}Finf​ satisfies F(x)≥Finf⁡F(x)\ge F_{\inf}F(x)≥Finf​ for all x∈Ux\in Ux∈U. Put mk=E[gk∣Fk]m_k=\mathbb E[g_k\mid\mathcal F_k]mk​=E[gk​∣Fk​]. Fix real constants 0<μ≤μG0<\mu\le\mu_G0<μ≤μG​, M≥0M\ge0M≥0, MV≥0M_V\ge0MV​≥0, and MG=MV+μG2M_G=M_V+\mu_G^2MG​=MV​+μG2​. The source's first- and second-moment assumptions are, almost surely for every kkk,

∇F(wk)⊤mk≥μ∥∇F(wk)∥2,∥mk∥≤μG∥∇F(wk)∥,\nabla F(w_k)^\top m_k\ge\mu\|\nabla F(w_k)\|^2, \qquad\|m_k\|\le\mu_G\|\nabla F(w_k)\|,∇F(wk​)⊤mk​≥μ∥∇F(wk​)∥2,∥mk​∥≤μG​∥∇F(wk​)∥, E[∥gk∥2∣Fk]−∥mk∥2≤M+MV∥∇F(wk)∥2.\mathbb E[\|g_k\|^2\mid\mathcal F_k]-\|m_k\|^2 \le M+M_V\|\nabla F(w_k)\|^2.E[∥gk​∥2∣Fk​]−∥mk​∥2≤M+MV​∥∇F(wk​)∥2.

Write qk=∥∇F(wk)∥2q_k=\|\nabla F(w_k)\|^2qk​=∥∇F(wk​)∥2, AK=∑k=0K−1αkA_K=\sum_{k=0}^{K-1}\alpha_kAK​=∑k=0K−1​αk​, WK=E[∑k=0K−1αkqk]W_K=\mathbb E[\sum_{k=0}^{K-1}\alpha_k q_k]WK​=E[∑k=0K−1​αk​qk​], and GK=E[∑k=0K−1qk]G_K=\mathbb E[\sum_{k=0}^{K-1}q_k]GK​=E[∑k=0K−1​qk​]; empty sums are zero. Define F∗:=inf⁡x∈RdF(x)F_*:=\inf_{x\in\mathbb R^d}F(x)F∗​:=infx∈Rd​F(x) using the actual objective's range (Lean's real-valued sInf), and Δk=E[F(wk)−F∗]\Delta_k=\mathbb E[F(w_k)-F_*]Δk​=E[F(wk​)−F∗​] when stating the strongly convex targets. Those targets require d≥1d\ge1d≥1, positive strong-convexity modulus, and Finf⁡=F∗F_{\inf}=F_*Finf​=F∗​. The other targets permit d=0d=0d=0 and use the trajectory-region lower bound Finf⁡F_{\inf}Finf​, without assuming a global minimizer.

Formalization note: these are source assumptions with explicit filtration, measurability, and finite-second-moment conventions for genuine Bochner and conditional expectations. The deterministic initialization and square-integrable directions imply finite iterate second moments; objective and gradient moments must be justified from smoothness in the proofs. The model assumes no expected descent inequality, no gradient-gap inequality, and no convergence conclusion. Local index 000 is paper index 111 throughout. Full-history conditioning follows Algorithm 4.1, PDF p. 22, footnote 4; the model assumptions are Assumptions 4.1 and 4.3, PDF p. 23 and PDF p. 24, equations (4.6)–(4.9), in Section 4 of Bottou–Curtis–Nocedal, Optimization Methods for Large-Scale Machine Learning: https://arxiv.org/abs/1606.04838v3.

Definition code
import Mathlib.Analysis.Calculus.Gradient.Basic
import Mathlib.Analysis.Convex.Strong
import Mathlib.Analysis.InnerProductSpace.PiL2
import Mathlib.Analysis.Normed.Lp.MeasurableSpace
import Mathlib.MeasureTheory.Function.L2Space
import Mathlib.Probability.ConditionalExpectation
import Mathlib.Probability.Process.Filtration

/-!
Bottou, Curtis, Nocedal, arXiv:1606.04838v3, Section 4, PDF pp. 21–34.
Algorithm 4.1 and its conditional-process convention: PDF p. 22, footnote 4.
Assumptions 4.1/4.3: PDF pp. 23–24, equations (4.6)–(4.9).
The local index 0 is the paper's index 1. Finite second moments are explicit.
The model contains no descent inequality or convergence conclusion.
-/

noncomputable section

open MeasureTheory ProbabilityTheory Filter
open scoped BigOperators Topology InnerProductSpace

namespace BCN

abbrev Space (d : ℕ) := EuclideanSpace ℝ (Fin d)

structure Objective (d : ℕ) where
  F : Space d → ℝ
  L : ℝ
  L_pos : 0 < L
  hasGradient : ∀ x, HasGradientAt F (gradient F x) x
  smooth : ∀ x y, ‖gradient F x - gradient F y‖ ≤ L * ‖x - y‖

structure MomentConstants where
  μ : ℝ
  μG : ℝ
  M : ℝ
  MV : ℝ
  μ_pos : 0 < μ
  μ_le_μG : μ ≤ μG
  M_nonneg : 0 ≤ M
  MV_nonneg : 0 ≤ MV

def MomentConstants.MG (C : MomentConstants) : ℝ := C.MV + C.μG ^ 2

variable {d : ℕ} {Ω : Type*} [mΩ : MeasurableSpace Ω]

structure Run (P : Objective d) (C : MomentConstants)
    (prob : Measure Ω) [IsProbabilityMeasure prob] (α : ℕ → ℝ) where
  history : Filtration ℕ mΩ
  w : ℕ → Ω → Space d
  g : ℕ → Ω → Space d
  w0 : Space d
  initial : ∀ ω, w 0 ω = w0
  w_adapted : ∀ k, StronglyMeasurable[history k] (w k)
  g_adapted : ∀ k, StronglyMeasurable[history (k + 1)] (g k)
  g_squareIntegrable : ∀ k, MemLp (g k) 2 prob
  step_pos : ∀ k, 0 < α k
  update : ∀ k, w (k + 1) =ᵐ[prob] fun ω ↦ w k ω - α k • g k ω
  region : Set (Space d)
  region_open : IsOpen region
  in_region : ∀ k, ∀ᵐ ω ∂prob, w k ω ∈ region
  lower : ℝ
  lower_bound : ∀ x ∈ region, lower ≤ P.F x
  angle : ∀ k, ∀ᵐ ω ∂prob,
    C.μ * ‖gradient P.F (w k ω)‖ ^ 2 ≤
      ⟪gradient P.F (w k ω), prob[g k | history k] ω⟫_ℝ
  mean_norm : ∀ k, ∀ᵐ ω ∂prob,
    ‖prob[g k | history k] ω‖ ≤ C.μG * ‖gradient P.F (w k ω)‖
  variance : ∀ k, ∀ᵐ ω ∂prob,
    prob[(fun ω ↦ ‖g k ω‖ ^ 2) | history k] ω - ‖prob[g k | history k] ω‖ ^ 2 ≤
      C.M + C.MV * ‖gradient P.F (w k ω)‖ ^ 2

variable {P : Objective d} {C : MomentConstants} {prob : Measure Ω}
  [IsProbabilityMeasure prob] {α : ℕ → ℝ}

def loss (R : Run P C prob α) (k : ℕ) (ω : Ω) : ℝ := P.F (R.w k ω)

def gradSq (R : Run P C prob α) (k : ℕ) (ω : Ω) : ℝ :=
  ‖gradient P.F (R.w k ω)‖ ^ 2

def expectedGradSq (R : Run P C prob α) (k : ℕ) : ℝ :=
  ∫ ω, gradSq R k ω ∂prob

def optimalValue (P : Objective d) : ℝ := sInf (Set.range P.F)

def expectedGap (R : Run P C prob α) (k : ℕ) : ℝ :=
  ∫ ω, P.F (R.w k ω) - optimalValue P ∂prob

def stepSum (α : ℕ → ℝ) (K : ℕ) : ℝ := ∑ k ∈ Finset.range K, α k

def weightedGradientSum (R : Run P C prob α) (K : ℕ) : ℝ :=
  ∫ ω, ∑ k ∈ Finset.range K, α k * gradSq R k ω ∂prob

def gradientSum (R : Run P C prob α) (K : ℕ) : ℝ :=
  ∫ ω, ∑ k ∈ Finset.range K, gradSq R k ω ∂prob

def fixedGapBound (P : Objective d) (C : MomentConstants)
    (w0 : Space d) (a c : ℝ) (k : ℕ) : ℝ :=
  a * P.L * C.M / (2 * c * C.μ) + (1 - a * c * C.μ) ^ k *
    (P.F w0 - optimalValue P - a * P.L * C.M / (2 * c * C.μ))

def diminishingGapConstant (P : Objective d) (C : MomentConstants)
    (w0 : Space d) (c β γ : ℝ) : ℝ :=
  max (β ^ 2 * P.L * C.M / (2 * (β * c * C.μ - 1)))
    ((γ + 1) * (P.F w0 - optimalValue P))

end BCN
Source
Léon Bottou, Frank E. Curtis, Jorge Nocedal, Optimization Methods for Large-Scale Machine Learning, arXiv:1606.04838v3, https://arxiv.org/abs/1606.04838v3; Section 4, PDF p. 22, Algorithm 4.1 and footnote 4; PDF p. 23 and PDF p. 24, Assumptions 4.1 and 4.3, equations (4.6)–(4.9); PDF pp. 24–34, Lemma 4.4 and Theorems 4.6, 4.7, 4.8, and 4.10.
Read-back

What the Lean code literally says, in plain math · gpt-6

This bundle defines data structures and expressions; it does not assert that a run exists or prove an estimate. For every natural number ddd, its space is the Euclidean space E=R{0,…,d−1}E=\mathbb{R}^{\{0,\ldots,d-1\}}E=R{0,…,d−1}. An objective consists of f:E→Rf:E\to\mathbb{R}f:E→R, a real L>0L>0L>0, the existence of its designated gradient ∇f(x)\nabla f(x)∇f(x) at every xxx, and ∥∇f(x)−∇f(y)∥≤L∥x−y∥\|\nabla f(x)-\nabla f(y)\|\le L\|x-y\|∥∇f(x)−∇f(y)∥≤L∥x−y∥ for all x,yx,yx,y. Moment constants are real μ,μG,M,MV\mu,\mu_G,M,M_Vμ,μG​,M,MV​ with 0<μ≤μG0<\mu\le\mu_G0<μ≤μG​, M≥0M\ge0M≥0, and MV≥0M_V\ge0MV​≥0; the derived constant is MG=MV+μG2M_G=M_V+\mu_G^2MG​=MV​+μG2​. For any such objective and constants, any sample type Ω\OmegaΩ with a measurable-space structure, any probability measure P\mathbb{P}P, and any deterministic real sequence α:N→R\alpha:\mathbb{N}\to\mathbb{R}α:N→R, a run consists of an increasing filtration (Hk)(\mathcal{H}_k)(Hk​) of sub-σ\sigmaσ-algebras of the ambient measurable space, functions wk,gk:Ω→Ew_k,g_k:\Omega\to Ewk​,gk​:Ω→E, a vector winit∈Ew_{\mathrm{init}}\in Ewinit​∈E, an open set U⊆EU\subseteq EU⊆E, and a real bbb. It requires w0(ω)=winitw_0(\omega)=w_{\mathrm{init}}w0​(ω)=winit​ for every ω\omegaω and, for every natural kkk, strong Hk\mathcal{H}_kHk​-measurability of wkw_kwk​, strong Hk+1\mathcal{H}_{k+1}Hk+1​-measurability of gkg_kgk​, membership gk∈L2(P;E)g_k\in L^2(\mathbb{P};E)gk​∈L2(P;E), positivity αk>0\alpha_k>0αk​>0, the almost-sure update wk+1=wk−αkgkw_{k+1}=w_k-\alpha_k g_kwk+1​=wk​−αk​gk​, and almost-sure membership wk∈Uw_k\in Uwk​∈U. It requires b≤f(x)b\le f(x)b≤f(x) for every x∈Ux\in Ux∈U. With vk=∇f(wk)v_k=\nabla f(w_k)vk​=∇f(wk​), mk=E[gk∣Hk]m_k=\mathbb{E}[g_k\mid\mathcal{H}_k]mk​=E[gk​∣Hk​], and qk=E[∥gk∥2∣Hk]q_k=\mathbb{E}[\|g_k\|^2\mid\mathcal{H}_k]qk​=E[∥gk​∥2∣Hk​], it requires, for every kkk, the almost-sure inequalities μ∥vk∥2≤⟨vk,mk⟩\mu\|v_k\|^2\le\langle v_k,m_k\rangleμ∥vk​∥2≤⟨vk​,mk​⟩, ∥mk∥≤μG∥vk∥\|m_k\|\le\mu_G\|v_k\|∥mk​∥≤μG​∥vk​∥, and qk−∥mk∥2≤M+MV∥vk∥2q_k-\|m_k\|^2\le M+M_V\|v_k\|^2qk​−∥mk​∥2≤M+MV​∥vk​∥2. Almost-sure requirements are imposed separately at each index; the initial equality holds everywhere. The loss and squared-gradient functions are f(wk)f(w_k)f(wk​) and ∥vk∥2\|v_k\|^2∥vk​∥2, and the expected squared gradient is ∫Ω∥vk∥2 dP\int_\Omega\|v_k\|^2\,d\mathbb{P}∫Ω​∥vk​∥2dP. For every objective it defines f∗=inf⁡{f(x):x∈E}f_*=\inf\{f(x):x\in E\}f∗​=inf{f(x):x∈E} using the total real infimum; the expected gap is ∫Ω(f(wk)−f∗) dP\int_\Omega(f(w_k)-f_*)\,d\mathbb{P}∫Ω​(f(wk​)−f∗​)dP. For natural KKK, the step sum is AK=∑k=0K−1αkA_K=\sum_{k=0}^{K-1}\alpha_kAK​=∑k=0K−1​αk​, the weighted gradient sum is WK=∫Ω∑k=0K−1αk∥vk∥2 dPW_K=\int_\Omega\sum_{k=0}^{K-1}\alpha_k\|v_k\|^2\,d\mathbb{P}WK​=∫Ω​∑k=0K−1​αk​∥vk​∥2dP, and the gradient sum is GK=∫Ω∑k=0K−1∥vk∥2 dPG_K=\int_\Omega\sum_{k=0}^{K-1}\|v_k\|^2\,d\mathbb{P}GK​=∫Ω​∑k=0K−1​∥vk​∥2dP. For every objective, moment constants, vector z∈Ez\in Ez∈E, real a,ca,ca,c, and natural kkk, the fixed-gap expression is Bk=aLM2cμ+(1−acμ)k(f(z)−f∗−aLM2cμ)B_k=\frac{aLM}{2c\mu}+(1-ac\mu)^k\left(f(z)-f_*-\frac{aLM}{2c\mu}\right)Bk​=2cμaLM​+(1−acμ)k(f(z)−f∗​−2cμaLM​). For every such objective, constants, and vector zzz, and arbitrary real c,β,γc,\beta,\gammac,β,γ, the diminishing-gap constant is D=max⁡{β2LM2(βcμ−1),(γ+1)(f(z)−f∗)}D=\max\left\{\frac{\beta^2LM}{2(\beta c\mu-1)},(\gamma+1)(f(z)-f_*)\right\}D=max{2(βcμ−1)β2LM​,(γ+1)(f(z)−f∗​)}. These last two definitions impose no sign restrictions on their additional real arguments. Indices start at zero, and at K=0K=0K=0 all the finite sums and their integrals are zero. The dimension d=0d=0d=0 is allowed and gives a one-point vector space; M=0M=0M=0 and MV=0M_V=0MV​=0 are allowed, while μ,μG,L,MG\mu,\mu_G,L,M_Gμ,μG​,L,MG​ are positive. The range of fff is nonempty even when d=0d=0d=0; if it is unbounded below, its total real infimum is zero. An objective is not required to have a global lower bound or an attained minimum. The run's bound bbb applies only on UUU and need not equal f∗f_*f∗​. An empty region cannot contain w0w_0w0​ almost surely on a probability space; an empty sample type admits no probability measure; and a step sequence with a nonpositive entry admits no run. All expectations use the total Bochner integral, which is zero for a nonintegrable integrand; conditional expectations use their total mathematical-library definitions, including zero when the required integrability fails. There are no separate run fields requiring integrability of the loss or squared gradient. Real division has x/0=0x/0=0x/0=0, and natural-number powers have zeroth power one, including 00=10^0=100=1.

Human review
  • Endorsed by Shuze Chen · Sep 26, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Minghui · Sep 26, 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