Theorem 4.1(1) — size of the active pool of WMI₂
ProvedWeightedMajority.InfinitePool.theorem_4_1_part_1Let , , and let be real functions on the positive integers with for all , , for all , and . Let , () be any sequence of predictions of the pool members and labels, on which makes at most mistakes, and consider any run of with parameter on it.
Then at the beginning of every trial the size of the active pool is the minimum such that
where is the number of mistakes made by in the trials before .
The algorithm raises to the least admissible value at or above its previous value; this statement says that this local rule yields the global minimum, so the active pool is no larger than necessary. Part 1 is used in the proof of part 2 to bound the total weight of the inactive members.
Formalization Note. Minimality is stated as: the inequality holds at and fails at every . The pool is indexed by ℕ+, so is What (Nat.succPNat l). The hypotheses on are those of Theorem 4.1, without the paper's computability requirement, which the result does not depend on.
import Mathlib import Definitions.Def_WeightedMajority_InfinitePool_IsWMI2Run
namespace WeightedMajority.InfinitePool
/-- Theorem 4.1, part 1 (Littlestone–Warmuth 1994, p. 226): at the beginning of any trial the
size of the active pool of WMI₂ is the minimum `l` with `Ŵ(l + 1) ≤ slack m`, where `m` is the
number of mistakes made in prior trials. -/
theorem theorem_4_1_part_1
(β : ℝ) (hβ0 : 0 ≤ β) (hβ1 : β < 1)
(W What : ℕ+ → ℝ) (hW_pos : ∀ i, 0 < W i) (hW_sum : Summable W)
(hWhat_tail : ∀ i, (∑' j : ℕ+, if i ≤ j then W j else 0) ≤ What i)
(hWhat_lim : Filter.Tendsto What Filter.atTop (nhds 0))
{T : ℕ} (x : Fin T → ℕ+ → Bool) (label : Fin T → Bool)
(mi : ℕ+ → ℕ)
(hmi : ∀ i, (Finset.univ.filter (fun t : Fin T => x t i ≠ label t)).card ≤ mi i)
(prediction : Fin T → Bool) (w : ℕ → ℕ+ → ℝ) (l : ℕ → ℕ)
(hrun : IsWMI2Run β W What x label prediction w l) :
∀ t : Fin T,
What (Nat.succPNat (l t.val)) ≤ slack β What (mistakesBefore prediction label t.val) ∧
∀ l' < l t.val,
slack β What (mistakesBefore prediction label t.val) < What (Nat.succPNat l') := by sorry
end WeightedMajority.InfinitePool
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.