Theorem 5.4 coefficient: positive range and limit 1 − log 2
ProvedModernOnlineLearning.LowerBounds.phi_propertiesonline-learningreal-analysisregret-lower-bounds
For , let
The coefficient in the unprojected online subgradient descent lower bound satisfies
and
This formalizes the range and endpoint-limit assertions accompanying Theorem 5.4. The existing theorem ModernOnlineLearning.LowerBounds.theorem_5_4 formalizes the adversarial sequence and regret estimate and explicitly leaves the endpoint limit outside its declaration. The limit here is from below, respecting the source domain ; it is not an assertion about the value of Lean's totalized formula at .
Preamble
import Mathlib import Definitions.Def_ModernOnlineLearning_LowerBounds_phi set_option autoImplicit false open Filter Set open scoped Topology
Formal statement
namespace ModernOnlineLearning.LowerBounds
/-- Coefficient range and endpoint limit accompanying Theorem 5.4, p. 52. -/
theorem phi_properties :
(∀ α : ℝ, 0 < α → α < 1 → phi α ∈ Set.Ioo 0 (1-Real.log 2)) ∧
Tendsto phi (𝓝[<] (1 : ℝ)) (𝓝 (1-Real.log 2)) ∧
(3/10 : ℝ) ≤ 1-Real.log 2 := by sorry
end ModernOnlineLearning.LowerBounds
Source
Francesco Orabona, A Modern Introduction to Online Learning, arXiv:1912.13213v10, Theorem 5.4, printed p. 52, coefficient codomain and final sentence. https://arxiv.org/abs/1912.13213v10