Theorem 1 — mini-batch Pegasos has average instantaneous objective within c(1 + ln T)/(2λT) of the optimum's
ProvedPegasos.Analysis.theorem_1Let and let be a training set with , and for every . Let be the SVM objective (1), let be a minimiser of (Eq. (9)), and for a mini-batch of indices let (Eq. (7)).
Run mini-batch Pegasos (Fig. 2) on any sequence of mini-batches : and with the sub-gradient (8) of at and either the projection step (6) or the identity. Let
Then for every ,
This is the paper's main convergence guarantee: the average instantaneous objective of the iterates approaches that of the SVM optimum at rate , with no dependence on the number of examples . 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 is random). Mini-batches are -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: and step uses and the batch only. The flag project : Bool selects the variant, and is chosen by it. is Real.log of cast to .
import Mathlib import Definitions.Def_Pegasos_Analysis_Model
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.