Section 2 — total-weight contraction on a WM mistake
ProvedWeightedMajority.Basic.mistake_weight_stepmistake-boundonline-learningp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1weighted-majority
Let WM use factor and strictly positive initial weights on a finite pool. Consider any finite binary sequence and any legal WM run. If the master errs on trial , the total pool weight after that trial is at most times its weight before the trial:
This is the local weight estimate in the proof of Theorem 2.1. It applies to either permitted tie choice.
Formalization Note The statement uses a weight inequality, which remains meaningful when a later weight is zero; no division by the current weight is needed.
Preamble
import Mathlib import Definitions.Def_WeightedMajority_Basic_IsWMRun
Formal statement
namespace WeightedMajority.Basic
/-- The per-mistake weight estimate used in the proof of Theorem 2.1. -/
theorem mistake_weight_step {n T : ℕ} (β : ℝ) (hβ₀ : 0 ≤ β) (hβ₁ : β < 1)
(initial : Fin n → ℝ) (hinitial : ∀ i, 0 < initial i)
(x : Fin T → Fin n → Bool) (label : Fin T → Bool)
(w : ℕ → Fin n → ℝ) (prediction : Fin T → Bool)
(hrun : IsWMRun β initial x label w prediction)
(t : Fin T) (hmistake : prediction t ≠ label t) :
totalWeight w (t.val + 1) ≤ ((1 + β) / 2) * totalWeight w t.val := by sorry
end WeightedMajority.Basic
Source
Littlestone and Warmuth, The Weighted Majority Algorithm, Information and Computation 108(2) (1994), p. 221, §2, proof of Theorem 2.1; https://doi.org/10.1006/inco.1994.1009
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.