Eq. (13) — without projection, w_{t+1} = (1/(λt)) Σ_{i≤t} v_i
ProvedPegasos.Analysis.eq_13p2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1stochastic-subgradientsvm
Let and run mini-batch Pegasos (Fig. 2) without the projection step, on any sequence of mini-batches of indices. Write
Then for every
Writing the unprojected iterate as an average of margin-violation vectors is what yields the norm bound .
Formalization Note. The paper's intermediate display (12) is printed as with inside the indicator; since the correct update is with in the indicator. Eq. (13) is correct as printed and is what is stated. Iterations are 1-based with .
Preamble
import Mathlib import Definitions.Def_Pegasos_Analysis_Model
Formal statement
namespace Pegasos.Analysis
/-- **Eq. (13)** (p. 11): without the projection step, for every `t ≥ 1`,
`w_{t+1} = (1/(λt)) Σ_{i=1}^t v_i` with `v_i = (1/k) Σ_{j∈A_i} 1l[y_j⟨w_i, x_j⟩ < 1] y_j x_j`. -/
theorem eq_13 {n m k : ℕ} (lam : ℝ) (hlam : 0 < lam)
(x : Fin m → EuclideanSpace ℝ (Fin n)) (y : Fin m → ℝ) (A : ℕ → Fin k → Fin m)
(t : ℕ) (ht : 1 ≤ t) :
run lam x y A false (t + 1)
= (1 / (lam * (t : ℝ))) • ∑ i ∈ Finset.Icc 1 t, hingeTerm x y (A i) (run lam x y A false i) := 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, Eq. (13) (proof of Theorem 1)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.