Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proof of Theorem 2.1, p. 7 — the RSG iterate xkx_kxk​ is Fk−1\mathcal F_{k-1}Fk−1​-measurable (a function of the history ξ[k−1]\xi_{[k-1]}ξ[k−1]​)

Proved
GhadimiLan.RSG.iterate_measurable

by SamenHossain · Oct 8, 2026 · Mathlib 0df444a (Lean v4.33.1)

infrastructuremeasurabilitynonconvex-optimizationsgdstochastic-approximation

Let G:Rn×Ξ→RnG:\mathbb R^n\times\Xi\to\mathbb R^nG:Rn×Ξ→Rn be a Borel stochastic oracle, let (Fk)k≥0(\mathcal F_k)_{k\ge0}(Fk​)k≥0​ be a filtration on the sample space, and let the noise variables ξk\xi_kξk​ be Fk\mathcal F_kFk​-measurable for every k≥1k\ge1k≥1. Let x1,x2,…x_1,x_2,\dotsx1​,x2​,… be an RSG run from the deterministic point x1x_1x1​, i.e.

xk+1=xk−γk G(xk,ξk),k≥1,x_{k+1}=x_k-\gamma_k\,G(x_k,\xi_k),\qquad k\ge1,xk+1​=xk​−γk​G(xk​,ξk​),k≥1,

pointwise on the sample space, with real stepsizes γk\gamma_kγk​. Then for every k≥1k\ge1k≥1 the iterate xkx_kxk​ is Fk−1\mathcal F_{k-1}Fk−1​-measurable:

xk is a measurable function with respect to Fk−1.x_k\ \text{is a measurable function with respect to}\ \mathcal F_{k-1}.xk​ is a measurable function with respect to Fk−1​.

This is the remark "the search point xkx_kxk​ is a function of the history ξ[k−1]\xi_{[k-1]}ξ[k−1]​ and hence is random" in the proof of Theorem 2.1. It is the measurability input for the conditional-expectation step (2.10), and it applies verbatim to the two-phase and zeroth-order variants of the method, which use the same recursion.

Formalization Note The run is the platform predicate IsRSGRun, which fixes x1x_1x1​ and the recursion for k≥1k\ge1k≥1 only; x0x_0x0​ and ξ0\xi_0ξ0​ are unconstrained. The statement is about the σ\sigmaσ-algebra Fk−1\mathcal F_{k-1}Fk−1​ of the filtration, written Measurable[ℱ (k - 1)]; for k=1k=1k=1 it says that the constant x1x_1x1​ is F0\mathcal F_0F0​-measurable. No probability measure is involved.

Preamble
import Mathlib
import Definitions.Def_ConvexOptAlg_SmoothGD_Defs
import Definitions.Def_GhadimiLan_RSG_Model
open MeasureTheory ProbabilityTheory
open scoped InnerProductSpace
Formal statement
namespace GhadimiLan.RSG

/-- Measurability of the RSG iterates (Ghadimi & Lan, arXiv:1309.5549v1, proof of Theorem 2.1,
p. 7: "the search point `x_k` is a function of the history `ξ_[k−1]`"): if the oracle `G` is
Borel and the noise `ξ_k` is `ℱ_k`-measurable for every `k ≥ 1`, then along an RSG run the
iterate `x_k` is `ℱ_{k-1}`-measurable for every `k ≥ 1` (`x_1 = x1` is constant, hence
`ℱ_0`-measurable). -/
theorem iterate_measurable {n : ℕ} {Ξ : Type*} [MeasurableSpace Ξ] (G : E n → Ξ → E n)
    (hG : Measurable (Function.uncurry G))
    {Ω : Type*} [MeasurableSpace Ω] (ℱ : Filtration ℕ ‹MeasurableSpace Ω›) (ξ : ℕ → Ω → Ξ)
    (hξ : ∀ k : ℕ, 1 ≤ k → Measurable[ℱ k] (ξ k))
    (γ : ℕ → ℝ) (x1 : E n) (x : ℕ → Ω → E n) (hx : IsRSGRun G γ x1 ξ x)
    (k : ℕ) (hk : 1 ≤ k) :
    Measurable[ℱ (k - 1)] (x k) := by sorry

end GhadimiLan.RSG
Source
Ghadimi & Lan, Stochastic first- and zeroth-order methods for nonconvex stochastic programming, arXiv:1309.5549v1, proof of Theorem 2.1, p. 7 ("Note that the search point x_k is a function of the history ξ_[k−1] of the generated random process and hence is random")

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