Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 5.1 — WMG makes at most log(w_init/w_fin)/log(2/(1+β)) mistakes

Proved
WeightedMajority.General.theorem_5_1

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

mistake-boundonline-learningp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1weighted-majority

Let 0≤β<10 \le \beta < 10≤β<1. Run the master algorithm WMG with parameter β\betaβ on a pool of nnn prediction algorithms, whose predictions xk,ix_{k,i}xk,i​ lie in [0,1][0,1][0,1], over any finite sequence of trials with binary labels ρk∈{0,1}\rho_k \in \{0,1\}ρk​∈{0,1}; WMG may update in every trial or only in the trials in which it makes a mistake, may break ties at γk=1/2\gamma_k = 1/2γk​=1/2 either way, and may use any update factors allowed by (5.1). Let winitw_{\mathrm{init}}winit​ and wfinw_{\mathrm{fin}}wfin​ be the total initial and final weights of the pool, and let mmm be the number of mistakes of WMG. If wfin>0w_{\mathrm{fin}} > 0wfin​>0, then

m≤ln⁡(winit/wfin)ln⁡(2/(1+β)).m \le \frac{\ln(w_{\mathrm{init}}/w_{\mathrm{fin}})}{\ln\bigl(2/(1+\beta)\bigr)} .m≤ln(2/(1+β))ln(winit​/wfin​)​.

This is the mistake bound of Theorem 2.1 for the binary algorithm WM, extended to pools whose members predict numbers in [0,1][0,1][0,1]. With equal initial weights it yields Corollary 5.1: the number of mistakes is at most (log⁡n+milog⁡(1/β))/log⁡(2/(1+β))(\log n + m_i \log(1/\beta))/\log(2/(1+\beta))(logn+mi​log(1/β))/log(2/(1+β)) for every pool member iii with total absolute loss mim_imi​.

Formalization Note The paper writes the bound as a ratio of logarithms with the base omitted; the ratio does not depend on the base, and Real.log is used. When wfin=0w_{\mathrm{fin}} = 0wfin​=0 (possible only if β=0\beta = 0β=0) the paper's bound is +∞+\infty+∞, and Lean's Real.log and division conventions would give a false literal statement; this case is excluded by the hypothesis wfin>0w_{\mathrm{fin}} > 0wfin​>0. The run is the relation IsWMGRun, so the bound is asserted for every tie-breaking, every update flag that is set on all mistake trials, and every factor in (5.1).

Preamble
import Mathlib
import Definitions.Def_WeightedMajority_General_WMGRun
Formal statement
namespace WeightedMajority.General

/-- Theorem 5.1 (pp. 234–235): for every run of WMG with `0 ≤ β < 1` on a sequence of `T` trials
with binary labels and pool predictions in `[0, 1]` (updating in every trial, only in mistake
trials, or in any set of trials containing the mistake trials), the number `m` of mistakes
satisfies `m ≤ log (w_init / w_fin) / log (2 / (1 + β))`, provided `w_fin > 0`
(for `w_fin = 0` the paper's bound is `+∞`). -/
theorem theorem_5_1 {n T : ℕ} {β : ℝ} {x : Fin T → Fin n → ℝ} {ρ : Fin T → ℝ}
    {w : ℕ → Fin n → ℝ} {pred : Fin T → ℝ} {upd : Fin T → Bool} {F : Fin T → Fin n → ℝ}
    (hβ0 : 0 ≤ β) (hβ1 : β < 1) (hrun : IsWMGRun β x ρ w pred upd F)
    (hfin : 0 < WeightedMajority.Basic.totalWeight w T) :
    (mistakeCount pred ρ : ℝ) ≤
      Real.log (WeightedMajority.Basic.totalWeight w 0 / WeightedMajority.Basic.totalWeight w T) / Real.log (2 / (1 + β)) := by sorry

end WeightedMajority.General
Source
Littlestone, Warmuth, The Weighted Majority Algorithm, Inform. and Comput. 108 (1994), pp. 234–235, Theorem 5.1
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