Theorem 6.1 — under the weak independence condition WMR has
ProvedWeightedMajority.Randomized.theorem_6_1Let the randomized master algorithm WMR run for trials on a sequence of instances with binary labels , using a pool of (possibly probabilistic) prediction algorithms whose predictions lie in . The parameter satisfies , the initial weights are positive, and in every trial each weight is multiplied by a factor satisfying (5.1),
WMR predicts , and is its number of mistakes. Let and be the total weights before the first and after the last trial, and assume almost surely. If the weak independence condition
holds, then
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 .
Formalization Note Both expectations are lower Lebesgue integrals with values in , so the right-hand side may be (as in the paper) and no integrability of is assumed; the logarithm is nonnegative because every factor is at most . The paper's bound is infinite when , where Lean's would give a false literal statement; the hypothesis almost surely excludes exactly that case. Trials are indexed from , 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.
import Mathlib import Definitions.Def_WeightedMajority_Randomized_WMRModel open MeasureTheory
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.