Eq. (58) —
ProvedIncProx.Randomized.eq58Consider problem (5)–(6): nonempty closed convex, convex, . Let be generated by one of the randomized incremental methods (42), (43), (44) with positive stepsizes from a starting point , where the component used at iteration is uniformly distributed over and independent of the past history (Assumption 3(a)/4(a)), and let Assumption 3(b) (for (42), (43)) or Assumption 4(b) (for (44)) hold with the constant .
Then for every optimal solution and every , almost surely,
This is the conditional descent inequality (58) of the proof of Proposition 9, i.e. Eq. (50) of the proof of Proposition 7 with the constant stepsize replaced by and by . It is the input to the supermartingale convergence theorem (Proposition 2).
Formalization Note The statement is for all , as in the paper, including with a starting point . Since , is finite and is written as . The conditional expectation is with respect to the -algebra generated by and . The setting hypotheses (the would-be step at is -measurable, the iterates are measurable, is a fixed vector) are those of the definition file; components are indexed .
import Mathlib import Definitions.Def_IncProx_Randomized_Basic
namespace IncProx.Randomized
open Filter Topology MeasureTheory
/-- Eq. (58) (proof of Proposition 9, p. 21; cf. (50), p. 17, β = 5): for every optimal x* ∈ X*
and every k ≥ 0, E{‖x_{k+1} − x*‖² | F_k} ≤ ‖x_k − x*‖² − (2α_k/m)(F(x_k) − F*) + 5α_k²c². -/
theorem eq58 {Ω : 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)
(xs : Vec n) (hxs : xs ∈ P.Xstar) (k : ℕ) :
μ[fun s => ‖x (k + 1) s - xs‖ ^ 2 | hist x (zOf ω zc) k] ≤ᵐ[μ]
fun s => ‖x k s - xs‖ ^ 2 - 2 * α k / m * (P.F (x k s) - P.F xs) + 5 * α k ^ 2 * c ^ 2 := by sorry
end IncProx.Randomized
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.