Lemma 3.1 — WML makes at most (log(n/(βγ)) + m₀ log(1/β))/log(1/u) mistakes, and keeps the weight floor
ProvedWeightedMajority.Shifting.lemma_3_1Let and , and put . Consider a pool of algorithms and any finite sequence of trials with binary predictions and labels, and let be the minimum, over the members of the pool, of the number of mistakes made on . Run WML with parameters on , from positive initial weights such that every initial weight is at least times the total initial weight:
Then:
- the number of mistakes made by WML on satisfies
- the final weights satisfy the same floor: for every .
The bound depends on the length of the sequence only through , and the second part allows the lemma to be applied again, from the final weights, to a following block of trials; this is how Theorem 3.1 is obtained.
Formalization Note The base of the logarithm cancels in the ratio, so the natural logarithm Real.log is used. The paper allows for the algorithm, but then the bound is and says nothing; in Lean would make the literal statement false, so is assumed. The pool is Fin n with ; the sequence has trials and is bestMistakesOn x ρ 0 T. The initial weights are arbitrary positive reals subject to the floor, so the lemma applies to any starting point of a run.
import Mathlib import Definitions.Def_WeightedMajority_Shifting_WML
namespace WeightedMajority.Shifting
theorem lemma_3_1 {n T : ℕ} (hn : 0 < n) {β γ : ℝ} (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)
(hfloor : ∀ i, β * γ / (n : ℝ) * totalWeight (w 0) ≤ w 0 i) :
(masterMistakes ρ lam : ℝ) ≤
(Real.log ((n : ℝ) / (β * γ)) + (bestMistakesOn x ρ 0 T : ℝ) * Real.log (1 / β)) /
Real.log (1 / uFactor β γ) ∧
∀ i, β * γ / (n : ℝ) * totalWeight (w T) ≤ w T i := by sorry
end WeightedMajority.Shifting
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.