Section 4.2.3, p. 45 — implicit regret bound for self-bounded losses
ProvedModernOnlineLearning.Adaptive.implicit_boundonline-learningp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1regretself-bounded-loss
Under Theorem 4.30's assumptions, let be any adaptive OSD run on nonnegative, convex, -self-bounded losses over a nonempty closed convex set of diameter at most . Then, for every ,
This is the implicit inequality preceding Lemma 4.29: the cumulative loss of the algorithm still appears on the right-hand side.
Formalization Note Self-boundedness is checked at every feasible point and for every full-space subgradient, with the loss infimum taken over all of . Losses are real-valued and globally nonnegative; and are explicit.
Preamble
import Mathlib import Definitions.Def_ModernOnlineLearning_Adaptive_Defs
Formal statement
namespace ModernOnlineLearning.Adaptive
/-- The implicit regret bound displayed immediately before Lemma 4.29 on p. 45. -/
theorem implicit_bound {d : ℕ} (V : Set (Vec d)) (ℓ : ℕ → Vec d → ℝ)
(D s : ℝ) (T : ℕ) (x g : ℕ → Vec d)
(hT : 1 ≤ T) (hs : 0 ≤ s) (hVne : V.Nonempty)
(hVclosed : IsClosed V) (hVconv : Convex ℝ V)
(hdiam : ∀ a ∈ V, ∀ b ∈ V, ‖a - b‖ ≤ D)
(hconv : ∀ t ∈ Finset.Icc 1 T, ConvexOn ℝ Set.univ (ℓ t))
(hnonneg : ∀ t ∈ Finset.Icc 1 T, ∀ z : Vec d, 0 ≤ ℓ t z)
(hself : ∀ t ∈ Finset.Icc 1 T, IsSelfBounded V s (ℓ t))
(hrun : IsAdaptiveOSDRun V ℓ D T x g) :
∀ u ∈ V, regret ℓ x u T ≤
2 * D * Real.sqrt (s * (∑ t ∈ Finset.Icc 1 T, ℓ t (x t))) := by sorry
end ModernOnlineLearning.Adaptive
Source
Orabona, arXiv:1912.13213v10, §4.2.3, display before Lemma 4.29, p. 45
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.