Theorem 4.1(2) — total weight of WMI₂ after m mistakes is at most (2 − 1/(m+1)) u^m Ŵ(1)
ProvedWeightedMajority.InfinitePool.theorem_4_1_part_2Let , , and let be real functions on the positive integers with for all , , for all , and . Consider any run of with parameter on any sequence of trials with binary predictions and labels. For let be the current weight of after the first trials if is active (), and if it is inactive.
If mistakes have been made by in the first trials, then the series converges and
This is the potential bound behind the mistake bound of : every mistake shrinks the total weight, counting inactive members at their initial weights, by a factor close to , the same factor as for the ordinary Weighted Majority Algorithm, at the price of the bounded overhead .
Formalization Note. The statement holds at every boundary ("after any initial sequence of trials"). Summability is part of the conclusion so that the bound cannot hold through Lean's value for a divergent tsum. The paper's computability requirement on is dropped; the result does not depend on it.
import Mathlib import Definitions.Def_WeightedMajority_InfinitePool_IsWMI2Run
namespace WeightedMajority.InfinitePool
/-- Theorem 4.1, part 2 (Littlestone–Warmuth 1994, p. 227): after any initial sequence of
trials in which `m` mistakes have been made, `∑ ω_i ≤ (2 - 1/(m+1)) u^m Ŵ(1)`, where `ω_i` is
the current weight of an active member and `W(i)` for an inactive one. The family `ω` is also
asserted to be summable. -/
theorem theorem_4_1_part_2
(β : ℝ) (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 ≤ T,
Summable (omega W w l t) ∧
∑' i, omega W w l t i ≤
(2 - 1 / ((mistakesBefore prediction label t : ℝ) + 1)) *
u β ^ mistakesBefore prediction label t * What 1 := by sorry
end WeightedMajority.InfinitePool
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.