Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Eq. (59) — for each x∗∈X∗x^*\in X^*x∗∈X∗, a.s. ∑k2αkm(F(xk)−F∗)<∞\sum_k\frac{2\alpha_k}{m}(F(x_k)-F^*)<\infty∑k​m2αk​​(F(xk​)−F∗)<∞ and ∥xk−x∗∥\|x_k-x^*\|∥xk​−x∗∥ converges

Proved
IncProx.Randomized.eq59

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

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

In the setting of the randomized incremental methods (42)–(44) (problem (5)–(6) with XXX nonempty closed convex and fi,hif_i,h_ifi​,hi​ convex; ωk\omega_kωk​ uniform on {1,…,m}\{1,\dots,m\}{1,…,m} and independent of the past history Fk\mathcal F_kFk​; Assumption 3(b) or 4(b) with constant ccc; positive stepsizes αk\alpha_kαk​), assume

∑k=0∞αk2<∞.\sum_{k=0}^\infty\alpha_k^2<\infty.k=0∑∞​αk2​<∞.

Then for each x∗∈X∗x^*\in X^*x∗∈X∗ there is a set Ωx∗\Omega_{x^*}Ωx∗​ of probability 1 such that for every sample path in Ωx∗\Omega_{x^*}Ωx∗​

∑k=0∞2αkm(F(xk)−F∗)<∞,\sum_{k=0}^\infty\frac{2\alpha_k}{m}\bigl(F(x_k)-F^*\bigr)<\infty,k=0∑∞​m2αk​​(F(xk​)−F∗)<∞,

and the sequence {∥xk−x∗∥}\{\|x_k-x^*\|\}{∥xk​−x∗∥} converges.

The probability-one set depends on x∗x^*x∗: the statement is "for each x∗x^*x∗, almost surely", not "almost surely, for all x∗x^*x∗". The proof of Proposition 9 passes from the first to the second through a countable dense subset of X∗X^*X∗.

Formalization Note F∗=F(x∗)F^*=F(x^*)F∗=F(x∗) is written as F(x∗)F(x^*)F(x∗). The series is stated as Summable of a real sequence; its terms are nonnegative from k=1k=1k=1 on (every xkx_kxk​ with k≥1k\ge1k≥1 lies in XXX), so this is the paper's ∑<∞\sum<\infty∑<∞. The hypotheses αk→0\alpha_k\to0αk​→0 and ∑αk=∞\sum\alpha_k=\infty∑αk​=∞ of Proposition 9 are not needed for (59) and are not assumed. Components are indexed 0,…,m−10,\dots,m-10,…,m−1.

Preamble
import Mathlib
import Definitions.Def_IncProx_Randomized_Basic
Formal statement
namespace IncProx.Randomized

open Filter Topology MeasureTheory

/-- Eq. (59) (proof of Proposition 9, p. 21): if Σ α_k² < ∞, then for each x* ∈ X*, with
probability 1, Σ_k (2α_k/m)(F(x_k) − F*) < ∞ and ‖x_k − x*‖ converges. -/
theorem eq59 {Ω : 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α2 : Summable fun k => α k ^ 2) (xs : Vec n) (hxs : xs ∈ P.Xstar) :
    ∀ᵐ s ∂μ, Summable (fun k => 2 * α k / m * (P.F (x k s) - P.F xs)) ∧
      ∃ L : ℝ, Tendsto (fun k => ‖x k s - xs‖) atTop (𝓝 L) := by sorry

end IncProx.Randomized
Source
Bertsekas, Incremental Proximal Methods for Large Scale Convex Optimization, LIDS-P-2847 (rev. March 2011), p. 21, §4.2, proof of Prop. 9, Eq. (59)
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