wm_mistake_bound_log
theoremverifiedformalizationimported Lean
Logarithmic mistake bound. Let $n \ge 2$ be an integer and let $\beta \in (0,1)$. Suppose $M^*$ and $M_{\mathrm{WM}}$ are nonnegative integers satisfying \[ \beta^{M^*} \;\le\; n \cdot \left(\frac{1+\beta}{2}\right)^{M_{\mathrm{WM}}}. \] Then \[ M_{\mathrm{WM}} \cdot \log\!\frac{2}{1+\beta} \;\le\; \log n \;+\; M^* \cdot \log\frac{1}{\beta}. \]
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in open Finset BigOperators Real in theorem wm_mistake_bound_log (n : ℕ) (hn : 1 < n) (β : ℝ) (hβ0 : 0 < β) (_hβ1 : β < 1) (M_star M_WM : ℕ) (h : β ^ M_star ≤ (n : ℝ) * ((1 + β) / 2) ^ M_WM) : (M_WM : ℝ) * Real.log (2 / (1 + β)) ≤ Real.log (n : ℝ) + (M_star : ℝ) * Real.log (1 / β)
- Formalizes
- Logarithmic mistake bound, as formalized in TCSlib (`wm_mistake_bound_log`)
- Lean proof
- By Arhaan Aggarwal, from github.com/Shilun-Allan-Li/tcslib at
c8a02591b1e5(Copyright (c) 2026 Arhaan Aggarwal. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.25.0.wm_mistake_bound_log← wm_mistake_bound_log (TCSlib/LearningTheory/MistakeBounds/WeightedMajority.lean:119): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
set_option relaxedAutoImplicit false inset_option autoImplicit false inopen Finset BigOperators Real in/-- The Weighted Majority mistake bound in logarithmic form: for `n > 1` experts, `0 < β < 1`, and under the potential hypothesis `h : β^{M*} ≤ n · ((1+β)/2)^{M_WM}`, `M_WM · log(2/(1+β)) ≤ log n + M* · log(1/β)`; equivalently `M_WM ≤ (log n + M* · log(1/β)) / log(2/(1+β))`. [MRT18, Thm 8.3]; [LW94, §2]. Deviation: the source derives the potential inequality from the algorithm; here it is the hypothesis `h`, and the theorem takes logarithms and rearranges (since `log((1+β)/2) < 0` the inequality is written with `log(2/(1+β)) > 0`). The hypothesis `1 < n` is stronger than needed: `0 < n` suffices. -/theorem wm_mistake_bound_log (n : ℕ) (hn : 1 < n) (β : ℝ) (hβ0 : 0 < β) (_hβ1 : β < 1) (M_star M_WM : ℕ) (h : β ^ M_star ≤ (n : ℝ) * ((1 + β) / 2) ^ M_WM) : (M_WM : ℝ) * Real.log (2 / (1 + β)) ≤ Real.log (n : ℝ) + (M_star : ℝ) * Real.log (1 / β) := by have := Real.log_le_log ?_ h; · rw [ Real.log_mul ( by positivity ) ( by positivity ), Real.log_pow, Real.log_pow ] at this; rw [ show ( 2 : ℝ ) / ( 1 + β ) = ( ( 1 + β ) / 2 ) ⁻¹ by rw [ inv_div ], Real.log_inv ] ; norm_num at * ; linarith; · positivity