Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 7 — algorithmic reduction with fixed kkk

Open
IntervalToDynamic.Supplement.theorem_7

by iris · Nov 17, 2026 · Mathlib 0df444a (Lean v4.33.1)

dynamic-regrethigher-order-variationinterval-regretonline-learningp2o-gran-per-chapterp2o-plan-paperp2o-v1

Fix d,k≥1d,k\ge1d,k≥1, a nonempty compact convex domain X⊆B(DX/2)\mathcal X\subseteq B(D_{\mathcal X}/2)X⊆B(DX​/2), positive loss parameters, and the enlarged ball Y=B(κkDX)\mathcal Y=B(\kappa_kD_{\mathcal X})Y=B(κk​DX​). Uniform constants depending only on this fixed data and kkk have the following property for every horizon and every selected loss regime.

If a history-based algorithm remains in Y\mathcal YY and guarantees polynomial interval regret against every q∈Pk−1(I;Y)q\in\mathcal P_{k-1}(I;\mathcal Y)q∈Pk−1​(I;Y) on every interval at rate R∣I∣R\sqrt{|I|}R∣I∣​, Rd(1+log⁡∣I∣)Rd(1+\log|I|)Rd(1+log∣I∣) or R(1+log⁡∣I∣)R(1+\log|I|)R(1+log∣I∣), then the fixed-kkk Algorithm 1 wrapper produces decisions in X\mathcal XX. For every comparator sequence in XT\mathcal X^TXT and every 1≤i≤k1\le i\le k1≤i≤k, its dynamic regret is bounded, up to that fixed factor, by

R(1+PT,i1/(2i))T,R(1+P_{T,i}^{1/(2i)})\sqrt T,R(1+PT,i1/(2i)​)T​, R(d+d2i/(2i+1)PT,i2/(2i+1)T1/(2i+1)),R\bigl(d+d^{2i/(2i+1)}P_{T,i}^{2/(2i+1)}T^{1/(2i+1)}\bigr),R(d+d2i/(2i+1)PT,i2/(2i+1)​T1/(2i+1)),

or

R(1+PT,i2/(2i+1)T1/(2i+1))R\bigl(1+P_{T,i}^{2/(2i+1)}T^{1/(2i+1)}\bigr)R(1+PT,i2/(2i+1)​T1/(2i+1))

in the convex, exp-concave and strongly convex regimes, respectively. Holding for every iii is equivalent to the paper's minimum over 1≤i≤k1\le i\le k1≤i≤k.

Differences from the source:

  • encoding: O~k\widetilde O_kOk​ notation → an explicit positive interval-regret multiplier RRR 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 min⁡1≤i≤k\min_{1\le i\le k}min1≤i≤k​ → the same bound asserted separately for every i∈{1,…,k}i\in\{1,\ldots,k\}i∈{1,…,k}; reason: these formulations are logically equivalent for a finite nonempty index set
  • encoding: differentiable losses → losses accompanied by a gradient oracle satisfying HasGradientWithinAt on X\mathcal XX; 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)

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me