Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

§6.2, proof of Theorem 6.3, p. 333 — E f(x_{s+1}) − f(x∗) ≤ (β + 1/η)E(D_Φ(x∗, x_s) − D_Φ(x∗, x_{s+1})) + ησ²/2

Proved
ConvexOptAlg.StochMD.thm_6_3_expected_step

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

convex-optimizationmirror-descentp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1stochastic-optimization

Let EEE be a finite-dimensional real normed space, X⊆E\mathcal X\subseteq EX⊆E compact and convex, Φ\PhiΦ a mirror map on D⊆E\mathcal D\subseteq ED⊆E with X⊆D‾\mathcal X\subseteq\overline{\mathcal D}X⊆D and X∩D≠∅\mathcal X\cap\mathcal D\ne\emptysetX∩D=∅, 111-strongly convex on X∩D\mathcal X\cap\mathcal DX∩D with respect to ∥⋅∥\|\cdot\|∥⋅∥. Let x1x_1x1​ minimize Φ\PhiΦ on X∩D\mathcal X\cap\mathcal DX∩D and let RRR satisfy Φ(x)−Φ(x1)≤R2\Phi(x)-\Phi(x_1)\le R^2Φ(x)−Φ(x1​)≤R2 for x∈X∩Dx\in\mathcal X\cap\mathcal Dx∈X∩D. Let fff be convex and β\betaβ-smooth on X\mathcal XX, β≥0\beta\ge0β≥0. On a probability space, let (xs,g~s)s≥1(x_s,\tilde g_s)_{s\ge1}(xs​,g~​s​)s≥1​ be an S-MD run started at x1x_1x1​ with step size 1/(β+1/η)1/(\beta+1/\eta)1/(β+1/η), η>0\eta>0η>0, driven by a stochastic oracle with E(g~s∣xs)=∇f(xs)\mathbb E(\tilde g_s\mid x_s)=\nabla f(x_s)E(g~​s​∣xs​)=∇f(xs​) and E(∥g~s−∇f(xs)∥∗2∣xs)≤σ2\mathbb E(\|\tilde g_s-\nabla f(x_s)\|_*^2\mid x_s)\le\sigma^2E(∥g~​s​−∇f(xs​)∥∗2​∣xs​)≤σ2. Then for every s≥1s\ge1s≥1 and every x∗∈Xx^*\in\mathcal Xx∗∈X, the random variables f(xs+1)f(x_{s+1})f(xs+1​) and DΦ(x∗,xs)−DΦ(x∗,xs+1)D_\Phi(x^*,x_s)-D_\Phi(x^*,x_{s+1})DΦ​(x∗,xs​)−DΦ​(x∗,xs+1​) are integrable and

Ef(xs+1)−f(x∗)≤(β+1η)E(DΦ(x∗,xs)−DΦ(x∗,xs+1))+ησ22.\mathbb E f(x_{s+1})-f(x^*)\le\Big(\beta+\frac1\eta\Big)\mathbb E\big(D_\Phi(x^*,x_s)-D_\Phi(x^*,x_{s+1})\big)+\frac{\eta\sigma^2}{2}.Ef(xs+1​)−f(x∗)≤(β+η1​)E(DΦ​(x∗,xs​)−DΦ​(x∗,xs+1​))+2ησ2​.

This is the expected one-step bound of the proof of Theorem 6.3; summing it from s=1s=1s=1 to ttt telescopes the Bregman terms and gives the theorem.

Formalization Note The expectation is the integral over the probability space; integrability of both random variables is part of the conclusion (a non-integrable function has integral 000 in Lean). The conditional expectations are given the σ-algebra generated by xsx_sxs​. The bound RRR (a hypothesis of Theorem 6.3) is assumed because it keeps the Bregman terms integrable. The book applies the bound to the minimizer x∗x^*x∗ of fff; it holds for every x∗∈Xx^*\in\mathcal Xx∗∈X. β≥0\beta\ge0β≥0 is the nonnegativity of a smoothness constant.

Preamble
import Mathlib
import Definitions.Def_ConvexOptAlg_StochMD_Defs
Formal statement
namespace ConvexOptAlg.StochMD

open MeasureTheory

/-- Bubeck, arXiv:1405.4980v2, proof of Theorem 6.3, printed p. 333, fourth display ("In
particular this yields …"): in the setting of Theorem 6.3, for a run of S-MD with step size
`1/(β + 1/η)` (any `η > 0`) driven by a stochastic oracle that is conditionally unbiased for `∇f`
with conditional variance at most `σ²`, for every `s ≥ 1` and every `x∗ ∈ X`, the random variables
`f(x_{s+1})` and `D_Φ(x∗, x_s) − D_Φ(x∗, x_{s+1})` are integrable and
`E f(x_{s+1}) − f(x∗) ≤ (β + 1/η) E(D_Φ(x∗, x_s) − D_Φ(x∗, x_{s+1})) + ησ²/2`. -/
theorem thm_6_3_expected_step {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E]
    [FiniteDimensional ℝ E] [MeasurableSpace E] [BorelSpace E]
    {Ω : Type*} [MeasurableSpace Ω] (μ : Measure Ω) [IsProbabilityMeasure μ]
    (X D : Set E) (hXcpt : IsCompact X) (hXconv : Convex ℝ X) (hXD : X ⊆ closure D)
    (hXDne : (X ∩ D).Nonempty)
    (Φ : E → ℝ) (Φ' : E → E →L[ℝ] ℝ) (hΦ : IsMirrorMap D Φ Φ')
    (hΦsc : IsStronglyConvexWRT (X ∩ D) Φ Φ' 1)
    (x₁ : E) (R : ℝ) (hR : ∀ z ∈ X ∩ D, Φ z - Φ x₁ ≤ R ^ 2)
    (f : E → ℝ) (f' : E → E →L[ℝ] ℝ) (β : ℝ) (hβ : 0 ≤ β)
    (hf : ConvexOn ℝ X f) (hsmooth : IsSmoothWRT X f f' β)
    (σ : ℝ) (x : ℕ → Ω → E) (gt : ℕ → Ω → E →L[ℝ] ℝ)
    (horacle : IsSmoothStochOracle μ f' σ x gt)
    (η : ℝ) (hη : 0 < η) (hrun : IsSMDRun X D Φ Φ' (1 / (β + 1 / η)) x₁ x gt)
    (xstar : E) (hxstar : xstar ∈ X) (s : ℕ) (hs : 1 ≤ s) :
    Integrable (fun ω => f (x (s + 1) ω)) μ ∧
      Integrable (fun ω => bregman Φ Φ' xstar (x s ω) - bregman Φ Φ' xstar (x (s + 1) ω)) μ ∧
      (∫ ω, f (x (s + 1) ω) ∂μ) - f xstar ≤
        (β + 1 / η) *
            (∫ ω, (bregman Φ Φ' xstar (x s ω) - bregman Φ Φ' xstar (x (s + 1) ω)) ∂μ) +
          η * σ ^ 2 / 2 := by sorry

end ConvexOptAlg.StochMD
Source
Bubeck, arXiv:1405.4980v2, §6.2, proof of Theorem 6.3, fourth display, p. 333
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

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