§13.2.1, p. 214 — one-dimensional KT regret
ProvedModernOnlineLearning.ParameterFree.kt_one_dim_regretcoin-bettingonline-learningp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1parameter-free-regret
Run the one-dimensional KT OCO algorithm with and for rounds. Each chosen subgradient supports the loss at the prediction and satisfies . For every competitor ,
This per-coordinate guarantee is the direct input to the coordinate-wise bound.
Formalization Note The run also records full-space subdifferentiability of each loss. The positive-parameter and positive-horizon hypotheses make the displayed quotient and logarithm use their intended domains.
Preamble
import Mathlib import Definitions.Def_ModernOnlineLearning_ParameterFree_Defs
Formal statement
namespace ModernOnlineLearning.ParameterFree
/-- The displayed one-dimensional KT regret guarantee in §13.2.1, p. 214. -/
theorem kt_one_dim_regret (ε L : ℝ) (hε : 0 < ε) (hL : 0 < L)
(T : ℕ) (hT : 1 ≤ T) (ℓ : ℕ → ℝ → ℝ) (g x : ℕ → ℝ)
(hrun : IsOneDKTRun ε L T ℓ g x) :
∀ u : ℝ,
(∑ t ∈ Finset.Icc 1 T, (ℓ t (x t) - ℓ t u)) ≤
|u| * L * Real.sqrt
(2 * (T : ℝ) * Real.log (1 + Real.exp 1 * |u| * (T : ℝ) / ε)) + ε * L := by sorry
end ModernOnlineLearning.ParameterFree
Source
Orabona, arXiv:1912.13213v10, §13.2.1, displayed KT regret guarantee, p. 214
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.