Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 3.1 — WML makes at most (log(n/(βγ)) + m₀ log(1/β))/log(1/u) mistakes, and keeps the weight floor

Proved
WeightedMajority.Shifting.lemma_3_1

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

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

Let 0<β<10 < \beta < 10<β<1 and 0<γ<120 < \gamma < \tfrac120<γ<21​, and put u=1+β2+(1−β)γu = \frac{1+\beta}{2} + (1-\beta)\gammau=21+β​+(1−β)γ. Consider a pool of n≥1n \ge 1n≥1 algorithms and any finite sequence S\mathcal SS of trials with binary predictions and labels, and let m0m_0m0​ be the minimum, over the members of the pool, of the number of mistakes made on S\mathcal SS. Run WML with parameters β,γ\beta, \gammaβ,γ on S\mathcal SS, from positive initial weights wiinitw_i^{\mathrm{init}}wiinit​ such that every initial weight is at least βγ/n\beta\gamma/nβγ/n times the total initial weight:

wiinit≥βγn∑jwjinitfor every i.w_i^{\mathrm{init}} \ge \frac{\beta\gamma}{n}\sum_{j} w_j^{\mathrm{init}} \quad \text{for every } i .wiinit​≥nβγ​j∑​wjinit​for every i.

Then:

  1. the number mmm of mistakes made by WML on S\mathcal SS satisfies
m≤log⁡(n/(βγ))+m0log⁡(1/β)log⁡(1/u);m \le \frac{\log\big(n/(\beta\gamma)\big) + m_0 \log(1/\beta)}{\log(1/u)} ;m≤log(1/u)log(n/(βγ))+m0​log(1/β)​;
  1. the final weights satisfy the same floor: wifin≥βγn∑jwjfinw_i^{\mathrm{fin}} \ge \frac{\beta\gamma}{n}\sum_j w_j^{\mathrm{fin}}wifin​≥nβγ​∑j​wjfin​ for every iii.

The bound depends on the length of the sequence only through m0m_0m0​, 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 γ=0\gamma = 0γ=0 for the algorithm, but then the bound is log⁡(n/0)=+∞\log(n/0) = +\inftylog(n/0)=+∞ and says nothing; in Lean n/0=0n/0 = 0n/0=0 would make the literal statement false, so γ>0\gamma > 0γ>0 is assumed. The pool is Fin n with n>0n > 0n>0; the sequence has TTT trials and m0m_0m0​ 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.

Preamble
import Mathlib
import Definitions.Def_WeightedMajority_Shifting_WML
Formal statement
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
Source
Littlestone, Warmuth, The Weighted Majority Algorithm, Inform. and Comput. 108 (1994), pp. 223–224, Lemma 3.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