Proof of Theorem 1 — without projection, ‖w_{t+1}‖ ≤ R/λ and ‖∇_t‖ ≤ 2R
ProvedPegasos.Analysis.subgrad_bound_no_projectionp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1stochastic-subgradientsvm
Let , , labels and for every example. Run mini-batch Pegasos (Fig. 2) without the projection step, on any sequence of mini-batches. Then for every
where is the sub-gradient (8) at on the batch .
This is the gradient bound that Lemma 1 needs in the unprojected case (with ).
Formalization Note. Iterations are 1-based with ; mini-batches are -tuples of indices and the statement holds for every sequence of them.
Preamble
import Mathlib import Definitions.Def_Pegasos_Analysis_Model
Formal statement
namespace Pegasos.Analysis
/-- **Proof of Theorem 1** (p. 11): without the projection step, for every `t ≥ 1`,
`‖w_{t+1}‖ ≤ R/λ` and the sub-gradient (8) at `w_t` on `A_t` satisfies `‖∇_t‖ ≤ 2R`. -/
theorem subgrad_bound_no_projection {n m k : ℕ} (lam R : ℝ) (hlam : 0 < lam) (hk : 0 < k)
(x : Fin m → EuclideanSpace ℝ (Fin n)) (y : Fin m → ℝ) (hy : ∀ i, y i = 1 ∨ y i = -1)
(hR : ∀ i, ‖x i‖ ≤ R) (A : ℕ → Fin k → Fin m) (t : ℕ) (ht : 1 ≤ t) :
‖run lam x y A false (t + 1)‖ ≤ R / lam ∧
‖subgrad lam x y (A t) (run lam x y A false t)‖ ≤ 2 * R := 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.