Lemma 5.1 — existence of an update factor
ProvedWeightedMajority.Continuous.lemma_5_1convexityonline-learningp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1weighted-majority
For real numbers and ,
This guarantees that the lower endpoint of the permitted WMC update-factor interval never exceeds its upper endpoint when and is an absolute prediction error.
Formalization Note Real exponentiation uses , as stipulated by the paper.
Preamble
import Mathlib
Formal statement
namespace WeightedMajority.Continuous
/-- Lemma 5.1, p. 233: the factor interval in (5.1) is nonempty. -/
theorem lemma_5_1 (beta r : ℝ) (hbeta : 0 ≤ beta)
(hr0 : 0 ≤ r) (hr1 : r ≤ 1) :
beta ^ r ≤ 1 + r * (beta - 1) := by sorry
end WeightedMajority.Continuous
Source
Littlestone and Warmuth, The Weighted Majority Algorithm, Information and Computation 108 (1994), p. 233, Lemma 5.1; https://doi.org/10.1006/inco.1994.1009
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.