Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Eq. (58) — E{∥xk+1−x∗∥2∣Fk}≤∥xk−x∗∥2−2αkm(F(xk)−F∗)+5αk2c2E\{\|x_{k+1}-x^*\|^2\mid\mathcal F_k\}\le\|x_k-x^*\|^2-\frac{2\alpha_k}{m}(F(x_k)-F^*)+5\alpha_k^2c^2E{∥xk+1​−x∗∥2∣Fk​}≤∥xk​−x∗∥2−m2αk​​(F(xk​)−F∗)+5αk2​c2

Proved
IncProx.Randomized.eq58

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

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

Consider problem (5)–(6): X⊆RnX\subseteq\mathbb R^nX⊆Rn nonempty closed convex, fi,hi:Rn→Rf_i,h_i:\mathbb R^n\to\mathbb Rfi​,hi​:Rn→R convex, F=∑i=1m(fi+hi)F=\sum_{i=1}^m(f_i+h_i)F=∑i=1m​(fi​+hi​). Let xkx_kxk​ be generated by one of the randomized incremental methods (42), (43), (44) with positive stepsizes αk\alpha_kαk​ from a starting point x0∈Rnx_0\in\mathbb R^nx0​∈Rn, where the component ωk\omega_kωk​ used at iteration kkk is uniformly distributed over {1,…,m}\{1,\dots,m\}{1,…,m} and independent of the past history Fk={xk,zk−1,xk−1,…,z0,x0}\mathcal F_k=\{x_k,z_{k-1},x_{k-1},\dots,z_0,x_0\}Fk​={xk​,zk−1​,xk−1​,…,z0​,x0​} (Assumption 3(a)/4(a)), and let Assumption 3(b) (for (42), (43)) or Assumption 4(b) (for (44)) hold with the constant ccc.

Then for every optimal solution x∗∈X∗x^*\in X^*x∗∈X∗ and every k≥0k\ge0k≥0, almost surely,

E{∥xk+1−x∗∥2∣Fk}≤∥xk−x∗∥2−2αkm(F(xk)−F∗)+βαk2c2,β=5.E\{\|x_{k+1}-x^*\|^2\mid\mathcal F_k\}\le\|x_k-x^*\|^2-\frac{2\alpha_k}{m}\bigl(F(x_k)-F^*\bigr)+\beta\alpha_k^2c^2,\qquad\beta=5.E{∥xk+1​−x∗∥2∣Fk​}≤∥xk​−x∗∥2−m2αk​​(F(xk​)−F∗)+βαk2​c2,β=5.

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 α\alphaα replaced by αk\alpha_kαk​ and yyy by x∗x^*x∗. It is the input to the supermartingale convergence theorem (Proposition 2).

Formalization Note The statement is for all kkk, as in the paper, including k=0k=0k=0 with a starting point x0∉Xx_0\notin Xx0​∈/X. Since x∗∈X∗x^*\in X^*x∗∈X∗, F∗=F(x∗)F^*=F(x^*)F∗=F(x∗) is finite and is written as F(x∗)F(x^*)F(x∗). The conditional expectation is with respect to the σ\sigmaσ-algebra generated by x0,…,xkx_0,\dots,x_kx0​,…,xk​ and z0,…,zk−1z_0,\dots,z_{k-1}z0​,…,zk−1​. The setting hypotheses (the would-be step at kkk is Fk\mathcal F_kFk​-measurable, the iterates are measurable, x0x_0x0​ is a fixed vector) are those of the definition file; 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. (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
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. (58) (cf. Eq. (50), p. 17, β = 5)
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