Section 2 — whole-sequence WM weight bound
ProvedWeightedMajority.Basic.weight_potentialmistake-boundonline-learningp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1weighted-majority
Run WM with factor and strictly positive initial weights on any finite binary sequence. Write for the number of mistakes made by the master, and and for the initial and final total pool weights. Then
This is the whole-sequence weight estimate stated before Theorem 2.1, with the value of used in that theorem. It also covers and a zero final weight.
Preamble
import Mathlib import Definitions.Def_WeightedMajority_Basic_IsWMRun
Formal statement
namespace WeightedMajority.Basic
/-- The whole-sequence weight estimate preceding Theorem 2.1. -/
theorem weight_potential {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) :
totalWeight w T ≤ totalWeight w 0 * ((1 + β) / 2) ^ mistakeCount prediction label := by sorry
end WeightedMajority.Basic
Source
Littlestone and Warmuth, The Weighted Majority Algorithm, Information and Computation 108(2) (1994), pp. 220–221, §2, discussion preceding 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.