Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 4.1(3) — WMI₂ makes at most inf_i (log(Ŵ(1)/W(i)) + m_i log(1/β) + log 2)/log(1/u) mistakes

Proved
WeightedMajority.InfinitePool.theorem_4_1_part_3

by mikedeng1 · Oct 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

mistake-boundonline-learningp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1prediction-with-expert-adviceweighted-majority

Let 0≤β<10 \le \beta < 10≤β<1 and u=(1+β)/2u = (1+\beta)/2u=(1+β)/2. Let W,W^W, \hat WW,W^ be real functions on the positive integers with W(i)>0W(i) > 0W(i)>0 for all iii, ∑iW(i)<∞\sum_i W(i) < \infty∑i​W(i)<∞, W^(i)≥∑j≥iW(j)\hat W(i) \ge \sum_{j \ge i} W(j)W^(i)≥∑j≥i​W(j) for all iii, and lim⁡i→∞W^(i)=0\lim_{i\to\infty} \hat W(i) = 0limi→∞​W^(i)=0. Let xt(i),ρtx_t(i), \rho_txt​(i),ρt​ (t=0,…,T−1t = 0, \dots, T-1t=0,…,T−1) be any finite sequence of binary predictions of a countably infinite pool A1,A2,…A_1, A_2, \dotsA1​,A2​,… and binary labels, on which AiA_iAi​ makes at most mim_imi​ mistakes, for every i≥1i \ge 1i≥1. Let mmm be the total number of mistakes of any run of WMI2\mathrm{WMI}_2WMI2​ with parameter β\betaβ on this sequence.

  1. If 0<β<10 < \beta < 10<β<1, then
m≤inf⁡i≥1log⁡(W^(1)/W(i))+milog⁡(1/β)+log⁡2log⁡(1/u).m \le \inf_{i \ge 1} \frac{\log\bigl(\hat W(1)/W(i)\bigr) + m_i \log(1/\beta) + \log 2}{\log(1/u)}.m≤i≥1inf​log(1/u)log(W^(1)/W(i))+mi​log(1/β)+log2​.
  1. If β=0\beta = 0β=0 and mi=0m_i = 0mi​=0 for some iii, then m≤1+log⁡2(W^(1)/W(i))m \le 1 + \log_2\bigl(\hat W(1)/W(i)\bigr)m≤1+log2​(W^(1)/W(i)).

This is the main result of Section 4: on an infinite pool, with only a finite active subpool maintained at any time, WMI2\mathrm{WMI}_2WMI2​ achieves essentially the bound that the (infeasible) Weighted Majority Algorithm on all infinitely many weights would give, up to the additive log⁡2\log 2log2 in the numerator. Choosing WWW and W^\hat WW^ trades the mistake bound against the growth of the active pool.

Formalization Note. The infimum over iii is stated as the bound for every iii, which is equivalent. In case 1 the logarithms appear in a ratio, so their base is irrelevant (as the paper notes); the natural logarithm is used. Case 2 uses the base-2 logarithm, as printed. All logarithms are of positive numbers under the hypotheses (W^(1)≥W(i)>0\hat W(1) \ge W(i) > 0W^(1)≥W(i)>0, 0<u<10 < u < 10<u<1). The paper's computability requirement on W,W^W, \hat WW,W^ is dropped: the result does not depend on it, so the statement is a generalization.

Preamble
import Mathlib
import Definitions.Def_WeightedMajority_InfinitePool_IsWMI2Run
Formal statement
namespace WeightedMajority.InfinitePool

/-- Theorem 4.1, part 3 (Littlestone–Warmuth 1994, p. 227). If `0 < β < 1`, the total number
`m` of mistakes of WMI₂ is at most `(log(Ŵ(1)/W(i)) + m_i log(1/β) + log 2) / log(1/u)` for every
`i` (equivalently, at most the infimum over `i ≥ 1`). If `β = 0` and `m_i = 0` for some `i`, then
`m ≤ 1 + log₂(Ŵ(1)/W(i))`. -/
theorem theorem_4_1_part_3
    (β : ℝ) (hβ0 : 0 ≤ β) (hβ1 : β < 1)
    (W What : ℕ+ → ℝ) (hW_pos : ∀ i, 0 < W i) (hW_sum : Summable W)
    (hWhat_tail : ∀ i, (∑' j : ℕ+, if i ≤ j then W j else 0) ≤ What i)
    (hWhat_lim : Filter.Tendsto What Filter.atTop (nhds 0))
    {T : ℕ} (x : Fin T → ℕ+ → Bool) (label : Fin T → Bool)
    (mi : ℕ+ → ℕ)
    (hmi : ∀ i, (Finset.univ.filter (fun t : Fin T => x t i ≠ label t)).card ≤ mi i)
    (prediction : Fin T → Bool) (w : ℕ → ℕ+ → ℝ) (l : ℕ → ℕ)
    (hrun : IsWMI2Run β W What x label prediction w l) :
    (0 < β → ∀ i : ℕ+,
      (mistakesBefore prediction label T : ℝ) ≤
        (Real.log (What 1 / W i) + (mi i : ℝ) * Real.log (1 / β) + Real.log 2) /
          Real.log (1 / u β)) ∧
    (β = 0 → ∀ i : ℕ+, mi i = 0 →
      (mistakesBefore prediction label T : ℝ) ≤ 1 + Real.logb 2 (What 1 / W i)) := by sorry

end WeightedMajority.InfinitePool
Source
Littlestone, Warmuth, The Weighted Majority Algorithm, Inform. and Comput. 108 (1994), p. 227, Theorem 4.1, part 3
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me