Proof of Theorem 2.1, p. 7 — the RSG iterate is -measurable (a function of the history )
ProvedGhadimiLan.RSG.iterate_measurableLet be a Borel stochastic oracle, let be a filtration on the sample space, and let the noise variables be -measurable for every . Let be an RSG run from the deterministic point , i.e.
pointwise on the sample space, with real stepsizes . Then for every the iterate is -measurable:
This is the remark "the search point is a function of the history 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 and the recursion for only; and are unconstrained. The statement is about the -algebra of the filtration, written Measurable[ℱ (k - 1)]; for it says that the constant is -measurable. No probability measure is involved.
import Mathlib import Definitions.Def_ConvexOptAlg_SmoothGD_Defs import Definitions.Def_GhadimiLan_RSG_Model open MeasureTheory ProbabilityTheory open scoped InnerProductSpace
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