Higher differences, normalized -th variation, and polynomial interval regret
DefinitionIntervalToDynamic_Supplement_HigherVariationdynamic-regrethigher-order-variationinterval-regretonline-learningp2o-gran-per-chapterp2o-plan-paperp2o-v1
For a sequence , define and . Its unnormalized and normalized -th difference variations are
On an interval , consists of the functions whose -th difference is zero whenever the entire stencil lies in . Polynomial interval regret is
A polynomial interval-regret guarantee holds simultaneously on every interval and against every such -valued comparator.
Formalization Note Round zero is unused. The difference function is total, but every variation sum and polynomial constraint begins only where the complete backward stencil exists. For , the normalized variation is definitionally the published path length.
Definition code
import Mathlib
import Definitions.Def_IntervalToDynamic_Supplement_Geometry
import Definitions.Def_IntervalToDynamic_OnlineAlgorithm
import Definitions.Def_IntervalToDynamic_decisions
namespace IntervalToDynamic.Supplement
/-- The backward `k`-th difference `D^k u_t`, p.11. Round zero and earlier junk values are never
read: every use below starts at `t = k + 1`. -/
def kthDifference {E : Type*} [AddGroup E] : ℕ → (ℕ → E) → ℕ → E
| 0, u, t => u t
| k + 1, u, t => kthDifference k u t - kthDifference k u (t - 1)
/-- The unnormalized variation `V_{T,k} = Σ_{t=k+1}^T ‖D^k u_t‖₂`. -/
noncomputable def higherVariation {E : Type*} [NormedAddGroup E]
(u : ℕ → E) (T k : ℕ) : ℝ :=
∑ t ∈ Finset.Icc (k + 1) T, ‖kthDifference k u t‖
/-- The normalized variation `P_{T,k} = T^{k-1} V_{T,k}`, p.11. -/
noncomputable def normalizedVariation {E : Type*} [NormedAddGroup E]
(u : ℕ → E) (T k : ℕ) : ℝ :=
(T : ℝ) ^ (k - 1) * higherVariation u T k
/-- `q ∈ P_{k-1}(I;Y)`: `q` is `Y`-valued on `I` and its `k`-th difference vanishes
whenever the complete stencil `[t-k,t]` lies in `I`, Eq. (16), p.11. -/
def IsPolynomialComparator {E : Type*} [AddGroup E] {T : ℕ}
(k : ℕ) (I : RoundInterval T) (Y : Set E) (q : ℕ → E) : Prop :=
(∀ t ∈ I.rounds, q t ∈ Y) ∧
∀ t ∈ Finset.Icc (I.start + k) I.stop, kthDifference k q t = 0
/-- Polynomial interval regret, Eq. (16), p.11. -/
def polynomialIntervalRegret {E : Type*} {T : ℕ} (h : ℕ → E → ℝ)
(y q : ℕ → E) (I : RoundInterval T) : ℝ :=
∑ t ∈ I.rounds, (h t (y t) - h t (q t))
/-- A simultaneous polynomial interval-regret guarantee against every `Y`-valued polynomial
comparator on every interval. -/
def HasPolynomialIntervalRegret {E : Type*} [AddGroup E] (A : IntervalToDynamic.OnlineAlgorithm E)
(Y : Set E) (C : (E → ℝ) → Prop) (T k : ℕ) (rate : ℕ → ℝ) : Prop :=
∀ h : ℕ → E → ℝ, (∀ t ∈ Finset.Icc 1 T, C (h t)) →
∀ I : RoundInterval T, ∀ q : ℕ → E, IsPolynomialComparator k I Y q →
polynomialIntervalRegret h (IntervalToDynamic.decisions A h) q I ≤ rate I.rounds.card
end IntervalToDynamic.Supplement
Source
Wang–Zhao–Zhou, On the Relation Between Interval Regret and Dynamic Regret, arXiv:2609.34423, Eq. (16) and preceding definitions, p.11 (PDF p.13)