Theorem 9 — algorithm realizability
OpenIntervalToDynamic.Supplement.theorem_9Fix , the ball , a positive Lipschitz bound , and positive exp-concavity and strong-convexity coefficients. There are positive constants and fixed nonnegative integer powers, all independent of the horizon and losses, such that for every horizon Algorithms 3–4 exist in each of the three modes and satisfy polynomial interval regret simultaneously on every interval against every at rates
The loss classes are differentiable convex -Lipschitz losses, with the corresponding exp-concavity or strong-convexity property in the curved modes.
The algorithm objects implement the exact dyadic cover, polynomial coefficient domains, OGD/ONS base updates, priors, mode-specific aggregation probabilities and weight recurrences printed in Algorithms 3–4.
Differences from the source:
- encoding: rates required by Theorem 7 → positive constants and fixed powers of , quantified before the horizon and multiplied by the displayed or factors; reason: this retains the logarithmic factors in that the paper hides while preserving the displayed dependence
- encoding: Algorithms 3 and 4 given as pseudocode → a structure whose fields are the exact geometric-cover, basis, feasibility, projected base-update, active aggregation and weight-update equations, together with a history-map algorithm agreeing with the aggregate decisions; reason: this makes the named algorithms mathematical data rather than an informal label
- encoding: differentiable losses and observed gradients on the closed ball →
DifferentiableOntogether with a domain-relative gradient oracle satisfyingHasGradientWithinAt; reason: this represents the paper's gradient observations without adding ambient differentiability at boundary points
import Mathlib import Definitions.Def_IntervalToDynamic_Supplement_Algorithms34 import Definitions.Def_LogRegretOCO_ONS_IsExpConcaveOn
namespace IntervalToDynamic.Supplement
/-- Theorem 9 (algorithm realizability), Wang--Zhao--Zhou,
*On the Relation Between Interval Regret and Dynamic Regret*, arXiv:2609.34423,
Theorem 9, p.42 (PDF p.44), with Algorithms 3--4 on pp.46 and 49.
One theorem covers all three branches. `Algorithms34` records the printed dyadic cover,
polynomial lifting and mode-specific base/meta recurrences; the conclusions are simultaneous on
every interval and against every polynomial comparator. The constants hidden by `Õ_k` are fixed
before the horizon and loss sequence, while explicit powers of `1 + log T` retain the logarithmic
factors in the paper's `Õ_k` notation. -/
theorem theorem_9 {d k : ℕ} (hd : 0 < d) (hk : 1 ≤ k)
(DY Gh alpha lam : ℝ) (hDY : 0 < DY) (hGh : 0 < Gh)
(halpha : 0 < alpha) (hlam : 0 < lam) :
∃ Cconv Cexp Cstrong : ℝ,
∃ pconv pexp pstrong : ℕ,
0 < Cconv ∧ 0 < Cexp ∧ 0 < Cstrong ∧
∀ T : ℕ, 1 ≤ T →
(∃ S : Algorithms34 .convex T d k DY Gh,
HasPolynomialIntervalRegret S.A
(Metric.closedBall (0 : EuclideanSpace ℝ (Fin d)) (DY / 2))
(fun h => DifferentiableOn ℝ h (Metric.closedBall 0 (DY / 2)) ∧
ConvexOn ℝ (Metric.closedBall 0 (DY / 2)) h ∧
∀ y ∈ Metric.closedBall (0 : EuclideanSpace ℝ (Fin d)) (DY / 2),
∀ z ∈ Metric.closedBall (0 : EuclideanSpace ℝ (Fin d)) (DY / 2),
|h y - h z| ≤ Gh * ‖y - z‖)
T k (fun n => Cconv * (1 + Real.log T) ^ pconv * Real.sqrt n)) ∧
(∃ S : Algorithms34 (.expConcave alpha) T d k DY Gh,
HasPolynomialIntervalRegret S.A
(Metric.closedBall (0 : EuclideanSpace ℝ (Fin d)) (DY / 2))
(fun h => DifferentiableOn ℝ h (Metric.closedBall 0 (DY / 2)) ∧
ConvexOn ℝ (Metric.closedBall 0 (DY / 2)) h ∧
(∀ y ∈ Metric.closedBall (0 : EuclideanSpace ℝ (Fin d)) (DY / 2),
∀ z ∈ Metric.closedBall (0 : EuclideanSpace ℝ (Fin d)) (DY / 2),
|h y - h z| ≤ Gh * ‖y - z‖) ∧
LogRegretOCO.ONS.IsExpConcaveOn alpha (Metric.closedBall 0 (DY / 2)) h)
T k (fun n => Cexp * (1 + Real.log T) ^ pexp * d * (1 + Real.log n))) ∧
(∃ S : Algorithms34 (.stronglyConvex lam) T d k DY Gh,
HasPolynomialIntervalRegret S.A
(Metric.closedBall (0 : EuclideanSpace ℝ (Fin d)) (DY / 2))
(fun h => DifferentiableOn ℝ h (Metric.closedBall 0 (DY / 2)) ∧
ConvexOn ℝ (Metric.closedBall 0 (DY / 2)) h ∧
(∀ y ∈ Metric.closedBall (0 : EuclideanSpace ℝ (Fin d)) (DY / 2),
∀ z ∈ Metric.closedBall (0 : EuclideanSpace ℝ (Fin d)) (DY / 2),
|h y - h z| ≤ Gh * ‖y - z‖) ∧
StrongConvexOn (Metric.closedBall 0 (DY / 2)) lam h)
T k (fun n => Cstrong * (1 + Real.log T) ^ pstrong *
(1 + Real.log n))) := by sorry
end IntervalToDynamic.Supplement