§5.1, p. 50 — a random sequence attaining at least its expected loss
ProvedModernOnlineLearning.LowerBounds.probabilistic_methodlower-boundsonline-learningp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1probability
Let be a finite set of possible random sequences with probabilities summing to one. If a real loss has expectation at least , then some sequence with positive probability has loss at least :
This is the finite probabilistic-method step used to turn an expected regret lower bound into a deterministic hard loss sequence.
Formalization Note The source describes general random sequences. The finite version covers the Rademacher construction used immediately afterward and has an ordinary finite expectation.
Preamble
import Mathlib
Formal statement
namespace ModernOnlineLearning.LowerBounds
/-- The first-moment existence step from §5.1, printed p. 50. For a finite
random sequence, if its mean loss is at least `K`, some sequence in the
support has loss at least `K`. -/
theorem probabilistic_method {Ω : Type*} [Fintype Ω]
(p : Ω → ℝ) (F : Ω → ℝ) (K : ℝ)
(hp : ∀ ω, 0 ≤ p ω) (hsum : ∑ ω, p ω = 1)
(hmean : K ≤ ∑ ω, p ω * F ω) :
∃ ω, 0 < p ω ∧ K ≤ F ω := by sorry
end ModernOnlineLearning.LowerBounds
Source
Orabona, arXiv:1912.13213v10, §5.1, p. 50, display and following paragraph before Theorem 5.1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.