Theorem 13.9, p. 215 — coordinate-wise KT parameter-free regret
ProvedModernOnlineLearning.ParameterFree.theorem_13_9coin-bettingonline-learningp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1parameter-free-regret
Let , , , and . Run Algorithm 13.3 on subdifferentiable losses , choosing a full-space subgradient at each prediction with . For every , both inequalities hold:
The result gives one parameter-free regret bound for each coordinate and the resulting bound in and norms.
Formalization Note Vectors are functions on Fin d; their function-space norm is the sup norm. The run predicate enforces Algorithm 13.3's exact update and bounds each selected subgradient coordinate. Positivity of , , and is explicit.
Preamble
import Mathlib import Definitions.Def_ModernOnlineLearning_ParameterFree_Defs
Formal statement
namespace ModernOnlineLearning.ParameterFree
/-- Theorem 13.9, p. 215: both coordinate-wise and norm-form regret bounds. -/
theorem theorem_13_9 (d : ℕ) (hd : 0 < d) (ε L : ℝ)
(hε : 0 < ε) (hL : 0 < L) (T : ℕ) (hT : 1 ≤ T)
(ℓ : ℕ → (Fin d → ℝ) → ℝ) (g x : ℕ → Fin d → ℝ)
(hrun : IsCoordKTRun ε L T ℓ g x) :
∀ u : Fin d → ℝ,
(∑ t ∈ Finset.Icc 1 T, (ℓ t (x t) - ℓ t u)) ≤
L * (∑ i : Fin d, |u i| * Real.sqrt
(2 * (T : ℝ) * Real.log
(1 + Real.exp 1 * |u i| * (T : ℝ) / ε))) + (d : ℝ) * ε * L ∧
L * (∑ i : Fin d, |u i| * Real.sqrt
(2 * (T : ℝ) * Real.log
(1 + Real.exp 1 * |u i| * (T : ℝ) / ε))) + (d : ℝ) * ε * L ≤
(∑ i : Fin d, |u i|) * L * Real.sqrt
(2 * (T : ℝ) * Real.log
(1 + Real.exp 1 * ‖u‖ * (T : ℝ) / ε)) + (d : ℝ) * ε * L := by sorry
end ModernOnlineLearning.ParameterFree
Source
Orabona, arXiv:1912.13213v10, Theorem 13.9, p. 215
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.