Theorem 3.1 — on any partition into consecutive segments, WML makes at most Σᵢ min(lᵢ, (log(n/(βγ)) + mᵢ log(1/β))/log(1/u)) mistakes
ProvedWeightedMajority.Shifting.theorem_3_1Let and , and put . Let be a finite sequence of trials with binary predictions of a pool of algorithms and binary labels, and let be a partition of into consecutive segments: there are indices and consists of the trials with . Let be the number of trials of , and let be the minimum, over the members of the pool, of the number of mistakes made on ; the best member may be a different one for each segment.
Run WML with parameters on from positive initial weights, each at least times the total initial weight. Then the number of mistakes of WML on satisfies
WML does not know the segments. The theorem says that it tracks a target that shifts from one pool member to another, paying for each segment a logarithmic cost in plus a constant multiple of the mistakes of that segment's best member.
Formalization Note The paper's "partitioning of into subsequences" is read as a partition into consecutive segments, as in the paper's own description of the scenario (Section 1, p. 217: "the original sequence is partitioned into segments"); for interleaved subsequences the inequality fails. Segments may be empty (then and the segment contributes ); forces . The boundaries are b : Fin (k+1) → ℕ, monotone, with b 0 = 0 and b (Fin.last k) = T, and segment (i : Fin k) runs from b i.castSucc to b i.succ. The natural logarithm is used (the base cancels). As in Lemma 3.1, is assumed because the bound is at .
import Mathlib import Definitions.Def_WeightedMajority_Shifting_WML
namespace WeightedMajority.Shifting
theorem theorem_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)
(k : ℕ) (b : Fin (k + 1) → ℕ) (hb_mono : Monotone b) (hb0 : b 0 = 0)
(hbk : b (Fin.last k) = T) :
(masterMistakes ρ lam : ℝ) ≤
∑ i : Fin k, min ((b i.succ - b i.castSucc : ℕ) : ℝ)
((Real.log ((n : ℝ) / (β * γ)) +
(bestMistakesOn x ρ (b i.castSucc) (b i.succ) : ℝ) * Real.log (1 / β)) /
Real.log (1 / uFactor β γ)) := by sorry
end WeightedMajority.Shifting
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.