Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 9 — randomized order, αk→0\alpha_k\to0αk​→0, ∑αk=∞\sum\alpha_k=\infty∑αk​=∞: a.s. lim inf⁡F(xk)=F∗\liminf F(x_k)=F^*liminfF(xk​)=F∗; with X∗≠∅X^*\neq\emptysetX∗=∅, ∑αk2<∞\sum\alpha_k^2<\infty∑αk2​<∞: a.s. xk→x∗∈X∗x_k\to x^*\in X^*xk​→x∗∈X∗

Proved
IncProx.Randomized.proposition9

by mikedeng1 · Oct 8, 2026 · Mathlib 0df444a (Lean v4.33.1)

convex-optimizationincremental-methodsp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1proximal-methodsstochastic-optimization

Consider the problem

minimize F(x)=∑i=1m(fi(x)+hi(x))subject to x∈X,\text{minimize } F(x)=\sum_{i=1}^m\bigl(f_i(x)+h_i(x)\bigr)\quad\text{subject to } x\in X,minimize F(x)=i=1∑m​(fi​(x)+hi​(x))subject to x∈X,

where X⊆RnX\subseteq\mathbb R^nX⊆Rn is nonempty, closed and convex and fi,hi:Rn→Rf_i,h_i:\mathbb R^n\to\mathbb Rfi​,hi​:Rn→R are convex, with optimal value F∗=inf⁡x∈XF(x)∈[−∞,∞)F^*=\inf_{x\in X}F(x)\in[-\infty,\infty)F∗=infx∈X​F(x)∈[−∞,∞) and optimal set X∗X^*X∗. Let {xk}\{x_k\}{xk​} be generated by one of the randomized incremental subgradient-proximal methods (42)–(44): at iteration kkk a component ωk\omega_kωk​ is drawn uniformly from {1,…,m}\{1,\dots,m\}{1,…,m}, independently of the past history Fk={xk,zk−1,…,z0,x0}\mathcal F_k=\{x_k,z_{k-1},\dots,z_0,x_0\}Fk​={xk​,zk−1​,…,z0​,x0​}, and a proximal step on fωkf_{\omega_k}fωk​​ and a projected subgradient step on hωkh_{\omega_k}hωk​​ are taken with stepsize αk>0\alpha_k>0αk​>0. Assume Assumption 3(b) (for (42), (43)) or Assumption 4(b) (for (44)) with constant ccc, and let the stepsize satisfy

lim⁡k→∞αk=0,∑k=0∞αk=∞.\lim_{k\to\infty}\alpha_k=0,\qquad\sum_{k=0}^\infty\alpha_k=\infty.k→∞lim​αk​=0,k=0∑∞​αk​=∞.

Then:

  1. with probability 1,
lim inf⁡k→∞F(xk)=F∗;\liminf_{k\to\infty}F(x_k)=F^*;k→∞liminf​F(xk​)=F∗;
  1. if furthermore X∗X^*X∗ is nonempty and ∑k=0∞αk2<∞\sum_{k=0}^\infty\alpha_k^2<\infty∑k=0∞​αk2​<∞, then with probability 1 the sequence {xk}\{x_k\}{xk​} converges to some x∗∈X∗x^*\in X^*x∗∈X∗.

The limit x∗x^*x∗ 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 F∗F^*F∗ and the lim inf⁡\liminfliminf are taken in the extended reals (EReal), so part 1 includes the case F∗=−∞F^*=-\inftyF∗=−∞. ∑αk=∞\sum\alpha_k=\infty∑αk​=∞ is stated as divergence of the partial sums to +∞+\infty+∞. Part 2 is "almost surely, there exists x∗∈X∗x^*\in X^*x∗∈X∗ with xk→x∗x_k\to x^*xk​→x∗". The paper's phrase "independent of the past history" is formalized as independence of σ(ωk)\sigma(\omega_k)σ(ωk​) from the σ\sigmaσ-algebra generated by x0,…,xk,z0,…,zk−1x_0,\dots,x_k,z_0,\dots,z_{k-1}x0​,…,xk​,z0​,…,zk−1​, together with the hypotheses that make it meaningful: the iterates are measurable, the step iteration kkk would take for each component is measurable with respect to that σ\sigmaσ-algebra, and x0x_0x0​ is a fixed vector. The bounds (45)–(48) are required for every component iii, not only the sampled one, as in the paper. Rn\mathbb R^nRn is EuclideanSpace ℝ (Fin n), components are indexed 0,…,m−10,\dots,m-10,…,m−1, and m≥1m\ge1m≥1.

Preamble
import Mathlib
import Definitions.Def_IncProx_Randomized_Basic
Formal statement
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
Source
Bertsekas, Incremental Proximal Methods for Large Scale Convex Optimization, LIDS-P-2847 (rev. March 2011), p. 20, Proposition 9
Human review
  • Endorsed by Shuze Chen · Oct 8, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 8, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me