Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 5 — SGD with α-suffix averaging: E[F(w̄ᵅ_T) − F(w*)] ≤ (2 + 2.5 log(1/(1−α)))/α · G²/(λT)

Proved
OptimalSGD.Suffix.theorem_5

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

p2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1sgdstochastic-optimizationstrong-convexity

Let W⊆RdW\subseteq\mathbb R^dW⊆Rd be closed and convex with 0∈W0\in W0∈W, and let F:Rd→RF:\mathbb R^d\to\mathbb RF:Rd→R be λ\lambdaλ-strongly convex on WWW for some λ>0\lambda>0λ>0. Let DDD be a probability law on a sample space Z\mathcal ZZ and g:Rd×Z→Rdg:\mathbb R^d\times\mathcal Z\to\mathbb R^dg:Rd×Z→Rd a jointly measurable stochastic gradient oracle such that, for every w∈Ww\in Ww∈W, g(w,z)g(w,z)g(w,z) is integrable, its mean Ez∼D g(w,z)\mathbb E_{z\sim D}\,g(w,z)Ez∼D​g(w,z) is a subgradient of FFF at www relative to WWW, and

Ez∼D∥g(w,z)∥2≤G2.\mathbb E_{z\sim D}\|g(w,z)\|^2\le G^2 .Ez∼D​∥g(w,z)∥2≤G2.

Let w∗∈Ww^*\in Ww∗∈W minimize FFF over WWW. Run projected SGD with step sizes ηt=1/(λt)\eta_t=1/(\lambda t)ηt​=1/(λt) on an i.i.d. sample z1,…,zT∼Dz_1,\dots,z_T\sim Dz1​,…,zT​∼D, T≥1T\ge1T≥1:

w1=0,wt+1=ΠW(wt−ηt g(wt,zt)),w_1=0,\qquad w_{t+1}=\Pi_W\big(w_t-\eta_t\,g(w_t,z_t)\big),w1​=0,wt+1​=ΠW​(wt​−ηt​g(wt​,zt​)),

and let α∈(0,1)\alpha\in(0,1)α∈(0,1) be such that (1−α)T(1-\alpha)T(1−α)T is an integer. Return the α-suffix average

wˉTα=w(1−α)T+1+⋯+wTαT.\bar w^{\alpha}_T=\frac{w_{(1-\alpha)T+1}+\dots+w_T}{\alpha T}.wˉTα​=αTw(1−α)T+1​+⋯+wT​​.

Then F(wˉTα)F(\bar w^\alpha_T)F(wˉTα​) has a finite expectation and

E[F(wˉTα)−F(w∗)] ≤ 2+2.5log⁡11−αα⋅G2λT.\mathbb E\big[F(\bar w^{\alpha}_T)-F(w^*)\big]\ \le\ \frac{2+2.5\log\frac{1}{1-\alpha}}{\alpha}\cdot\frac{G^2}{\lambda T}.E[F(wˉTα​)−F(w∗)] ≤ α2+2.5log1−α1​​⋅λTG2​.

For any fixed α\alphaα this is an O(G2/(λT))O(G^2/(\lambda T))O(G2/(λT)) rate for plain SGD on a non-smooth strongly convex objective, whereas averaging all iterates can lose a log⁡T\log TlogT factor.

Formalization Note The paper's Hilbert space is specialized to Rd\mathbb R^dRd (UnderstandingML.Vec d). The statement of Theorem 5 on p. 6 writes the hypothesis as E∥g^t∥2≤G\mathbb E\|\hat g_t\|^2\le GE∥g^​t​∥2≤G; the standing assumption of §2 (p. 3) and the proof use G2G^2G2, which is what is stated here. "Regardless of how the iterates evolve" is rendered as the moment bound at every point of WWW. log⁡\loglog is the natural logarithm. The iterate index in Lean is the paper's t−1t-1t−1, and k=(1−α)Tk=(1-\alpha)Tk=(1−α)T is passed as a natural number tied to α\alphaα by k=(1−α)Tk=(1-\alpha)Tk=(1−α)T. Strong convexity is Mathlib's StrongConvexOn W lam F, equivalent to the paper's (1) for functions with subgradients relative to WWW at every point of WWW, which the oracle provides.


Retired 2026-10-27: a Lean-vs-paper fidelity audit found this statement weaker than, or narrower than, the cited result. A corrected statement will be resubmitted.

Preamble
import Definitions.Def_OptimalSGD_Suffix_Model

open MeasureTheory UnderstandingML
open scoped InnerProductSpace
Formal statement
namespace OptimalSGD.Suffix

/-- **Theorem 5** (Rakhlin, Shamir, Sridharan, arXiv:1109.5647v7, §5, p. 6; proof App. B.6,
p. 18). Consider projected SGD started at `w₁ = 0` with step sizes `η_t = 1/(λt)` on the closed
convex set `W ∋ 0`, an i.i.d. sample `S ∼ D^T`, and α-suffix averaging with `α ∈ (0, 1)` and
`k = (1 − α)T` an integer. Suppose `F` is `λ`-strongly convex on `W`, the oracle mean
`E_z g(w, z)` is a subgradient of `F` relative to `W` at every `w ∈ W`, `E‖g(w, z)‖² ≤ G²` at
every `w ∈ W`, and `w*` minimizes `F` over `W`. Then `F(w̄ᵅ_T)` has a finite expectation and
`E[F(w̄ᵅ_T) − F(w*)] ≤ (2 + 2.5 log(1/(1 − α)))/α · G²/(λT)`, `log` the natural logarithm. -/
theorem theorem_5
    {d : ℕ} {Z : Type*} [MeasurableSpace Z]
    (W : Set (Vec d)) (hWconv : Convex ℝ W) (hWclosed : IsClosed W) (hW0 : (0 : Vec d) ∈ W)
    (F : Vec d → ℝ) {lam : ℝ} (hlam : 0 < lam) (hF : StrongConvexOn W lam F)
    (D : Measure Z) [IsProbabilityMeasure D] (g : Vec d → Z → Vec d)
    (hg : Measurable (Function.uncurry g)) (horacle : IsSubgradientOracleOn W F D g)
    {G : ℝ} (hmoment : ∀ w ∈ W, ∫⁻ z, ENNReal.ofReal (‖g w z‖ ^ 2) ∂D ≤ ENNReal.ofReal (G ^ 2))
    (wstar : Vec d) (hwstar : wstar ∈ W) (hmin : ∀ w ∈ W, F wstar ≤ F w)
    {α : ℝ} (hα0 : 0 < α) (hα1 : α < 1) (T k : ℕ) (hT : 0 < T) (hk : (k : ℝ) = (1 - α) * T) :
    Integrable (fun S => F (suffixAverage lam W g S k)) (iidLaw D T) ∧
    ∫ S, (F (suffixAverage lam W g S k) - F wstar) ∂(iidLaw D T) ≤
      (2 + 2.5 * Real.log (1 / (1 - α))) / α * (G ^ 2 / (lam * T)) := by sorry

end OptimalSGD.Suffix
Source
Rakhlin, Shamir, Sridharan, Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization, arXiv:1109.5647v7, p. 6, Theorem 5 (proof App. B.6, p. 18)
Human review
  • Endorsed by Shuze Chen · Oct 7, 2026

    Confirmed by the moderator at approval.

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