Theorem 7 — algorithmic reduction with fixed
OpenIntervalToDynamic.Supplement.theorem_7dynamic-regrethigher-order-variationinterval-regretonline-learningp2o-gran-per-chapterp2o-plan-paperp2o-v1
Fix , a nonempty compact convex domain , positive loss parameters, and the enlarged ball . Uniform constants depending only on this fixed data and have the following property for every horizon and every selected loss regime.
If a history-based algorithm remains in and guarantees polynomial interval regret against every on every interval at rate , or , then the fixed- Algorithm 1 wrapper produces decisions in . For every comparator sequence in and every , its dynamic regret is bounded, up to that fixed factor, by
or
in the convex, exp-concave and strongly convex regimes, respectively. Holding for every is equivalent to the paper's minimum over .
Differences from the source:
- encoding: notation → an explicit positive interval-regret multiplier and positive reduction constants chosen before the horizon, losses, algorithm and comparator; reason: this preserves the permitted fixed-parameter and polylogarithmic dependence without allowing constants to depend on adversarial data
- encoding: a bound by → the same bound asserted separately for every ; reason: these formulations are logically equivalent for a finite nonempty index set
- encoding: differentiable losses → losses accompanied by a gradient oracle satisfying
HasGradientWithinAton ; reason: the domain may have empty interior and this is the published base mission's faithful Assumption 1 convention
Preamble
import Mathlib import Definitions.Def_IntervalToDynamic_Supplement_HigherVariation import Definitions.Def_IntervalToDynamic_Supplement_FixedKWrapper import Definitions.Def_IntervalToDynamic_SatisfiesAssumptions import Definitions.Def_ModernOnlineLearning_Dynamic_Defs open ModernOnlineLearning.Dynamic (dynamicRegret)
Formal statement
namespace IntervalToDynamic.Supplement
/-- Theorem 7 (algorithmic reduction with fixed `k`), Wang--Zhao--Zhou,
*On the Relation Between Interval Regret and Dynamic Regret*, arXiv:2609.34423, pp.11--12
(PDF pp.13--14).
The constants hidden by `Õ_k` are chosen before the horizon, losses, algorithm, and comparator.
Writing the conclusion for every `1 ≤ i ≤ k` is equivalent to the displayed minimum over `i`.
The algorithm domain and every surrogate coefficient use `D_Y = 2 κ_k D_X`. -/
theorem theorem_7 {d k : ℕ} (hd : 0 < d) (hk : 1 ≤ k)
(X : Set (EuclideanSpace ℝ (Fin d))) (DX G alpha lam : ℝ)
(hDX : 0 < DX) (hG : 0 < G) (halpha : 0 < alpha) (hlam : 0 < lam) :
∃ Cconv Cexp Cstrong : ℝ,
0 < Cconv ∧ 0 < Cexp ∧ 0 < Cstrong ∧
∀ (T : ℕ), 1 ≤ T →
∀ (f : ℕ → EuclideanSpace ℝ (Fin d) → ℝ)
(g : ℕ → EuclideanSpace ℝ (Fin d) → EuclideanSpace ℝ (Fin d))
(A : IntervalToDynamic.OnlineAlgorithm (EuclideanSpace ℝ (Fin d))),
(∀ hist, A hist ∈ Metric.closedBall (0 : EuclideanSpace ℝ (Fin d)) (kappa k * DX)) →
((∀ t ∈ Finset.Icc 1 T,
IntervalToDynamic.SatisfiesAssumptions .convex X DX G (f t) (g t)) →
∀ R : ℝ, 0 < R →
HasPolynomialIntervalRegret A (Metric.closedBall 0 (kappa k * DX))
(LossClassK k .convex DX G) T k (fun n => R * Real.sqrt n) →
let W := fixedKWrapper k .convex X DX G A g
(∀ t ∈ Finset.Icc 1 T, W.x t ∈ X) ∧
∀ u : ℕ → EuclideanSpace ℝ (Fin d),
(∀ t ∈ Finset.Icc 1 T, u t ∈ X) →
∀ i ∈ Finset.Icc 1 k,
dynamicRegret f W.x u T ≤ Cconv * R *
(1 + normalizedVariation u T i ^ (1 / (2 * i) : ℝ)) * Real.sqrt T) ∧
((∀ t ∈ Finset.Icc 1 T,
IntervalToDynamic.SatisfiesAssumptions (.expConcave alpha) X DX G (f t) (g t)) →
∀ R : ℝ, 0 < R →
HasPolynomialIntervalRegret A (Metric.closedBall 0 (kappa k * DX))
(LossClassK k (.expConcave alpha) DX G) T k
(fun n => R * d * (1 + Real.log n)) →
let W := fixedKWrapper k (.expConcave alpha) X DX G A g
(∀ t ∈ Finset.Icc 1 T, W.x t ∈ X) ∧
∀ u : ℕ → EuclideanSpace ℝ (Fin d),
(∀ t ∈ Finset.Icc 1 T, u t ∈ X) →
∀ i ∈ Finset.Icc 1 k,
dynamicRegret f W.x u T ≤ Cexp * R *
((d : ℝ) + (d : ℝ) ^ (((2 * i : ℕ) : ℝ) / ((2 * i + 1 : ℕ) : ℝ)) *
normalizedVariation u T i ^ ((2 : ℝ) / (2 * i + 1)) *
(T : ℝ) ^ ((1 : ℝ) / (2 * i + 1)))) ∧
((∀ t ∈ Finset.Icc 1 T,
IntervalToDynamic.SatisfiesAssumptions (.stronglyConvex lam) X DX G (f t) (g t)) →
∀ R : ℝ, 0 < R →
HasPolynomialIntervalRegret A (Metric.closedBall 0 (kappa k * DX))
(LossClassK k (.stronglyConvex lam) DX G) T k
(fun n => R * (1 + Real.log n)) →
let W := fixedKWrapper k (.stronglyConvex lam) X DX G A g
(∀ t ∈ Finset.Icc 1 T, W.x t ∈ X) ∧
∀ u : ℕ → EuclideanSpace ℝ (Fin d),
(∀ t ∈ Finset.Icc 1 T, u t ∈ X) →
∀ i ∈ Finset.Icc 1 k,
dynamicRegret f W.x u T ≤ Cstrong * R *
(1 + normalizedVariation u T i ^ ((2 : ℝ) / (2 * i + 1)) *
(T : ℝ) ^ ((1 : ℝ) / (2 * i + 1)))) := by sorry
end IntervalToDynamic.Supplement
Source
Wang–Zhao–Zhou, On the Relation Between Interval Regret and Dynamic Regret, arXiv:2609.34423, Theorem 7, pp.11–12 (PDF pp.13–14); proof, pp.33–35 (PDF pp.35–37)