Proposition 3, p. 635 — stochastic gradient method with zero-mean noise: a.s. f(x_t) → −∞, or f(x_t) converges and ∇f(x_t) → 0
ProvedGradErrors.Stochastic.proposition_3Let be continuously differentiable with an -Lipschitz gradient, for all . Let be a probability space with an increasing sequence of -fields . Let , , be random vectors in and a deterministic positive stepsize, generated by the method
where is a descent direction and a random noise term. Assume:
- (a) and are -measurable;
- (b) there are positive scalars such that for all
- (c) for all , with probability 1,
where is a positive deterministic constant; 4. (d) and .
Then, with probability 1, either , or else converges to a finite value and . Furthermore, with probability 1, every limit point of is a stationary point of .
This is the stochastic counterpart of the paper's Proposition 1. It covers stochastic gradient descent and its variants for nonconvex objectives without assuming that is bounded below or that the iterates stay bounded, and with a noise variance allowed to grow quadratically in .
Formalization Note is EuclideanSpace ℝ (Fin n), is gradient f, and is L : ℝ≥0. The recursion and the conditions (b) hold on every sample path, as on the page. The conditional expectations in (c) are encoded through set integrals rather than Mathlib's condExp: Mathlib's conditional expectation of a non-integrable function is , and the page assumes no integrability of (the bound need not be integrable). The encoding is: for every -measurable set , as -valued integrals, and whenever . These are exactly the generalized conditional-expectation statements and a.s. No measurability of is assumed; it follows from the recursion. is divergence of the partial sums to , and is Summable. "Limit point" is MapClusterPt. The almost-sure quantifier is outside the dichotomy: different sample paths may take different branches.
import Mathlib open Filter Topology NNReal ENNReal MeasureTheory ProbabilityTheory InnerProductSpace
namespace GradErrors.Stochastic
theorem proposition_3 {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)) :
∀ᵐ ω ∂P,
(Tendsto (fun t => f (x t ω)) atTop atBot ∨
((∃ l : ℝ, Tendsto (fun t => f (x t ω)) atTop (𝓝 l)) ∧
Tendsto (fun t => gradient f (x t ω)) atTop (𝓝 0))) ∧
∀ xbar, MapClusterPt xbar atTop (fun t => x t ω) → gradient f xbar = 0 := by sorry
end GradErrors.Stochastic
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.