Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 4.2 — under µ-strong convexity, E[φ(x̄_T) − φ(x*)] ≤ µ‖x₀−x*‖²/(T+2)² + 16𝖫²/(µ(T+2))

Proved
StochModelWC.StrongCvx.theorem_4_2

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

convex-optimizationmodel-based-methodsp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1stochastic-optimizationstrong-convexity

Setting. Minimize φ=f+r\varphi=f+rφ=f+r over Rd\mathbb R^dRd, where r:Rd→R∪{∞}r:\mathbb R^d\to\mathbb R\cup\{\infty\}r:Rd→R∪{∞} is closed with nonempty domain DDD and fff is locally Lipschitz. Suppose Assumption B holds with τ=0\tau=0τ=0 and with the functions fx(⋅,ξ)+r(⋅)f_x(\cdot,\xi)+r(\cdot)fx​(⋅,ξ)+r(⋅) μ\muμ-strongly convex for some μ>0\mu>0μ>0 (η=−μ\eta=-\muη=−μ): stochastic models fx(⋅,ξ)f_x(\cdot,\xi)fx​(⋅,ξ), exact in expectation at the base point and lower-bounding fff in expectation, with a random Lipschitz constant L(ξ)L(\xi)L(ξ) satisfying EL(ξ)2≤L\sqrt{\mathbb E L(\xi)^2}\le\mathsf LEL(ξ)2​≤L. Run Algorithm 4.1 from x0∈Ux_0\in Ux0​∈U with βt=μ(t+1)/2\beta_t=\mu(t+1)/2βt​=μ(t+1)/2,

xt+1=argmin⁡x{r(x)+fxt(x,ξt)+μ(t+1)4∥x−xt∥2},t=0,…,T,x_{t+1}=\operatorname*{argmin}_{x}\Big\{r(x)+f_{x_t}(x,\xi_t)+\frac{\mu(t+1)}{4}\|x-x_t\|^2\Big\},\qquad t=0,\dots,T,xt+1​=xargmin​{r(x)+fxt​​(x,ξt​)+4μ(t+1)​∥x−xt​∥2},t=0,…,T,

on i.i.d. samples ξt∼P\xi_t\sim Pξt​∼P. Let x∗x^*x∗ be any minimizer of φ\varphiφ.

Conclusion. For every integer T>0T>0T>0, the function inside the expectation below is integrable and

E[φ(2(T+2)(T+3)−2∑t=1T+1(t+1) xt)−φ(x∗)]≤μ∥x0−x∗∥2(T+2)2+16L2μ(T+2).\mathbb E\Big[\varphi\Big(\frac{2}{(T+2)(T+3)-2}\sum_{t=1}^{T+1}(t+1)\,x_t\Big)-\varphi(x^*)\Big]\le\frac{\mu\|x_0-x^*\|^2}{(T+2)^2}+\frac{16\mathsf L^2}{\mu(T+2)}.E[φ((T+2)(T+3)−22​t=1∑T+1​(t+1)xt​)−φ(x∗)]≤(T+2)2μ∥x0​−x∗∥2​+μ(T+2)16L2​.

The weights 2(t+1)(T+2)(T+3)−2\frac{2(t+1)}{(T+2)(T+3)-2}(T+2)(T+3)−22(t+1)​, t=1,…,T+1t=1,\dots,T+1t=1,…,T+1, sum to one, so the averaged point lies in DDD.

The theorem gives the O(1/(μT))O(1/(\mu T))O(1/(μT)) function-gap rate for stochastic model-based minimization (stochastic proximal point, prox-linear and proximal subgradient methods) under strong convexity, extending the nonuniform averaging technique of Schmidt, Le Roux and Bach to the fully proximal setting.

Formalization Note The paper prints 8L28\mathsf L^28L2 in place of 16L216\mathsf L^216L2. Its proof sums the first display of the proof (p. 23), which comes from (4.8); the proof of (4.8) yields the constant 4L2/(βt(βt−η))4\mathsf L^2/(\beta_t(\beta_t-\eta))4L2/(βt​(βt​−η)), not the printed 2L2/(βt(βt−η))2\mathsf L^2/(\beta_t(\beta_t-\eta))2L2/(βt​(βt​−η)), and this doubles the L2\mathsf L^2L2 term of the final bound. The statement is what the proof establishes; whether the printed bound with 8L28\mathsf L^28L2 also holds was not settled. Expectations are integrals against P⊗(T+1)P^{\otimes(T+1)}P⊗(T+1); the minimizer x∗x^*x∗ is a point of DDD with φ(x∗)≤φ(y)\varphi(x^*)\le\varphi(y)φ(x∗)≤φ(y) for all y∈Dy\in Dy∈D. The paper's ρˉ\bar\rhoρˉ​ of Algorithm 4.1 does not affect the iterates: any ρˉ∈(−μ,μ/2)\bar\rho\in(-\mu,\mu/2)ρˉ​∈(−μ,μ/2) satisfies βt>ρˉ>τ+η=−μ\beta_t>\bar\rho>\tau+\eta=-\muβt​>ρˉ​>τ+η=−μ for every ttt. μ\muμ-strong convexity is encoded as (−μ)(-\mu)(−μ)-weak convexity, which in a Euclidean space is the same notion. The constant L\mathsf LL is L in Lean and L(ξ)L(\xi)L(ξ) is Lfun.

