Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 6.1 — under the weak independence condition WMR has E(m)≤E(ln⁡(winit/wfin))/(1−β)\mathbf E(m)\le\mathbf E(\ln(w_{\mathrm{init}}/w_{\mathrm{fin}}))/(1-\beta)E(m)≤E(ln(winit​/wfin​))/(1−β)

Proved
WeightedMajority.Randomized.theorem_6_1

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

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

Let the randomized master algorithm WMR run for ttt trials on a sequence of instances with binary labels ρ(j)∈{0,1}\rho^{(j)} \in \{0,1\}ρ(j)∈{0,1}, using a pool of nnn (possibly probabilistic) prediction algorithms whose predictions xi(j)x_i^{(j)}xi(j)​ lie in [0,1][0,1][0,1]. The parameter satisfies 0≤β<10 \le \beta < 10≤β<1, the initial weights are positive, and in every trial each weight is multiplied by a factor satisfying (5.1),

β∣xi(j)−ρ(j)∣≤F≤1−(1−β) ∣xi(j)−ρ(j)∣.\beta^{|x_i^{(j)}-\rho^{(j)}|} \le F \le 1-(1-\beta)\,|x_i^{(j)}-\rho^{(j)}|.β∣xi(j)​−ρ(j)∣≤F≤1−(1−β)∣xi(j)​−ρ(j)∣.

WMR predicts λ(j)∈{0,1}\lambda^{(j)} \in \{0,1\}λ(j)∈{0,1}, and m=∑j=1t∣λ(j)−ρ(j)∣m = \sum_{j=1}^t |\lambda^{(j)}-\rho^{(j)}|m=∑j=1t​∣λ(j)−ρ(j)∣ is its number of mistakes. Let winitw_{\mathrm{init}}winit​ and wfinw_{\mathrm{fin}}wfin​ be the total weights before the first and after the last trial, and assume wfin>0w_{\mathrm{fin}} > 0wfin​>0 almost surely. If the weak independence condition

E(λ(j) ∣ (x(1),ρ(1)),…,(x(j),ρ(j)))=γ(j)a.s.,j=1,…,t,\mathbf E\big(\lambda^{(j)} \,\big|\, (x^{(1)},\rho^{(1)}),\dots,(x^{(j)},\rho^{(j)})\big) = \gamma^{(j)} \quad\text{a.s.}, \qquad j = 1,\dots,t,E(λ(j)​(x(1),ρ(1)),…,(x(j),ρ(j)))=γ(j)a.s.,j=1,…,t,

holds, then

E(m)≤E(ln⁡(winit/wfin))1−β.\mathbf E(m) \le \frac{\mathbf E\big(\ln(w_{\mathrm{init}}/w_{\mathrm{fin}})\big)}{1-\beta}.E(m)≤1−βE(ln(winit​/wfin​))​.

The bound transfers the loss bound of the deterministic weighted-average algorithm WMC to a master whose predictions are binary, the improvement over the deterministic binary master WMG coming from the randomization. When predictions and labels are deterministic it reads E(m)≤ln⁡(winit/wfin)/(1−β)\mathbf E(m) \le \ln(w_{\mathrm{init}}/w_{\mathrm{fin}})/(1-\beta)E(m)≤ln(winit​/wfin​)/(1−β).

Formalization Note Both expectations are lower Lebesgue integrals with values in [0,∞][0,\infty][0,∞], so the right-hand side may be +∞+\infty+∞ (as in the paper) and no integrability of ln⁡(winit/wfin)\ln(w_{\mathrm{init}}/w_{\mathrm{fin}})ln(winit​/wfin​) is assumed; the logarithm is nonnegative because every factor is at most 111. The paper's bound is infinite when wfin=0w_{\mathrm{fin}} = 0wfin​=0, where Lean's ln⁡0=0\ln 0 = 0ln0=0 would give a false literal statement; the hypothesis wfin>0w_{\mathrm{fin}} > 0wfin​>0 almost surely excludes exactly that case. Trials are indexed from 000, the initial weights are deterministic, and the update factor is a measurable function of the member's prediction and the label that may depend on the trial and the member.

Preamble
import Mathlib
import Definitions.Def_WeightedMajority_Randomized_WMRModel

open MeasureTheory
Formal statement
namespace WeightedMajority.Randomized

/-- Theorem 6.1 (p. 240): under the weak independence condition, the expected number of
mistakes of WMR is at most `E(ln(w_init/w_fin))/(1 − β)`. Expectations are lower Lebesgue
integrals, so the right-hand side may be `+∞`; `w_fin > 0` almost surely excludes the paper's
infinite-bound case. -/
theorem theorem_6_1 {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω)
    [IsProbabilityMeasure P] {n t : ℕ} (β : ℝ) (w1 : Fin n → ℝ)
    (F : ℕ → Fin n → ℝ → ℝ → ℝ) (x : ℕ → Fin n → Ω → ℝ) (ρ lam : ℕ → Ω → ℝ)
    (hM : IsWMRModel t β w1 F x ρ lam)
    (hweak : WeakIndependence P t w1 F x ρ lam)
    (hfin : ∀ᵐ ω ∂P, 0 < totalWeight w1 F x ρ t ω) :
    ∫⁻ ω, ENNReal.ofReal (mistakes t lam ρ ω) ∂P ≤
      (∫⁻ ω, ENNReal.ofReal
          (Real.log (totalWeight w1 F x ρ 0 ω / totalWeight w1 F x ρ t ω)) ∂P)
        / ENNReal.ofReal (1 - β) := by sorry

end WeightedMajority.Randomized
Source
Littlestone, Warmuth, The Weighted Majority Algorithm, Inform. and Comput. 108 (1994), p. 240, Theorem 6.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