Eq. (8) is a sub-gradient of the mini-batch objective f(·; A)
ProvedPegasos.Analysis.eq_8_subgradientp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1subgradientsvm
Let , let be examples with , , and let be a mini-batch of indices. For every , the vector
of Eq. (8) is a sub-gradient at of the instantaneous objective of Eq. (7): for all .
This is what makes each Pegasos step a sub-gradient step on , so that Lemma 1 applies.
Formalization Note. The statement holds for every real label (at the kink the chosen value is a sub-gradient of the hinge), so no hypothesis is needed. The mini-batch is a -tuple of indices; repeated indices are allowed.
Preamble
import Mathlib import Definitions.Def_Pegasos_Analysis_Model
Formal statement
namespace Pegasos.Analysis
/-- **Eq. (8)** (p. 8, §2.3): the vector `∇ = λw − (1/k) Σ_{i∈A} 1l[yᵢ⟨w, xᵢ⟩ < 1] yᵢxᵢ` is a
sub-gradient of the instantaneous objective `f(·; A)` of Eq. (7) at `w`, for every
mini-batch `A` and every `w`. -/
theorem eq_8_subgradient {n m k : ℕ} (lam : ℝ) (hlam : 0 < lam)
(x : Fin m → EuclideanSpace ℝ (Fin n)) (y : Fin m → ℝ) (B : Fin k → Fin m)
(w : EuclideanSpace ℝ (Fin n)) :
UnderstandingML.IsSubgradient (instObj lam x y B) w (subgrad lam x y B w) := by sorry
end Pegasos.Analysis
Source
Shalev-Shwartz, Singer, Srebro & Cotter, Pegasos: primal estimated sub-gradient solver for SVM, Math. Program. 127 (2011), p. 8, §2.3, Eq. (8) (and Eq. (7)); used in the proof of Theorem 1, p. 11
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.