Appendix, p. 256 — a mistake of WMG multiplies the total weight by at most (1+β)/2
ProvedWeightedMajority.General.appendix_mistake_stepmistake-boundonline-learningp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1weighted-majority
Let and consider a run of the algorithm WMG with parameter on a pool of algorithms with predictions and binary labels , with weights and total weights . If WMG makes a mistake in trial , that is, its prediction differs from , then the total weight after the update is at most a fraction of the total weight before it:
In the notation of the Appendix, with and , the total weight before the trial is and the claim is that it is at most afterwards.
This is the step on which the alternate proof of Theorem 5.1 in the Appendix rests.
Formalization Note The run is the relation IsWMGRun; the claim holds for every choice of tie-breaking, update flags and factors allowed by (5.1).
Preamble
import Mathlib import Definitions.Def_WeightedMajority_General_WMGRun
Formal statement
namespace WeightedMajority.General
/-- Appendix, p. 256 (alternate proof of Theorem 5.1): in a trial in which WMG makes a mistake,
the total weight after the update is at most `(1 + β) / 2` times the total weight before it. -/
theorem appendix_mistake_step {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)
(k : Fin T) (hmis : pred k ≠ ρ k) :
WeightedMajority.Basic.totalWeight w (k.val + 1) ≤ (1 + β) / 2 * WeightedMajority.Basic.totalWeight w k.val := by sorry
end WeightedMajority.General
Source
Littlestone, Warmuth, The Weighted Majority Algorithm, Inform. and Comput. 108 (1994), p. 256, Appendix, alternate proof of Theorem 5.1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.