Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

§5, p. 235 — the sum of log(1 − (1−β)|γ − ρ|) over update trials is at most m log(1/2 + β/2)

Proved
WeightedMajority.General.log_display

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 WMG with parameter β\betaβ on a pool with predictions xk,i∈[0,1]x_{k,i} \in [0,1]xk,i​∈[0,1] and binary labels ρk\rho_kρk​, with weighted averages γk\gamma_kγk​ and mmm mistakes. Suppose that it is not the case that β=0\beta = 0β=0 and ∣γk−ρk∣=1|\gamma_k - \rho_k| = 1∣γk​−ρk​∣=1 for some update trial kkk. Then, writing UUU for the set of update trials and M⊆UM \subseteq UM⊆U for the set of trials in which WMG makes a mistake,

∑k∈Uln⁡(1−(1−β)∣γk−ρk∣)  ≤  ∑k∈Mln⁡(1−(1−β)∣γk−ρk∣)  ≤  mln⁡(12+12β).\sum_{k \in U} \ln\bigl(1 - (1-\beta)|\gamma_k - \rho_k|\bigr) \;\le\; \sum_{k \in M} \ln\bigl(1 - (1-\beta)|\gamma_k - \rho_k|\bigr) \;\le\; m \ln\Bigl(\frac12 + \frac12\beta\Bigr).k∈U∑​ln(1−(1−β)∣γk​−ρk​∣)≤k∈M∑​ln(1−(1−β)∣γk​−ρk​∣)≤mln(21​+21​β).

This display, combined with Lemma 5.2 of the paper (ln⁡(wfin/winit)\ln(w_{\mathrm{fin}}/w_{\mathrm{init}})ln(wfin​/winit​) is at most the left-hand sum), gives Theorem 5.1.

Formalization Note The paper writes "log" with the base left open; the inequality does not depend on the base, and the natural logarithm Real.log is used. The excluded case is the one in which a factor 1−(1−β)∣γk−ρk∣1 - (1-\beta)|\gamma_k - \rho_k|1−(1−β)∣γk​−ρk​∣ vanishes, where the paper's logarithm is −∞-\infty−∞ and Lean's Real.log 0 = 0 would make the second inequality false.

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

/-- §5, p. 235 (proof of Theorem 5.1): outside the case `β = 0` and `|γ - ρ| = 1` in some update
trial, the sum over the update trials of `log (1 - (1 - β) |γ - ρ|)` is at most the same sum over
the mistake trials, which is at most `m log (1/2 + β/2)`. -/
theorem log_display {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)
    (hnot : ¬ (β = 0 ∧ ∃ k, upd k = true ∧ |gamma x w k - ρ k| = 1)) :
    (∑ k ∈ Finset.univ.filter (fun k => upd k = true),
        Real.log (1 - (1 - β) * |gamma x w k - ρ k|)) ≤
      (∑ k ∈ Finset.univ.filter (fun k => upd k = true ∧ pred k ≠ ρ k),
        Real.log (1 - (1 - β) * |gamma x w k - ρ k|)) ∧
    (∑ k ∈ Finset.univ.filter (fun k => upd k = true ∧ pred k ≠ ρ k),
        Real.log (1 - (1 - β) * |gamma x w k - ρ k|)) ≤
      (mistakeCount pred ρ : ℝ) * Real.log (1 / 2 + 1 / 2 * β) := by sorry

end WeightedMajority.General
Source
Littlestone, Warmuth, The Weighted Majority Algorithm, Inform. and Comput. 108 (1994), p. 235, Section 5, proof of Theorem 5.1 (unnumbered display)
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