Theorem 10 — linear dimension dependence is necessary
OpenAltRegret.Supplement.theorem_10algorithmic-game-theoryonline-convex-optimizationonline-learningp2o-gran-per-chapterp2o-plan-paperp2o-v1regret
Let , , , and let be the product of copies of together with one interval when is odd. For every possibly randomized causal online algorithm on , there is a deterministic oblivious sequence of continuous convex losses such that
In particular this yields the paper's lower bound.
The statement uses the paper's specific body and preserves every floor and the exact constant.
Differences from the source:
- encoding: the product body X is displayed as a Cartesian product → coordinate-pair inequalities define the same product, with the last coordinate constrained to [−r,r] when d is odd; reason: this is the literal coordinate membership test for the displayed body
- encoding: a possibly randomized online algorithm A → a measurable causal map from past losses and a private seed with an arbitrary probability law; reason: the deterministic loss sequence is existential outside the seed, preserving obliviousness and the expectation convention
Preamble
import Mathlib import Definitions.Def_AltRegret_Supplement_OnlineAlgorithm import Definitions.Def_AltRegret_Supplement_productBody open MeasureTheory
Formal statement
namespace AltRegret.Supplement
/-- **Theorem 10 (Linear dimension dependence is necessary).** Tao–Zheng,
*Optimal Alternating Regret for Online Learning and Games*, arXiv:2608.24731, Theorem 10,
p.15. On the paper's product body `X ⊆ B_d(1)`, every randomized online algorithm has a
deterministic oblivious continuous convex loss sequence forcing expected alternating regret
at least `mK/125`, with the exact floor definitions of `m` and `K`.
**Formalization Note.** `productBody d` is exactly the product of `⌊d/2⌋` copies of
`(1/√d) B₂(1)` and, for odd `d`, the interval `[-1/√d,1/√d]`. -/
theorem theorem_10 {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω) [IsProbabilityMeasure P]
{d : ℕ} (hd : 2 ≤ d) (A : OnlineAlgorithm Ω d)
(hA : IsOnlineAlgorithmOn (productBody d) A)
(T : ℕ) (hT : 16 ≤ T) :
∃ f : ℕ → Point d → ℝ,
(∀ t, 1 ≤ t → t ≤ T →
ContinuousOn (f t) (productBody d) ∧
ConvexOn ℝ (productBody d) (f t) ∧
∀ u ∈ productBody d, f t u ∈ Set.Icc (0 : ℝ) 1) ∧
((lowerBlockCount d T * lowerLogCount d T : ℕ) : ℝ) / 125 ≤
expectedWorstAltRegret P (productBody d) A f T := by sorry
end AltRegret.Supplement
Source
Tao, Zheng, Optimal Alternating Regret for Online Learning and Games, arXiv:2608.24731, Theorem 10, p.15