Product body for the dimension-dependent lower bound
DefinitionAltRegret_Supplement_productBodyalgorithmic-game-theoryonline-convex-optimizationonline-learningp2o-gran-per-chapterp2o-plan-paperp2o-v1regret
For , set . The body used in Theorem 10 is
It is compact, convex, full-dimensional, and contained in . The associated exact lower-bound parameters are and .
This is the specific body on which Theorem 10 establishes the dimension dependence.
Definition code
import Mathlib
import Definitions.Def_AltRegret_Supplement_ContinuousAAHedgeRun
namespace AltRegret.Supplement
/-- Coordinate `i`, extended by zero outside `Fin d`. -/
def coord {d : ℕ} (x : Point d) (i : ℕ) : ℝ :=
if h : i < d then x ⟨i, h⟩ else 0
/-- The radius `r = 1 / √d` in §4.2. -/
noncomputable def blockRadius (d : ℕ) : ℝ := 1 / Real.sqrt d
/-- The product of `⌊d/2⌋` radius-`1/√d` planar balls and, for odd `d`, one interval. -/
noncomputable def productBody (d : ℕ) : Set (Point d) :=
{x | (∀ j : Fin (d / 2),
coord x (2 * j.1) ^ 2 + coord x (2 * j.1 + 1) ^ 2 ≤ blockRadius d ^ 2) ∧
(d % 2 = 1 → |coord x (d - 1)| ≤ blockRadius d)}
/-- `m = min{⌊d/2⌋, ⌊T/16⌋}` from Theorem 10. -/
def lowerBlockCount (d T : ℕ) : ℕ := min (d / 2) (T / 16)
/-- `K = ⌊log₁₆ ⌊T/m⌋⌋` from Theorem 10. -/
noncomputable def lowerLogCount (d T : ℕ) : ℕ :=
⌊Real.logb 16 (T / lowerBlockCount d T : ℕ)⌋₊
end AltRegret.Supplement
Source
Tao, Zheng, Optimal Alternating Regret for Online Learning and Games, arXiv:2608.24731, §4.2, p.15