Eq. (10) — the sub-gradient inequality for λ-strongly convex functions
ProvedPegasos.Analysis.eq_10p2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1strong-convexitysubgradient
Call -strongly convex if is convex, and call a sub-gradient of at if for every .
If is -strongly convex and is a sub-gradient of at , then for every
This is the per-round inequality that, in the proof of Lemma 1, upgrades the linear lower bound of a sub-gradient to a quadratic one; it is what produces the logarithmic rate.
Formalization Note. Strong convexity is stated as the paper defines it (p. 9), as convexity of on all of ; no sign condition on is imposed, since the inequality holds for every real . No differentiability is assumed.
Preamble
import Mathlib import Definitions.Def_Pegasos_Analysis_Model
Formal statement
namespace Pegasos.Analysis
/-- **Eq. (10)** (p. 10, proof of Lemma 1): if `f` is λ-strongly convex in the paper's sense
(`f(w) − λ/2‖w‖²` is convex, p. 9) and `g` is a sub-gradient of `f` at `w`
(`∀ u, f(u) − f(w) ≥ ⟨g, u − w⟩`, p. 17), then for every `u`,
`⟨w − u, g⟩ ≥ f(w) − f(u) + λ/2 ‖w − u‖²`. -/
theorem eq_10 {n : ℕ} (lam : ℝ) (f : EuclideanSpace ℝ (Fin n) → ℝ)
(hf : ConvexOn ℝ Set.univ (fun v => f v - lam / 2 * ‖v‖ ^ 2))
(w g : EuclideanSpace ℝ (Fin n)) (hg : UnderstandingML.IsSubgradient f w g)
(u : EuclideanSpace ℝ (Fin n)) :
f w - f u + lam / 2 * ‖w - u‖ ^ 2 ≤ inner ℝ (w - u) g := by sorry
end Pegasos.Analysis
Source
Shalev-Shwartz, Singer, Srebro & Cotter, Pegasos: primal estimated sub-gradient solver for SVM, Math. Program. 127 (2011), p. 10, Eq. (10) (proof of Lemma 1); λ-strong convexity p. 9; sub-gradient p. 17
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.