BanditAlgorithm.ftrl_regret_bound
Provedftrlonline-learningregret
(Follow-the-regularised-leader regret bound, Theorem 28.5) Let , be convex with domain (differentiable at every iterate, an explicit hypothesis since the Lean Bregman divergence uses the total gradient), and a non-empty convex set. If are the (well-defined) FTRL iterates then for any comparator :
Preamble
import Definitions.Def_OnlineLinearOptimization open RealInnerProductSpace
Formal statement
theorem BanditAlgorithm.ftrl_regret_bound
{d : ℕ} {η : ℝ} (hη : 0 < η)
{F : EuclideanSpace ℝ (Fin d) → ℝ} {D 𝒜 : Set (EuclideanSpace ℝ (Fin d))}
(hF : ConvexOn ℝ D F) (h𝒜conv : Convex ℝ 𝒜) (h𝒜ne : 𝒜.Nonempty)
(y a : ℕ → EuclideanSpace ℝ (Fin d)) (n : ℕ)
(hiter : IsFTRLIterates η F D 𝒜 y a)
(hdiff : ∀ t, DifferentiableAt ℝ F (a t)) :
∀ a₀ ∈ 𝒜 ∩ D,
oloRegret a y n a₀ ≤
(F a₀ - F (a 0)) / η +
∑ t ∈ Finset.range n,
(⟪a t - a (t + 1), y t⟫ - (1 / η) * bregmanDiv F (a (t + 1)) (a t)) := by
sorry
Source
L&S Theorem 28.5, p.334