Eq. (8.5), p. 145 — mistakes bounded by margin and hinge loss
ProvedModernOnlineLearning.Classification.eq_8_5machine-learningmistake-boundp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1perceptron
For Algorithm 8.2 with , let and let be the hinge loss. Every satisfies
This is the implicit mistake inequality to which Lemma 4.29 applies at .
Formalization Note Labels are restricted to on rounds and is explicit. A zero score is an update and a mistake.
Preamble
import Mathlib import Definitions.Def_ModernOnlineLearning_Classification_Perceptron
Formal statement
namespace ModernOnlineLearning.Classification
/-- Orabona, Eq. (8.5), p. 145, including its bound by the full hinge loss. -/
theorem eq_8_5 {d : ℕ} (T : ℕ) (z : ℕ → ModernOnlineLearning.Adaptive.Vec d) (y : ℕ → ℝ)
(hy : ∀ t ∈ Finset.Icc 1 T, y t = -1 ∨ y t = 1)
(R : ℝ) (hR : 0 ≤ R)
(hz : ∀ t ∈ Finset.Icc 1 T, ‖z t‖ ≤ R) (u : ModernOnlineLearning.Adaptive.Vec d) :
mistakes z y T ≤
‖u‖ * R * Real.sqrt (mistakes z y T) +
(∑ t ∈ Finset.Icc 1 T,
mistakeIndicator z y t * hingePower 1 (inner ℝ (z t) u) (y t)) ∧
‖u‖ * R * Real.sqrt (mistakes z y T) +
(∑ t ∈ Finset.Icc 1 T,
mistakeIndicator z y t * hingePower 1 (inner ℝ (z t) u) (y t)) ≤
‖u‖ * R * Real.sqrt (mistakes z y T) + cumulativeHinge z y T u 1 := by sorry
end ModernOnlineLearning.Classification
Source
Orabona, arXiv:1912.13213v10, Eq. (8.5), proof of Theorem 8.2, p. 145
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.