§5, p. 235 — the sum of log(1 − (1−β)|γ − ρ|) over update trials is at most m log(1/2 + β/2)
ProvedWeightedMajority.General.log_displayLet and consider a run of WMG with parameter on a pool with predictions and binary labels , with weighted averages and mistakes. Suppose that it is not the case that and for some update trial . Then, writing for the set of update trials and for the set of trials in which WMG makes a mistake,
This display, combined with Lemma 5.2 of the paper ( 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 vanishes, where the paper's logarithm is and Lean's Real.log 0 = 0 would make the second inequality false.
import Mathlib import Definitions.Def_WeightedMajority_General_WMGRun
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.