Theorem 5.1 — WMG makes at most log(w_init/w_fin)/log(2/(1+β)) mistakes
ProvedWeightedMajority.General.theorem_5_1Let . Run the master algorithm WMG with parameter on a pool of prediction algorithms, whose predictions lie in , over any finite sequence of trials with binary labels ; WMG may update in every trial or only in the trials in which it makes a mistake, may break ties at either way, and may use any update factors allowed by (5.1). Let and be the total initial and final weights of the pool, and let be the number of mistakes of WMG. If , then
This is the mistake bound of Theorem 2.1 for the binary algorithm WM, extended to pools whose members predict numbers in . With equal initial weights it yields Corollary 5.1: the number of mistakes is at most for every pool member with total absolute loss .
Formalization Note The paper writes the bound as a ratio of logarithms with the base omitted; the ratio does not depend on the base, and Real.log is used. When (possible only if ) the paper's bound is , and Lean's Real.log and division conventions would give a false literal statement; this case is excluded by the hypothesis . The run is the relation IsWMGRun, so the bound is asserted for every tie-breaking, every update flag that is set on all mistake trials, and every factor in (5.1).
import Mathlib import Definitions.Def_WeightedMajority_General_WMGRun
namespace WeightedMajority.General
/-- Theorem 5.1 (pp. 234–235): for every run of WMG with `0 ≤ β < 1` on a sequence of `T` trials
with binary labels and pool predictions in `[0, 1]` (updating in every trial, only in mistake
trials, or in any set of trials containing the mistake trials), the number `m` of mistakes
satisfies `m ≤ log (w_init / w_fin) / log (2 / (1 + β))`, provided `w_fin > 0`
(for `w_fin = 0` the paper's bound is `+∞`). -/
theorem theorem_5_1 {n T : ℕ} {β : ℝ} {x : Fin T → Fin n → ℝ} {ρ : Fin T → ℝ}
{w : ℕ → Fin n → ℝ} {pred : Fin T → ℝ} {upd : Fin T → Bool} {F : Fin T → Fin n → ℝ}
(hβ0 : 0 ≤ β) (hβ1 : β < 1) (hrun : IsWMGRun β x ρ w pred upd F)
(hfin : 0 < WeightedMajority.Basic.totalWeight w T) :
(mistakeCount pred ρ : ℝ) ≤
Real.log (WeightedMajority.Basic.totalWeight w 0 / WeightedMajority.Basic.totalWeight w T) / Real.log (2 / (1 + β)) := by sorry
end WeightedMajority.General
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.