Proof of Theorem 11.5, p. 183 — exp-concave losses on the shrunken competitor set
ProvedModernOnlineLearning.Aggregating.restricted_prior_stepexp-concavityonline-learningp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1weighted-average
Let , , be convex, , and each be -exp-concave on . Put and . For every there is with , and for ,
Consequently,
This gives the loss comparison on the portion of the prior retained near a fixed competitor.
Formalization Note The hypotheses make the scaling and the printed division by well defined.
Preamble
import Mathlib import Definitions.Def_ModernOnlineLearning_Aggregating_ExpConcave import Definitions.Def_ModernOnlineLearning_Aggregating_ShrunkSet set_option autoImplicit false
Formal statement
namespace ModernOnlineLearning.Aggregating
/-- The two exponential inequalities in the proof of Theorem 11.5, p. 183. -/
theorem restricted_prior_step {d : ℕ} (hd : 0 < d) (T : ℕ) (hT : 0 < T)
(V : Set (EuclideanSpace ℝ (Fin d))) (hV : Convex ℝ V)
(u : EuclideanSpace ℝ (Fin d)) (hu : u ∈ V)
(α : ℝ) (hα : 0 < α)
(ℓ : ℕ → EuclideanSpace ℝ (Fin d) → ℝ)
(hℓ : ∀ t ∈ Finset.Icc 1 T, ExpConcaveOn V α (ℓ t)) :
∀ x ∈ shrunkSet V u T, ∃ w ∈ V,
x = (((T : ℝ) / (d : ℝ)) / ((T : ℝ) / (d : ℝ) + 1)) • u +
(1 / ((T : ℝ) / (d : ℝ) + 1)) • w ∧
(∀ t ∈ Finset.Icc 1 T,
Real.exp (-α * ℓ t x) ≥
(((T : ℝ) / (d : ℝ)) / ((T : ℝ) / (d : ℝ) + 1)) *
Real.exp (-α * ℓ t u) +
(1 / ((T : ℝ) / (d : ℝ) + 1)) * Real.exp (-α * ℓ t w) ∧
(((T : ℝ) / (d : ℝ)) / ((T : ℝ) / (d : ℝ) + 1)) *
Real.exp (-α * ℓ t u) +
(1 / ((T : ℝ) / (d : ℝ) + 1)) * Real.exp (-α * ℓ t w) ≥
(((T : ℝ) / (d : ℝ)) / ((T : ℝ) / (d : ℝ) + 1)) *
Real.exp (-α * ℓ t u)) ∧
Real.exp (-α * ∑ t ∈ Finset.Icc 1 T, ℓ t x) ≥
((((T : ℝ) / (d : ℝ)) / ((T : ℝ) / (d : ℝ) + 1)) ^ T) *
Real.exp (-α * ∑ t ∈ Finset.Icc 1 T, ℓ t u) ∧
Real.exp (-α * ∑ t ∈ Finset.Icc 1 T, ℓ t x) ≥
Real.exp (-α * ∑ t ∈ Finset.Icc 1 T, ℓ t u) / Real.exp (d : ℝ) := by sorry
end ModernOnlineLearning.Aggregating
Source
Orabona, arXiv:1912.13213v10, proof of Theorem 11.5, p. 183, first two display chains
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.