Lemma 13.6, p. 213: pointwise Gaussian exponential conjugate bound
ProvedModernOnlineLearning.ParameterFree.lemma_13_6_pointwisecoin-bettingconvex-conjugateexponential-inequalityonline-learning
Let and let be arbitrary real numbers. Then
This uniform pointwise inequality gives the final upper bound on the Fenchel conjugate of in Lemma 13.6. It converts an exponential wealth lower bound into a comparator-dependent regret bound.
Formalization Note The statement is the pointwise form of the last conjugate bound, retaining the negative constant . It does not formalize the preceding exact Lambert-W formula.
Preamble
import Mathlib
Formal statement
theorem ModernOnlineLearning.ParameterFree.lemma_13_6_pointwise (a b x y : ℝ) (ha : 0 < a) (hb : 0 < b) :
x * y - b * Real.exp (x ^ 2 / (2 * a)) ≤
|y| * Real.sqrt (2 * a * Real.log (1 + Real.sqrt a * |y| / b)) - b := by sorrySource
Francesco Orabona, Online Learning: A Modern Introduction Using Convex Optimization, arXiv:1912.13213v10, Lemma 13.6, printed p. 213, final inequality. https://arxiv.org/abs/1912.13213v10