Proposition 9 — randomized order, , : a.s. ; with , : a.s.
ProvedIncProx.Randomized.proposition9Consider the problem
where is nonempty, closed and convex and are convex, with optimal value and optimal set . Let be generated by one of the randomized incremental subgradient-proximal methods (42)–(44): at iteration a component is drawn uniformly from , independently of the past history , and a proximal step on and a projected subgradient step on are taken with stepsize . Assume Assumption 3(b) (for (42), (43)) or Assumption 4(b) (for (44)) with constant , and let the stepsize satisfy
Then:
- with probability 1,
- if furthermore is nonempty and , then with probability 1 the sequence converges to some .
The limit in part 2 may depend on the sample path. This is the exact-convergence result for the randomized order, the counterpart of Proposition 6 for the cyclic order.
Formalization Note and the are taken in the extended reals (EReal), so part 1 includes the case . is stated as divergence of the partial sums to . Part 2 is "almost surely, there exists with ". The paper's phrase "independent of the past history" is formalized as independence of from the -algebra generated by , together with the hypotheses that make it meaningful: the iterates are measurable, the step iteration would take for each component is measurable with respect to that -algebra, and is a fixed vector. The bounds (45)–(48) are required for every component , not only the sampled one, as in the paper. is EuclideanSpace ℝ (Fin n), components are indexed , and .
import Mathlib import Definitions.Def_IncProx_Randomized_Basic
namespace IncProx.Randomized
open Filter Topology MeasureTheory
/-- Proposition 9 (p. 20): for the randomized methods (42)–(44) with α_k → 0 and Σ α_k = ∞, with
probability 1, liminf_k F(x_k) = F*. If moreover X* is nonempty and Σ α_k² < ∞, then with
probability 1 the sequence x_k converges to some x* ∈ X* (which may depend on the sample path). -/
theorem proposition9 {Ω : Type*} [MeasurableSpace Ω] {n m : ℕ} [NeZero m]
(μ : Measure Ω) [IsProbabilityMeasure μ] (P : Problem n m) (hP : P.Standing) (A : Alg)
(α : ℕ → ℝ) (hαpos : ∀ k, 0 < α k) (ω : ℕ → Ω → Fin m) (x : ℕ → Ω → Vec n)
(zc gFc gHc xc : ℕ → Fin m → Ω → Vec n) (x₀ : Vec n) (c : ℝ)
(hR : RandHyp μ P A α ω x zc gFc gHc xc x₀ c)
(hα0 : Tendsto α atTop (𝓝 0))
(hαsum : Tendsto (fun N => ∑ k ∈ Finset.range N, α k) atTop atTop) :
(∀ᵐ s ∂μ, liminf (fun k => ((P.F (x k s) : ℝ) : EReal)) atTop = P.Fstar) ∧
(P.Xstar.Nonempty → Summable (fun k => α k ^ 2) →
∀ᵐ s ∂μ, ∃ xs ∈ P.Xstar, Tendsto (fun k => x k s) atTop (𝓝 xs)) := by sorry
end IncProx.Randomized
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.