Theorem 7.2 — strict Kraft-type inequality for deterministic learners
ProvedWeightedMajority.Shattered.theorem_7_2Let be shattered by their domain, which may be finite or infinite. Let be any deterministic online learner. For each , let be the largest number of mistakes can make on a finite trial sequence whose labels agree with . If every is finite, then
This constrains the simultaneous per-target guarantees of every deterministic learner on a domain that realizes all label patterns across the target functions.
Formalization Note A published online-learning definition supplies the predictor, finite trial sequences, and the mistake-bound supremum in . The explicit finiteness hypothesis permits the conversion of each bound to a natural number. The empty-family sum is zero. Indices are zero-based in Lean.
import Definitions.Def_UnderstandingML_Online import Definitions.Def_WeightedMajority_Shattered_ShatteredByDomain
namespace WeightedMajority.Shattered
/-- Littlestone--Warmuth, Theorem 7.2, pp. 244--245. -/
theorem theorem_7_2 {X : Type*} {n : ℕ} (φ : Fin n → X → Bool)
(hφ : ShatteredByDomain φ) (A : UnderstandingML.OnlineAlg X Bool)
(hfin : ∀ i, UnderstandingML.mistakeBound A ({φ i} : Set (X → Bool)) < ⊤) :
(∑ i : Fin n, (2 : ℝ) ^ (-((UnderstandingML.mistakeBound A
({φ i} : Set (X → Bool))).toNat : ℤ))) < 2 := by sorry
end WeightedMajority.Shattered
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.