Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 1 — mini-batch Pegasos has average instantaneous objective within c(1 + ln T)/(2λT) of the optimum's

Proved
Pegasos.Analysis.theorem_1

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

p2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1stochastic-subgradientstrong-convexitysvm

Let λ>0\lambda > 0λ>0 and let S=(xi,yi)i∈[m]S = (x_i,y_i)_{i\in[m]}S=(xi​,yi​)i∈[m]​ be a training set with xi∈Rnx_i\in\mathbb R^nxi​∈Rn, yi∈{+1,−1}y_i\in\{+1,-1\}yi​∈{+1,−1} and ∥xi∥≤R\|x_i\|\le R∥xi​∥≤R for every iii. Let f(w)=λ2∥w∥2+1m∑imax⁡{0,1−yi⟨w,xi⟩}f(w) = \frac\lambda2\|w\|^2 + \frac1m\sum_{i}\max\{0,1-y_i\langle w,x_i\rangle\}f(w)=2λ​∥w∥2+m1​∑i​max{0,1−yi​⟨w,xi​⟩} be the SVM objective (1), let w⋆w^\starw⋆ be a minimiser of fff (Eq. (9)), and for a mini-batch AAA of k≥1k\ge1k≥1 indices let f(w;A)=λ2∥w∥2+1k∑i∈Amax⁡{0,1−yi⟨w,xi⟩}f(w;A) = \frac\lambda2\|w\|^2 + \frac1k\sum_{i\in A}\max\{0,1-y_i\langle w,x_i\rangle\}f(w;A)=2λ​∥w∥2+k1​∑i∈A​max{0,1−yi​⟨w,xi​⟩} (Eq. (7)).

Run mini-batch Pegasos (Fig. 2) on any sequence of mini-batches A1,A2,…A_1, A_2,\dotsA1​,A2​,…: w1=0w_1 = 0w1​=0 and wt+1=P(wt−1λt∇t)w_{t+1} = P(w_t - \frac{1}{\lambda t}\nabla_t)wt+1​=P(wt​−λt1​∇t​) with ∇t\nabla_t∇t​ the sub-gradient (8) of f(⋅;At)f(\cdot;A_t)f(⋅;At​) at wtw_twt​ and PPP either the projection step (6) or the identity. Let

c={(λ+R)2with the projection step,4R2without it.c = \begin{cases}(\sqrt\lambda + R)^2 & \text{with the projection step},\\ 4R^2 & \text{without it}.\end{cases}c={(λ​+R)24R2​with the projection step,without it.​

Then for every T≥3T\ge3T≥3,

1T∑t=1Tf(wt;At)  ≤  1T∑t=1Tf(w⋆;At)+c (1+ln⁡T)2λT.\frac1T\sum_{t=1}^T f(w_t;A_t) \;\le\; \frac1T\sum_{t=1}^T f(w^\star;A_t) + \frac{c\,(1+\ln T)}{2\lambda T}.T1​t=1∑T​f(wt​;At​)≤T1​t=1∑T​f(w⋆;At​)+2λTc(1+lnT)​.

This is the paper's main convergence guarantee: the average instantaneous objective of the iterates approaches that of the SVM optimum at rate O(ln⁡T/(λT))O(\ln T/(\lambda T))O(lnT/(λT)), with no dependence on the number of examples mmm. Expectation and high-probability bounds for random mini-batches follow from it.

Formalization Note. The bound is pathwise: it is stated for every sequence of mini-batches, so no probability space appears (the paper's proof never uses that AtA_tAt​ is random). Mini-batches are kkk-tuples Fin k → Fin m; injective tuples are the subsets of Fig. 2 and non-injective ones the i.i.d. multi-sets the paper also allows (p. 9). Iterations are 1-based: w1=0w_1 = 0w1​=0 and step t≥1t\ge1t≥1 uses ηt=1/(λt)\eta_t = 1/(\lambda t)ηt​=1/(λt) and the batch AtA_tAt​ only. The flag project : Bool selects the variant, and ccc is chosen by it. ln⁡\lnln is Real.log of TTT cast to R\mathbb RR.

Preamble
import Mathlib
import Definitions.Def_Pegasos_Analysis_Model
Formal statement
namespace Pegasos.Analysis

/-- **Theorem 1** (p. 11): assume `‖xᵢ‖ ≤ R` for every example, let `w⋆` minimise the SVM
objective (1) (Eq. (9)), and let `c = (√λ + R)²` with the projection step and `c = 4R²`
without. Then for every mini-batch sequence `A_1, A_2, …` and `T ≥ 3`, the mini-batch
Pegasos run of Fig. 2 satisfies
`(1/T) Σ_{t=1}^T f(w_t; A_t) ≤ (1/T) Σ_{t=1}^T f(w⋆; A_t) + c(1 + ln T)/(2λT)`. -/
theorem theorem_1 {n m k : ℕ} (lam R : ℝ) (hlam : 0 < lam) (hk : 0 < k)
    (x : Fin m → EuclideanSpace ℝ (Fin n)) (y : Fin m → ℝ) (hy : ∀ i, y i = 1 ∨ y i = -1)
    (hR : ∀ i, ‖x i‖ ≤ R) (A : ℕ → Fin k → Fin m) (project : Bool)
    (wstar : EuclideanSpace ℝ (Fin n)) (hwstar : ∀ w, svmObj lam x y wstar ≤ svmObj lam x y w)
    (T : ℕ) (hT : 3 ≤ T) :
    (1 / (T : ℝ)) * ∑ t ∈ Finset.Icc 1 T, instObj lam x y (A t) (run lam x y A project t)
      ≤ (1 / (T : ℝ)) * ∑ t ∈ Finset.Icc 1 T, instObj lam x y (A t) wstar
        + (if project then (Real.sqrt lam + R) ^ 2 else 4 * R ^ 2) * (1 + Real.log T)
          / (2 * lam * T) := by sorry

end Pegasos.Analysis
Source
Shalev-Shwartz, Singer, Srebro & Cotter, Pegasos: primal estimated sub-gradient solver for SVM, Math. Program. 127 (2011), p. 11, Theorem 1 (with Eq. (1), (2), (6)-(9) and Fig. 2)
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