Eq. (8.4), p. 145 — Perceptron comparator inequality (corrected)
ProvedModernOnlineLearning.Classification.eq_8_4machine-learningmistake-boundp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1perceptron
Let indicate the update rounds of Algorithm 8.2, let , and suppose . For every competitor ,
This is the comparator estimate used to obtain the mistake inequality (8.5).
Formalization Note The printed (8.4) adds on the left. That version is false for the actual Perceptron iterates: with , , and , its left side is and its right side . The Lean statement drops that nonnegative summand, preserving the valid inequality needed for (8.5). The source text is retained verbatim in the milestone record.
Preamble
import Mathlib import Definitions.Def_ModernOnlineLearning_Classification_Perceptron
Formal statement
namespace ModernOnlineLearning.Classification
/-- Orabona, Eq. (8.4), p. 145, with its invalid `-⟨τ_t y_t z_t,x_t⟩`
summand omitted from the left. The comparator term is the part used in Eq. (8.5). -/
theorem eq_8_4 {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) :
(∑ t ∈ Finset.Icc 1 T, mistakeIndicator z y t * y t * inner ℝ (z t) u) ≤
‖u‖ * Real.sqrt (∑ t ∈ Finset.Icc 1 T,
mistakeIndicator z y t * ‖z t‖ ^ 2) ∧
‖u‖ * Real.sqrt (∑ t ∈ Finset.Icc 1 T,
mistakeIndicator z y t * ‖z t‖ ^ 2) ≤
‖u‖ * R * Real.sqrt (mistakes z y T) := by sorry
end ModernOnlineLearning.Classification
Source
Orabona, arXiv:1912.13213v10, Eq. (8.4), proof of Theorem 8.2, p. 145 (corrected comparator form)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.