Theorem 2 — homogeneous aggregation represents all proofs
OpenIntervalToDynamic.Supplement.theorem_2dynamic-regretinterval-regretlinear-programming-dualityonline-learningp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
Fix a positive horizon, a nonempty compact convex domain , continuous losses , a comparator path in , a nonnegative nondecreasing rate , and . Among all actual -valued decision sequences satisfying every OIR constraint
simultaneously for all intervals and all , dynamic regret has a maximizing sequence . Among all homogeneous fractional interval covers, the singleton-corrected dual objective has a minimizing cover . These attained values are equal:
Here is exactly the paper's cost, including .
This equality characterizes the strongest dynamic-regret conclusion obtainable from the OIR inequalities alone.
Differences from the source:
- encoding: attained maximum and minimum notation → explicit maximizing decision sequence and minimizing homogeneous cover, with universal optimality clauses and equality of their values; reason: real suprema and infima are total in Lean and have junk defaults, whereas witnesses express both attainment claims literally
- generalization: → a nonempty compact convex subset of an arbitrary real normed vector space; reason: the LP argument uses only compactness, convexity and continuity, and the Lean statement specializes to the paper by taking Euclidean space
Preamble
import Mathlib import Definitions.Def_IntervalToDynamic_Supplement_Geometry open ModernOnlineLearning.Dynamic (dynamicRegret)
Formal statement
namespace IntervalToDynamic.Supplement
/-- Theorem 2 (homogeneous aggregation represents all proofs), Wang--Zhao--Zhou,
*On the Relation Between Interval Regret and Dynamic Regret*, arXiv:2609.34423, p.5
(PDF p.7).
The two extrema are expressed by maximizing/minimizing witnesses, avoiding any default value of a
real `sSup` or `sInf`. The primal ranges over actual `X`-valued decision sequences satisfying every
Eq. (4) constraint; the dual ranges over homogeneous fractional covers, not partitions. -/
theorem theorem_2 {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E]
(T : ℕ) (hT : 1 ≤ T) (X : Set E) (hXc : IsCompact X) (hXv : Convex ℝ X)
(hXn : X.Nonempty) (f : ℕ → E → ℝ)
(hf : ∀ t ∈ Finset.Icc 1 T, ContinuousOn (f t) X)
(u : ℕ → E) (hu : ∀ t ∈ Finset.Icc 1 T, u t ∈ X)
(rho : ℕ → ℝ) (hrho : ∀ n, 0 ≤ rho n)
(hrho_mono : Monotone rho) (A : ℝ) (hA : 1 ≤ A) :
∃ (xStar : ℕ → E) (lamStar : RoundInterval T → ℝ),
(∀ t ∈ Finset.Icc 1 T, xStar t ∈ X) ∧
SatisfiesOIR (T := T) X f xStar A rho ∧ IsHomogeneous lamStar ∧
(∀ x : ℕ → E, (∀ t ∈ Finset.Icc 1 T, x t ∈ X) →
SatisfiesOIR (T := T) X f x A rho →
dynamicRegret f x u T ≤ dynamicRegret f xStar u T) ∧
(∀ lam : RoundInterval T → ℝ, IsHomogeneous lam →
aggregationValue X f u A rho lamStar ≤ aggregationValue X f u A rho lam) ∧
dynamicRegret f xStar u T = aggregationValue X f u A rho lamStar := by sorry
end IntervalToDynamic.Supplement
Source
Wang–Zhao–Zhou, On the Relation Between Interval Regret and Dynamic Regret, arXiv:2609.34423, Theorem 2, p.5 (PDF p.7); proof, pp.15–16 (PDF pp.17–18)