Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Appendix, p. 256 — a mistake of WMG multiplies the total weight by at most (1+β)/2

Proved
WeightedMajority.General.appendix_mistake_step

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 and consider a run of the algorithm WMG with parameter β\betaβ on a pool of nnn algorithms with predictions xk,i∈[0,1]x_{k,i} \in [0,1]xk,i​∈[0,1] and binary labels ρk\rho_kρk​, with weights wk,iw_{k,i}wk,i​ and total weights sk=∑iwk,is_k = \sum_i w_{k,i}sk​=∑i​wk,i​. If WMG makes a mistake in trial kkk, that is, its prediction λk\lambda_kλk​ differs from ρk\rho_kρk​, then the total weight after the update is at most a fraction (1+β)/2(1+\beta)/2(1+β)/2 of the total weight before it:

sk+1≤1+β2 sk.s_{k+1} \le \frac{1+\beta}{2}\, s_k .sk+1​≤21+β​sk​.

In the notation of the Appendix, with q0=∑iwk,i(1−xk,i)q_0 = \sum_i w_{k,i}(1 - x_{k,i})q0​=∑i​wk,i​(1−xk,i​) and q1=∑iwk,ixk,iq_1 = \sum_i w_{k,i} x_{k,i}q1​=∑i​wk,i​xk,i​, the total weight before the trial is q0+q1q_0 + q_1q0​+q1​ and the claim is that it is at most 1+β2(q0+q1)\frac{1+\beta}{2}(q_0+q_1)21+β​(q0​+q1​) afterwards.

This is the step on which the alternate proof of Theorem 5.1 in the Appendix rests.

Formalization Note The run is the relation IsWMGRun; the claim holds for every choice of tie-breaking, update flags and factors allowed by (5.1).

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

/-- Appendix, p. 256 (alternate proof of Theorem 5.1): in a trial in which WMG makes a mistake,
the total weight after the update is at most `(1 + β) / 2` times the total weight before it. -/
theorem appendix_mistake_step {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)
    (k : Fin T) (hmis : pred k ≠ ρ k) :
    WeightedMajority.Basic.totalWeight w (k.val + 1) ≤ (1 + β) / 2 * WeightedMajority.Basic.totalWeight w k.val := by sorry

end WeightedMajority.General
Source
Littlestone, Warmuth, The Weighted Majority Algorithm, Inform. and Comput. 108 (1994), p. 256, Appendix, alternate proof of 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