Lemma 5.2 — logarithmic potential bound for continuous predictions
ProvedWeightedMajority.Continuous.lemma_5_2online-learningp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1potential-methodweighted-majority
Consider a finite, nonempty pool with positive initial weights, nonnegative weights thereafter, , and expert predictions and labels in . At each trial , suppose every weight obeys the upper update bound . Let be the weighted mean prediction and let and be the initial and final total weights.
If and on some trial, then . When ,
This is the paper's potential estimate for the master prediction; it uses only the upper update bound, so it also applies to WMC runs.
Formalization Note The paper treats a zero final weight as a logarithmic bound. Lean's real logarithm of zero returns zero, so the finite logarithmic clause explicitly assumes .
Preamble
import Definitions.Def_WeightedMajority_Continuous_WMCRun
Formal statement
namespace WeightedMajority.Continuous
/-- Lemma 5.2, p. 234: a unit master loss at beta zero exhausts the weights;
otherwise the logarithmic potential is bounded by the trialwise factors. -/
theorem lemma_5_2 {n t : ℕ} (beta : ℝ) (w : ℕ → Fin n → ℝ)
(x : Fin t → Fin n → ℝ) (rho : Fin t → ℝ)
(h : PotentialConditions beta w x rho) :
(beta = 0 → (∃ j : Fin t, |meanPrediction w x j - rho j| = 1) →
WeightedMajority.Basic.totalWeight w t = 0) ∧
(0 < WeightedMajority.Basic.totalWeight w t →
Real.log (WeightedMajority.Basic.totalWeight w t / WeightedMajority.Basic.totalWeight w 0) ≤
∑ j : Fin t,
Real.log (1 - (1 - beta) * |meanPrediction w x j - rho j|)) := by sorry
end WeightedMajority.Continuous
Source
Littlestone and Warmuth, The Weighted Majority Algorithm, Information and Computation 108 (1994), p. 234, Lemma 5.2; https://doi.org/10.1006/inco.1994.1009
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.