§3, p. 224, proof of Lemma 3.1 — a mistake of WML multiplies the total weight by at most u = (1+β)/2 + (1−β)γ
ProvedWeightedMajority.Shifting.lemma_3_1_ratiomistake-boundonline-learningp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1weighted-majority
Let and , and consider a run of the algorithm WML with parameters on a pool of algorithms and an arbitrary sequence of binary-labelled trials. Write for the total weight of the pool at the beginning of trial . If the master algorithm makes a mistake in trial , then
This is the per-mistake contraction step of the proof of Lemma 3.1: members whose weight is at most times the total are protected from the update, and their total weight is at most , which is what the extra term accounts for. Since , the factor is less than .
Formalization Note is totalWeight (w t) and the factor is uFactor β γ. The run's initial weights are positive, as WML requires.
Preamble
import Mathlib import Definitions.Def_WeightedMajority_Shifting_WML
Formal statement
namespace WeightedMajority.Shifting
theorem lemma_3_1_ratio {n T : ℕ} {β γ : ℝ} (hβ0 : 0 < β) (hβ1 : β < 1)
(hγ0 : 0 ≤ γ) (hγ1 : γ < 1 / 2)
(x : Fin T → Fin n → Bool) (ρ : Fin T → Bool) (w : ℕ → Fin n → ℝ) (lam : Fin T → Bool)
(hrun : IsWMLRun β γ x ρ w lam) (t : Fin T) (hmis : lam t ≠ ρ t) :
totalWeight (w ((t : ℕ) + 1)) ≤ uFactor β γ * totalWeight (w t) := by sorry
end WeightedMajority.Shifting
Source
Littlestone, Warmuth, The Weighted Majority Algorithm, Inform. and Comput. 108 (1994), p. 224, Section 3, proof of Lemma 3.1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.