Theorem 13.4, pp. 210–211: KT wealth dominates its potential
ProvedModernOnlineLearning.ParameterFree.wealth_dominates_potentialcoin-bettinggamma-functioninductiononline-learning
Let , let be an integer, and let . Write and define the KT wealth by . For the gamma-function potential
we have
This is the wealth-domination step in Theorem 13.4, which combines with a lower bound on the potential to obtain an exponential wealth guarantee.
Formalization Note The statement includes the zero-round base case explicitly used in the source proof. It uses the existing definitions of KT wealth and potential.
Preamble
import Definitions.Def_ModernOnlineLearning_ParameterFree_Defs open ModernOnlineLearning.ParameterFree
Formal statement
theorem ModernOnlineLearning.ParameterFree.wealth_dominates_potential (ε : ℝ) (hε : 0 < ε) (T : ℕ)
(c : ℕ → ℝ) (hc : ∀ t ∈ Finset.Icc 1 T, -1 ≤ c t ∧ c t ≤ 1) :
ktPotential ε T (∑ t ∈ Finset.Icc 1 T, c t) ≤ ktWealth ε c T := by sorrySource
Francesco Orabona, Online Learning: A Modern Introduction Using Convex Optimization, arXiv:1912.13213v10, proof of Theorem 13.4, printed pp. 210–211. https://arxiv.org/abs/1912.13213v10