Theorem 8.1 — with η anomalies, opt(F, η) ≥ opt(F, 0) + 2η for every class with |F| > 1
ProvedWeightedMajority.Anomalies.theorem_8_1Let be an arbitrary domain and a class of -valued functions on , possibly infinite, with at least two members. For let be the minimum, over all deterministic on-line prediction algorithms , of the maximum number of mistakes makes on a finite sequence of trials having at most anomalies with respect to (some disagrees with at most of its labels). Then
Each anomaly the adversary is allowed therefore costs every deterministic learner at least two additional mistakes beyond the optimal noise-free bound. The theorem shows that the deterministic Weighted Majority algorithm, whose mistake bound grows at a rate that can be made arbitrarily close to per anomaly by the choice of , has an essentially optimal rate of growth in the number of anomalies.
Formalization Note Values are in (ℕ∞); when the statement says . The hypothesis is F.Nontrivial (two distinct members), which also covers infinite classes.
import Mathlib import Definitions.Def_UnderstandingML_Online import Definitions.Def_WeightedMajority_Anomalies_Opt
namespace WeightedMajority.Anomalies
/-- Littlestone and Warmuth's Theorem 8.1 (p. 250): for every class `F` of `{0,1}`-valued
functions with `|F| > 1` and every `η ≥ 0`, `opt(F, η) ≥ opt(F, 0) + 2η`. -/
theorem theorem_8_1 {X : Type*} (F : Set (X → Bool)) (hF : F.Nontrivial) (η : ℕ) :
opt F 0 + 2 * (η : ℕ∞) ≤ opt F η := by sorry
end WeightedMajority.Anomalies
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.