Proof of Theorem 1 — the projection step (6) is Π_B onto the ball of radius 1/√λ
ProvedPegasos.Analysis.projBall_isProjp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1projectionsvm
Let and let . For every , the point
produced by the projection step (6) is the Euclidean projection : it lies in and is at least as close to as every point of .
This lets the projected Pegasos update be written as , the form Lemma 1 requires.
Formalization Note. At the formula is undefined on paper; Lean's gives , which is the projection of .
Preamble
import Mathlib import Definitions.Def_Pegasos_Analysis_Model
Formal statement
namespace Pegasos.Analysis
/-- **Proof of Theorem 1** (p. 11): the projection step (6), `w ↦ min{1, (1/√λ)/‖w‖} w`,
is the Euclidean projection `Π_B` onto the closed ball `B` of radius `1/√λ` centred at 0. -/
theorem projBall_isProj {n : ℕ} (lam : ℝ) (hlam : 0 < lam) (v : EuclideanSpace ℝ (Fin n)) :
LogRegretOCO.OGD.IsProj (Metric.closedBall 0 (1 / Real.sqrt lam)) v (projBall lam v) := 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, proof of Theorem 1 (with Eq. (6), p. 8)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.