Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 1 — projected sub-gradient steps 1/(λt) on λ-strongly convex functions have average regret G²(1+ln T)/(2λT)

Proved
Pegasos.Analysis.lemma_1

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

online-convex-optimizationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1strong-convexitysubgradient

Let λ>0\lambda > 0λ>0, let f1,…,fT:Rn→Rf_1,\dots,f_T:\mathbb R^n\to\mathbb Rf1​,…,fT​:Rn→R be λ\lambdaλ-strongly convex (each ft−λ2∥⋅∥2f_t - \frac\lambda2\|\cdot\|^2ft​−2λ​∥⋅∥2 is convex), and let B⊆RnB\subseteq\mathbb R^nB⊆Rn be closed and convex, with Euclidean projection ΠB(w)=arg⁡min⁡w′∈B∥w−w′∥\Pi_B(w) = \arg\min_{w'\in B}\|w - w'\|ΠB​(w)=argminw′∈B​∥w−w′∥. Let w1,…,wT+1w_1,\dots,w_{T+1}w1​,…,wT+1​ satisfy w1∈Bw_1\in Bw1​∈B and, for 1≤t≤T1\le t\le T1≤t≤T,

wt+1=ΠB(wt−ηt∇t),ηt=1λt,w_{t+1} = \Pi_B(w_t - \eta_t\nabla_t),\qquad \eta_t = \frac{1}{\lambda t},wt+1​=ΠB​(wt​−ηt​∇t​),ηt​=λt1​,

where ∇t\nabla_t∇t​ is a sub-gradient of ftf_tft​ at wtw_twt​ with ∥∇t∥≤G\|\nabla_t\|\le G∥∇t​∥≤G. Then for every u∈Bu\in Bu∈B,

1T∑t=1Tft(wt)  ≤  1T∑t=1Tft(u)+G2(1+ln⁡T)2λT.\frac1T\sum_{t=1}^T f_t(w_t) \;\le\; \frac1T\sum_{t=1}^T f_t(u) + \frac{G^2(1+\ln T)}{2\lambda T}.T1​t=1∑T​ft​(wt​)≤T1​t=1∑T​ft​(u)+2λTG2(1+lnT)​.

This is the logarithmic-regret bound for online sub-gradient descent on strongly convex losses, without any smoothness; Theorem 1 is this lemma applied to the Pegasos iterates.

Formalization Note. The step producing wt+1w_{t+1}wt+1​ uses ηt=1/(λt)\eta_t = 1/(\lambda t)ηt​=1/(λt), as in the paper (iterations are 1-based). "wt+1w_{t+1}wt+1​ is the projection" is the predicate IsProj B v z (z∈Bz \in Bz∈B and ∥z−v∥≤∥w−v∥\|z - v\| \le \|w - v\|∥z−v∥≤∥w−v∥ for all w∈Bw\in Bw∈B). The hypotheses are required only for 1≤t≤T1 \le t \le T1≤t≤T. No lower bound on TTT is assumed; at T=0T = 0T=0 both sides are 000 in Lean.

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

/-- **Lemma 1** (p. 10): let `f₁, …, f_T` be λ-strongly convex (`f_t − λ/2‖·‖²` convex),
`B` a closed convex set, `w₁ ∈ B` and, for `t ≥ 1`, `w_{t+1} = Π_B(w_t − η_t ∇_t)` with
`∇_t` a sub-gradient of `f_t` at `w_t`, `η_t = 1/(λt)` and `‖∇_t‖ ≤ G`. Then for all
`u ∈ B`, `(1/T) Σ_{t=1}^T f_t(w_t) ≤ (1/T) Σ_{t=1}^T f_t(u) + G²(1 + ln T)/(2λT)`. -/
theorem lemma_1 {n : ℕ} (lam G : ℝ) (hlam : 0 < lam) (B : Set (EuclideanSpace ℝ (Fin n)))
    (hBclosed : IsClosed B) (hBconvex : Convex ℝ B) (T : ℕ)
    (f : ℕ → EuclideanSpace ℝ (Fin n) → ℝ) (w g : ℕ → EuclideanSpace ℝ (Fin n))
    (hf : ∀ t ∈ Finset.Icc 1 T, ConvexOn ℝ Set.univ (fun v => f t v - lam / 2 * ‖v‖ ^ 2))
    (hw1 : w 1 ∈ B)
    (hstep : ∀ t ∈ Finset.Icc 1 T,
      LogRegretOCO.OGD.IsProj B (w t - (1 / (lam * (t : ℝ))) • g t) (w (t + 1)))
    (hg : ∀ t ∈ Finset.Icc 1 T, UnderstandingML.IsSubgradient (f t) (w t) (g t))
    (hG : ∀ t ∈ Finset.Icc 1 T, ‖g t‖ ≤ G)
    (u : EuclideanSpace ℝ (Fin n)) (hu : u ∈ B) :
    (1 / (T : ℝ)) * ∑ t ∈ Finset.Icc 1 T, f t (w t)
      ≤ (1 / (T : ℝ)) * ∑ t ∈ Finset.Icc 1 T, f t u
        + G ^ 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. 10, Lemma 1
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