Theorem 8.2 — with anomalies,
ProvedWeightedMajority.RandAnomalies.theorem_8_2Let be a pool of -valued functions on an arbitrary domain , let be an integer, let be the optimal worst-case number of mistakes of a deterministic learner on sequences consistent with some member of , and let be the optimal worst-case expected number of mistakes of a randomized learner on sequences with at most anomalies with respect to .
Theorem 8.2. If contains at least two functions, then
Thus every randomized learner has worst-case expected mistakes at least over sequences fixed in advance with at most anomalies. When , these expected mistake counts are unbounded. It is the randomized counterpart of Theorem 8.1 (), and shows that the coefficient of in the expected mistake bound of the randomized Weighted Majority algorithm WMR cannot be improved by any randomized algorithm.
Formalization Note is cast to , where . "" is F.Nontrivial (two distinct members), which also covers infinite pools.
import Definitions.Def_WeightedMajority_RandAnomalies_OptRand open scoped ENNReal
namespace WeightedMajority.RandAnomalies
/-- **Theorem 8.2** (Littlestone–Warmuth 1994, p. 252). For all target classes `F` and all
`η ≥ 0`, if `|F| > 1` then `opt_RAND(F, η) ≥ ½ opt(F, 0) + η`. -/
theorem theorem_8_2 {X : Type*} (F : Set (X → Bool)) (hF : F.Nontrivial) (η : ℕ) :
((WeightedMajority.Anomalies.opt F 0 : ℕ∞) : ℝ≥0∞) / 2 + η ≤ optRand F η := by sorry
end WeightedMajority.RandAnomalies
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.