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)‖ ≤ δ
ProvedGradErrors.Stochastic.lemma_6Assume the setting of Proposition 3. Thus is continuously differentiable with an -Lipschitz gradient; is a probability space with a filtration ; are random vectors in and are deterministic stepsizes with
on every sample path; and
- and are -measurable;
- there are with and for all (on every sample path);
- for all , with probability 1, and , where is deterministic;
- and .
Let . Then for almost every sample path, converges to a finite value or to , and if then
Since is arbitrary, this lemma yields the gradient part of Proposition 3: on paths where does not diverge to , .
Formalization Note The conditional expectations in 3 are encoded through set integrals rather than Mathlib's condExp, which is for non-integrable functions and would make the hypotheses vacuous; the page assumes no integrability of . Precisely: for every -measurable set , (as -valued integrals), and whenever . These are exactly the generalized conditional-expectation statements of the page. "" is written as "for every , eventually ", because may be unbounded. Convergence to is Tendsto · atTop atBot. is divergence of the partial sums to . The Lipschitz constant is L : ℝ≥0.
import Mathlib open Filter Topology NNReal ENNReal MeasureTheory ProbabilityTheory InnerProductSpace
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.