Proposition 7 — constant stepsize , randomized order: a.s. if , else ,
ProvedIncProx.Randomized.proposition7Let be generated by one of the randomized incremental methods (42)–(44) for problem (5)–(6) ( nonempty closed convex, convex), with the stepsize fixed at a positive constant , under Assumption 3 (for (42), (43)) or Assumption 4 (for (44)) with constant .
- If , then with probability 1
- If , then with probability 1
Compared with the cyclic order (Proposition 4(b)), the error bound is smaller by a factor of .
Formalization Note and the infimum are taken in the extended reals (EReal), so the case is represented exactly. The setting hypotheses are those of the definition file: is independent of the -algebra generated by the past history, the would-be step at is measurable with respect to it, the iterates are measurable, and is a fixed vector. Components are indexed .
import Mathlib import Definitions.Def_IncProx_Randomized_Basic
namespace IncProx.Randomized
open Filter Topology MeasureTheory
/-- Proposition 7 (p. 16): for the randomized methods (42)–(44) with constant stepsize α > 0,
(a) if F* = −∞ then with probability 1 inf_{k≥0} F(x_k) = F*;
(b) if F* > −∞ then with probability 1 inf_{k≥0} F(x_k) ≤ F* + αβmc²/2, with β = 5. -/
theorem proposition7 {Ω : Type*} [MeasurableSpace Ω] {n m : ℕ} [NeZero m]
(μ : Measure Ω) [IsProbabilityMeasure μ] (P : Problem n m) (hP : P.Standing) (A : Alg)
(α : ℝ) (hα : 0 < α) (ω : ℕ → Ω → Fin m) (x : ℕ → Ω → Vec n)
(zc gFc gHc xc : ℕ → Fin m → Ω → Vec n) (x₀ : Vec n) (c : ℝ)
(hR : RandHyp μ P A (fun _ => α) ω x zc gFc gHc xc x₀ c) :
(P.Fstar = ⊥ → ∀ᵐ s ∂μ, ⨅ k, ((P.F (x k s) : ℝ) : EReal) = P.Fstar) ∧
(P.Fstar ≠ ⊥ → ∀ᵐ s ∂μ,
⨅ k, ((P.F (x k s) : ℝ) : EReal) ≤ P.Fstar + ((α * 5 * m * c ^ 2 / 2 : ℝ) : EReal)) := by sorry
end IncProx.Randomized
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.