Lemma 1 — projected sub-gradient steps 1/(λt) on λ-strongly convex functions have average regret G²(1+ln T)/(2λT)
ProvedPegasos.Analysis.lemma_1online-convex-optimizationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1strong-convexitysubgradient
Let , let be -strongly convex (each is convex), and let be closed and convex, with Euclidean projection . Let satisfy and, for ,
where is a sub-gradient of at with . Then for every ,
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 uses , as in the paper (iterations are 1-based). " is the projection" is the predicate IsProj B v z ( and for all ). The hypotheses are required only for . No lower bound on is assumed; at both sides are 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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.