Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 3.1 — on any partition into consecutive segments, WML makes at most Σᵢ min(lᵢ, (log(n/(βγ)) + mᵢ log(1/β))/log(1/u)) mistakes

Proved
WeightedMajority.Shifting.theorem_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−β)γ. Let S\mathcal SS be a finite sequence of TTT trials with binary predictions of a pool of n≥1n \ge 1n≥1 algorithms and binary labels, and let S1,…,Sk\mathcal S_1, \dots, \mathcal S_kS1​,…,Sk​ be a partition of S\mathcal SS into kkk consecutive segments: there are indices 0=b0≤b1≤⋯≤bk=T0 = b_0 \le b_1 \le \dots \le b_k = T0=b0​≤b1​≤⋯≤bk​=T and Si\mathcal S_iSi​ consists of the trials ttt with bi−1≤t<bib_{i-1} \le t < b_ibi−1​≤t<bi​. Let li=bi−bi−1l_i = b_i - b_{i-1}li​=bi​−bi−1​ be the number of trials of Si\mathcal S_iSi​, and let mim_imi​ be the minimum, over the members of the pool, of the number of mistakes made on Si\mathcal S_iSi​; the best member may be a different one for each segment.

Run WML with parameters β,γ\beta, \gammaβ,γ on S\mathcal SS from positive initial weights, each at least βγ/n\beta\gamma/nβγ/n times the total initial weight. Then the number mmm of mistakes of WML on S\mathcal SS satisfies

m≤∑i=1kmin⁡(li, log⁡(n/(βγ))+milog⁡(1/β)log⁡(1/u)).m \le \sum_{i=1}^{k} \min\left( l_i,\ \frac{\log\big(n/(\beta\gamma)\big) + m_i \log(1/\beta)}{\log(1/u)} \right).m≤i=1∑k​min(li​, log(1/u)log(n/(βγ))+mi​log(1/β)​).

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 nnn plus a constant multiple of the mistakes of that segment's best member.

Formalization Note The paper's "partitioning of S\mathcal SS into kkk 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 sss segments"); for interleaved subsequences the inequality fails. Segments may be empty (then bi−1=bib_{i-1} = b_ibi−1​=bi​ and the segment contributes 000); k=0k = 0k=0 forces T=0T = 0T=0. The boundaries are b : Fin (k+1) → ℕ, monotone, with b 0 = 0 and b (Fin.last k) = T, and segment iii (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, γ>0\gamma > 0γ>0 is assumed because the bound is +∞+\infty+∞ at γ=0\gamma = 0γ=0.

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