Proof of Theorem 1 — the mini-batch objective f(·; A) is λ-strongly convex
ProvedPegasos.Analysis.instObj_strongly_convexp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1strong-convexitysvm
For any data and any mini-batch of indices, the instantaneous objective is -strongly convex in the paper's sense:
This verifies the first hypothesis of Lemma 1 for the functions .
Formalization Note. The paper's definition of -strong convexity (p. 9) is used verbatim, so the statement is the convexity of the averaged hinge loss over the batch; it holds for every real and every (at , Lean's makes the average ).
Preamble
import Mathlib import Definitions.Def_Pegasos_Analysis_Model
Formal statement
namespace Pegasos.Analysis
/-- **Proof of Theorem 1** (p. 11): the instantaneous objective `f(·; A)` of Eq. (7) is
λ-strongly convex in the paper's sense (p. 9): `f(w; A) − λ/2‖w‖²` is a convex function
of `w`. -/
theorem instObj_strongly_convex {n m k : ℕ} (lam : ℝ)
(x : Fin m → EuclideanSpace ℝ (Fin n)) (y : Fin m → ℝ) (B : Fin k → Fin m) :
ConvexOn ℝ Set.univ (fun w => instObj lam x y B w - lam / 2 * ‖w‖ ^ 2) := 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
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.