Lemma 5.3 — absolute loss under the upper update bound
ProvedWeightedMajority.Continuous.lemma_5_3loss-boundonline-learningp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1weighted-majority
Under Lemma 5.2's assumptions, with positive final total weight, the weighted mean predictions have total absolute loss bounded by
This inequality applies to any nonnegative weight sequence satisfying the upper update bound, independently of how its update factors were selected.
Formalization Note Positive final weight selects the finite-valued case of the paper's bound; when final weight vanishes, its right side is interpreted as infinite.
Preamble
import Definitions.Def_WeightedMajority_Continuous_WMCRun
Formal statement
namespace WeightedMajority.Continuous
/-- Lemma 5.3, p. 236: the absolute loss bound under Lemma 5.2's conditions. -/
theorem lemma_5_3 {n t : ℕ} (beta : ℝ) (w : ℕ → Fin n → ℝ)
(x : Fin t → Fin n → ℝ) (rho : Fin t → ℝ)
(h : PotentialConditions beta w x rho) (hfin : 0 < WeightedMajority.Basic.totalWeight w t) :
masterLoss w x rho ≤
Real.log (WeightedMajority.Basic.totalWeight w 0 / WeightedMajority.Basic.totalWeight w t) / (1 - beta) := by sorry
end WeightedMajority.Continuous
Source
Littlestone and Warmuth, The Weighted Majority Algorithm, Information and Computation 108 (1994), p. 236, Lemma 5.3; https://doi.org/10.1006/inco.1994.1009
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.