Theorem 11.5, p. 183 — uniform-prior weighted average regret on exp-concave losses
ProvedModernOnlineLearning.Aggregating.theorem_11_5Let be convex, closed, bounded, and full-dimensional. Let , and suppose the losses are -exp-concave on . The Weighted Average Algorithm starts with the uniform distribution on , sets , and predicts with the exponential-weighted mean of based on losses before round . For every ,
The bound compares one deterministic sequence of weighted predictions with every fixed feasible competitor, with explicit dependence on dimension, horizon, and exp-concavity.
Formalization Note The theorem uses the published EWOO weighted-mean definition, which equals WAA for the uniform prior and . Rounds start at one. The hypotheses , positive volume, almost-everywhere measurability on , and integrability of the exponential weights and their vector moments make the divisions and Bochner integrals represent the source's quantities.
Retired 2026-10-27: a Lean-vs-paper fidelity audit found this statement weaker than, or narrower than, the cited result. A corrected statement will be resubmitted.
import Mathlib import Definitions.Def_LogRegretOCO_EWOO_ewooPoint import Definitions.Def_ModernOnlineLearning_Aggregating_ExpConcave set_option autoImplicit false open MeasureTheory
namespace ModernOnlineLearning.Aggregating
/-- Theorem 11.5, p. 183: uniform-prior WAA with `1 / λ_t = α`.
The published EWOO point is exactly the uniform-prior WAA weighted mean. -/
theorem theorem_11_5 {d : ℕ} (hd : 0 < d) (T : ℕ) (hT : 0 < T)
(V : Set (EuclideanSpace ℝ (Fin d)))
(hconv : Convex ℝ V) (hclosed : IsClosed V) (hbounded : Bornology.IsBounded V)
(hvol_pos : 0 < volume V)
(α : ℝ) (hα : 0 < α)
(ℓ : ℕ → EuclideanSpace ℝ (Fin d) → ℝ)
(hexp : ∀ t ∈ Finset.Icc 1 T, ExpConcaveOn V α (ℓ t))
(hmeas : ∀ t ∈ Finset.Icc 1 T, AEMeasurable (ℓ t) (volume.restrict V))
(hint_weight : ∀ t ∈ Finset.Icc 1 T,
IntegrableOn (LogRegretOCO.EWOO.ewooWeight α ℓ t) V)
(hint_point : ∀ t ∈ Finset.Icc 1 T,
IntegrableOn (fun x => LogRegretOCO.EWOO.ewooWeight α ℓ t x • x) V) :
∀ u ∈ V,
(∑ t ∈ Finset.Icc 1 T,
(ℓ t (LogRegretOCO.EWOO.ewooPoint V α ℓ t) - ℓ t u)) ≤
(d : ℝ) / α * (1 + Real.log ((T : ℝ) / (d : ℝ) + 1)) := by sorry
end ModernOnlineLearning.Aggregating
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.