Theorem 1 — OIR does not imply ODR on general convex domains
OpenIntervalToDynamic.Supplement.theorem_1dynamic-regretinterval-regretlower-boundsonline-learningp2o-gran-per-chapterp2o-plan-paperp2o-v1
There are absolute constants such that, for every path-length budget family with eventually and , the following hold for every sufficiently large :
- On the unit Euclidean ball in , there are linear losses with coefficient norm at most , decisions having interval regret at most on every interval against every comparator, and a comparator path of length at most , while
- On the unit ball in , there are quadratic losses that are -Lipschitz, -strongly convex and -exp-concave, decisions having interval regret at most on every interval against every comparator, and a comparator path of length at most , while
This shows that optimal interval regret alone does not imply the minimax dynamic-regret rate on general smooth convex domains.
Differences from the source:
- encoding: "for every sufficiently large and " → absolute positive constants followed by every budget function with an eventual lower bound and , then an eventual quantifier over ; reason: little- is a property of an asymptotic family and the lower-bound constants supplied by the construction are uniform in the budget family
- encoding: linear and quadratic losses on the two unit balls → explicit two-dimensional coefficient-norm linear losses and explicit identity-Hessian quadratics together with the printed Lipschitz and curvature predicates; reason: the proof's constructions live in and this makes every advertised loss property part of the Lean assertion
Preamble
import Mathlib import Definitions.Def_IntervalToDynamic_Supplement_Geometry import Definitions.Def_LogRegretOCO_ONS_IsExpConcaveOn open Filter open ModernOnlineLearning.Dynamic (dynamicRegret pathLength)
Formal statement
namespace IntervalToDynamic.Supplement
/-- Theorem 1 (OIR does not imply ODR on general convex domains), Wang--Zhao--Zhou,
*On the Relation Between Interval Regret and Dynamic Regret*, arXiv:2609.34423, p.4
(PDF p.6).
Both counterexample families are retained. The positive lower-bound constants are absolute: they
are chosen before the admissible budget family, horizon, losses, decisions, and comparators. -/
theorem theorem_1 :
∃ cLin cQuad : ℝ, 0 < cLin ∧ 0 < cQuad ∧
∀ tau : ℕ → ℝ,
(∀ᶠ T in atTop, 1 ≤ tau T) →
Tendsto (fun T : ℕ => tau T / T) atTop (nhds 0) →
∀ᶠ T : ℕ in atTop,
(∃ (g : ℕ → EuclideanSpace ℝ (Fin 2))
(x u : ℕ → EuclideanSpace ℝ (Fin 2)),
(∀ t ∈ Finset.Icc 1 T, ‖g t‖ ≤ 1) ∧
(∀ t ∈ Finset.Icc 1 T, x t ∈ unitLpBall 2 ∧ u t ∈ unitLpBall 2) ∧
SatisfiesOIR (T := T) (unitLpBall 2) (fun t z => inner ℝ (g t) z) x 1
(fun n => Real.sqrt n) ∧
pathLength u T ≤ tau T ∧
cLin * tau T ^ (2 / 5 : ℝ) * (T : ℝ) ^ (3 / 5 : ℝ) ≤
dynamicRegret (fun t z => inner ℝ (g t) z) x u T) ∧
(∃ (f : ℕ → EuclideanSpace ℝ (Fin 2) → ℝ)
(a : ℕ → EuclideanSpace ℝ (Fin 2)) (b : ℕ → ℝ)
(x u : ℕ → EuclideanSpace ℝ (Fin 2)),
(∀ t ∈ Finset.Icc 1 T, ∀ z,
f t z = (1 / 2 : ℝ) * ‖z‖ ^ 2 + inner ℝ (a t) z + b t) ∧
(∀ t ∈ Finset.Icc 1 T, ∀ z ∈ unitLpBall (3 / 2 : ℝ),
∀ z' ∈ unitLpBall (3 / 2 : ℝ), |f t z - f t z'| ≤ 3 * ‖z - z'‖) ∧
(∀ t ∈ Finset.Icc 1 T,
StrongConvexOn (unitLpBall (3 / 2 : ℝ)) 1 (f t) ∧
LogRegretOCO.ONS.IsExpConcaveOn (1 / 9 : ℝ) (unitLpBall (3 / 2 : ℝ)) (f t)) ∧
(∀ t ∈ Finset.Icc 1 T,
x t ∈ unitLpBall (3 / 2 : ℝ) ∧ u t ∈ unitLpBall (3 / 2 : ℝ)) ∧
SatisfiesOIR (T := T) (unitLpBall (3 / 2 : ℝ)) f x 1 (fun _ => 1) ∧
pathLength u T ≤ tau T ∧
cQuad * tau T ^ (3 / 5 : ℝ) * (T : ℝ) ^ (2 / 5 : ℝ) ≤
dynamicRegret f x u T) := by sorry
end IntervalToDynamic.Supplement
Source
Wang–Zhao–Zhou, On the Relation Between Interval Regret and Dynamic Regret, arXiv:2609.34423, Theorem 1, p.4 (PDF p.6); proof, pp.14–15 (PDF pp.16–17)