Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

§6.3, p. 338 — general one-epoch gap bound

Proved
ConvexOptAlg.SVRG.epoch_bound

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

convex-optimizationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1strong-convexitysvrg

Let m,k≥1m,k\ge1m,k≥1, let each component fif_ifi​ be convex and β\betaβ-smooth, and suppose their average fff is α\alphaα-strongly convex with minimizer x∗x^*x∗, where α,β>0\alpha,\beta>0α,β>0. For an anchor yyy and a step size 0<η<1/(2β)0<\eta<1/(2\beta)0<η<1/(2β), run an SVRG epoch and average the first kkk inner iterates to obtain y+y^+y+. Then

E f(y+)−f(x∗)≤(1αη(1−2βη)k+2βη1−2βη)(f(y)−f(x∗)).\mathbb E\,f(y^+)-f(x^*)\le\left(\frac{1}{\alpha\eta(1-2\beta\eta)k}+\frac{2\beta\eta}{1-2\beta\eta}\right)\bigl(f(y)-f(x^*)\bigr).Ef(y+)−f(x∗)≤(αη(1−2βη)k1​+1−2βη2βη​)(f(y)−f(x∗)).

The expectation is over all kkk independent uniform component indices in the epoch. This is the general contraction formula before the constants of Theorem 6.5 are substituted.

Formalization Note Strong convexity uses the published StronglyConvexOn definition on all of Rn\mathbb R^nRn. The condition 2βη<12\beta\eta<12βη<1 makes the denominators positive.

Preamble
import Mathlib
import Definitions.Def_ConvexOptAlg_SVRG_Defs
import Definitions.Def_OnlineConvexOpt_ConvexBasics_StronglyConvexOn

open scoped InnerProductSpace
Formal statement
namespace ConvexOptAlg.SVRG

/-- The rearranged one-epoch inequality on p. 338, before substituting
`η = 1/(10β)` and `k = 20β/α`. The expectation is over all `k` samples. -/
theorem epoch_bound {n m : ℕ}
    (fs : Fin m → EuclideanSpace ℝ (Fin n) → ℝ)
    (gs : Fin m → EuclideanSpace ℝ (Fin n) → EuclideanSpace ℝ (Fin n))
    (α β η : ℝ) (k : ℕ) (y xstar : EuclideanSpace ℝ (Fin n))
    (hm : 0 < m) (hk : 0 < k) (hα : 0 < α) (hβ : 0 < β)
    (hη : 0 < η) (hηsmall : 2 * β * η < 1)
    (hfamily : SmoothConvexFamily fs gs β)
    (hstrong : OnlineConvexOpt.ConvexBasics.StronglyConvexOn
      Set.univ (objective fs) (fullGradient gs) α)
    (hmin : ∀ z, objective fs xstar ≤ objective fs z) :
    uniformMean (fun idx : Fin k → Fin m => objective fs (epochOut gs η k y idx)) -
        objective fs xstar ≤
      (1 / (α * η * (1 - 2 * β * η) * (k : ℝ)) +
        2 * β * η / (1 - 2 * β * η)) *
        (objective fs y - objective fs xstar) := by sorry

end ConvexOptAlg.SVRG
Source
Bubeck, arXiv:1405.4980v2, §6.3, p. 338, PDF p. 111, unnumbered rearranged epoch display
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