Proof of Theorem 1 — the SVM optimum satisfies ‖w⋆‖ ≤ 1/√λ
ProvedPegasos.Analysis.wstar_norm_bounddualityp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1svm
Let and let be examples with and . If minimises the SVM objective
of Eq. (1) (that is, is as in Eq. (9)), then
So the optimum lies in the ball onto which projected Pegasos projects, which is the last hypothesis of Lemma 1 () in the projected case.
Formalization Note. The minimiser is any with for all ; no dual problem is formalized (the paper's proof goes through the dual (14)–(15), but the statement concerns only the primal minimiser).
Preamble
import Mathlib import Definitions.Def_Pegasos_Analysis_Model
Formal statement
namespace Pegasos.Analysis
/-- **Proof of Theorem 1** (pp. 11–12): every minimiser `w⋆` of the SVM objective (1)
(Eq. (9)) satisfies `‖w⋆‖ ≤ 1/√λ`. -/
theorem wstar_norm_bound {n m : ℕ} (lam : ℝ) (hlam : 0 < lam)
(x : Fin m → EuclideanSpace ℝ (Fin n)) (y : Fin m → ℝ) (hy : ∀ i, y i = 1 ∨ y i = -1)
(wstar : EuclideanSpace ℝ (Fin n)) (hwstar : ∀ w, svmObj lam x y wstar ≤ svmObj lam x y w) :
‖wstar‖ ≤ 1 / Real.sqrt lam := by sorry
end Pegasos.Analysis
Source
Shalev-Shwartz, Singer, Srebro & Cotter, Pegasos: primal estimated sub-gradient solver for SVM, Math. Program. 127 (2011), pp. 11-12, proof of Theorem 1 (with Eq. (1) and (9))
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.