Preamble
import Mathlib
import Definitions.Def_StochModelWC_ModelBased_Basic
import Definitions.Def_StochModelWC_ModelBased_AssumptionB

open MeasureTheory Filter Topology
Formal statement
namespace StochModelWC.StrongCvx

/-- Theorem 4.2 (p. 23): in the strongly convex setting (`τ = 0`, `f_x(·, ξ) + r` `μ`-strongly convex for some
`μ > 0`, i.e. Assumption B with `η = -μ`), Algorithm 4.1 with `β_t = μ (t + 1) / 2`, run on `T + 1` i.i.d. samples
`ω = (ξ₀, …, ξ_T) ∼ P^{⊗(T+1)}`, satisfies, for every `T > 0` and any minimizer `x*` of `φ = f + r`,
`E[φ(x̄_T) − φ(x*)] ≤ μ‖x₀ − x*‖² / (T + 2)² + 16 L² / (μ (T + 2))`,
where `x̄_T = 2 / ((T + 2)(T + 3) − 2) · Σ_{t=1}^{T+1} (t + 1) x_t` (weights summing to one, so `x̄_T ∈ D`), and
`φ(x̄_T)` is integrable. The paper prints `8 L²`; its proof, run with the constant of (4.8) that the proof of
Lemma 4.2 (p. 21) establishes, yields `16 L²`. -/
theorem theorem_4_2 {d : ℕ} {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω) [IsProbabilityMeasure P]
    (U D : Set (EuclideanSpace ℝ (Fin d))) (f r : EuclideanSpace ℝ (Fin d) → ℝ)
    (model : EuclideanSpace ℝ (Fin d) → EuclideanSpace ℝ (Fin d) → Ω → ℝ)
    (L : ℝ) (Lfun : Ω → ℝ) (μ : ℝ) (hμ : 0 < μ)
    (hD : D.Nonempty) (hr : StochModelWC.ModelBased.IsClosedFn D r) (hf : LocallyLipschitz f)
    (hB : StochModelWC.ModelBased.AssumptionB P U D f r model 0 (-μ) L Lfun)
    (upd : ℕ → EuclideanSpace ℝ (Fin d) → Ω → EuclideanSpace ℝ (Fin d))
    (hupd : StochModelWC.ModelBased.IsAlg41Step P U D r model (fun t => μ * ((t : ℝ) + 1) / 2) upd)
    (x0 : EuclideanSpace ℝ (Fin d)) (hx0 : x0 ∈ U)
    (xstar : EuclideanSpace ℝ (Fin d)) (hxstar : xstar ∈ D)
    (hmin : ∀ y ∈ D, f xstar + r xstar ≤ f y + r y)
    (T : ℕ) (hT : 0 < T) :
    Integrable (fun ω : Fin (T + 1) → Ω =>
        f ((2 / (((T : ℝ) + 2) * ((T : ℝ) + 3) - 2)) •
            ∑ t ∈ Finset.Icc 1 (T + 1), ((t : ℝ) + 1) • StochModelWC.ModelBased.run upd x0 ω t)
          + r ((2 / (((T : ℝ) + 2) * ((T : ℝ) + 3) - 2)) •
            ∑ t ∈ Finset.Icc 1 (T + 1), ((t : ℝ) + 1) • StochModelWC.ModelBased.run upd x0 ω t))
      (Measure.pi fun _ : Fin (T + 1) => P) ∧
    ∫ ω, (f ((2 / (((T : ℝ) + 2) * ((T : ℝ) + 3) - 2)) •
              ∑ t ∈ Finset.Icc 1 (T + 1), ((t : ℝ) + 1) • StochModelWC.ModelBased.run upd x0 ω t)
            + r ((2 / (((T : ℝ) + 2) * ((T : ℝ) + 3) - 2)) •
              ∑ t ∈ Finset.Icc 1 (T + 1), ((t : ℝ) + 1) • StochModelWC.ModelBased.run upd x0 ω t)
            - (f xstar + r xstar)) ∂(Measure.pi fun _ : Fin (T + 1) => P) ≤
      μ * ‖x0 - xstar‖ ^ 2 / ((T : ℝ) + 2) ^ 2 + 16 * L ^ 2 / (μ * ((T : ℝ) + 2)) := by sorry

end StochModelWC.StrongCvx
Source
Davis–Drusvyatskiy, Stochastic Model-Based Minimization of Weakly Convex Functions, arXiv:1803.06523v3, p. 23, Theorem 4.2 and its proof, (4.19); p. 19, Algorithm 4.1
Human review
  • Endorsed by Shuze Chen · Oct 9, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 9, 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