Proposition 8 — a.s., with
ProvedIncProx.Randomized.proposition8Let be generated as in Proposition 7 (one of the randomized methods (42)–(44), constant stepsize , Assumption 3 or 4 with constant ), assume that is nonempty, and let . Let
and let be the first iteration at which the run enters ( if it never does). Then is a random variable, with probability 1
and
The bound (55) is on the expected number of iterations needed to reach the error tolerance, to be compared with the deterministic count of Proposition 5 for the cyclic order.
Formalization Note The paper writes "where is a random variable with (55)"; an arbitrary would make the statement nearly empty ( satisfies (55) whenever (54) holds at ), so is the paper's own random variable from the proof of Proposition 8 (p. 19): the first index with , valued in . With probability 1 it is finite, and (54) is stated as the existence of with below the bound. Added hypothesis: the starting point lies in . The proof applies Eq. (50) at , which for (42) and (44) uses ; the paper does not state this. is Metric.infDist, is the extended-real optimal value (finite since ), and is the lower Lebesgue integral of in .
import Mathlib import Definitions.Def_IncProx_Randomized_Basic
namespace IncProx.Randomized
open Filter Topology MeasureTheory
/-- Proposition 8 (p. 19), for a run as in Proposition 7 started inside X: assume X* ≠ ∅ and
ε > 0, and let N be the first k with x_k in the level set
L = {x ∈ X | F(x) < F* + (αβmc² + ε)/2}, β = 5 (proof of Prop. 8, p. 19). Then N is a random
variable; with probability 1, N < ∞ and min_{0≤k≤N} F(x_k) ≤ F* + (αβmc² + ε)/2 (54); and
E{N} ≤ m dist(x₀; X*)²/(αε) (55). The hypothesis x₀ ∈ X is added. -/
theorem proposition8 {Ω : 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)
(hx₀ : x₀ ∈ P.X) (hXstar : P.Xstar.Nonempty) (ε : ℝ) (hε : 0 < ε) :
let L : Set (Vec n) :=
{y | y ∈ P.X ∧ ((P.F y : ℝ) : EReal) < P.Fstar + (((α * 5 * m * c ^ 2 + ε) / 2 : ℝ) : EReal)}
let N : Ω → ℕ∞ := firstHit x L
Measurable N ∧
(∀ᵐ s ∂μ, N s ≠ ⊤ ∧ ∃ k : ℕ, (k : ℕ∞) ≤ N s ∧
((P.F (x k s) : ℝ) : EReal) ≤ P.Fstar + (((α * 5 * m * c ^ 2 + ε) / 2 : ℝ) : EReal)) ∧
∫⁻ s, ENat.toENNReal (N s) ∂μ ≤
ENNReal.ofReal (m * Metric.infDist x₀ P.Xstar ^ 2 / (α * ε)) := by sorry
end IncProx.Randomized
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.