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
Read-back
What the Lean code literally says, in plain math · claude-fable-5
Work in with the Euclidean inner product . For , is the gradient (junk value where is not differentiable) and is the Bregman divergence. For iterates , losses and comparator , the regret is .
The theorem asserts: for every comparator ,
Hypotheses:
- .
- is convex and is convex on — only this; no Legendre-type interior, strict-convexity, or boundary-steepness conditions are assumed.
- is convex and nonempty.
- are FTRL iterates for the losses at rate : and for every ; and for every , and minimizes over ("minimizes" = value value at every point; no uniqueness).
- is differentiable at for every (not only ), so the gradients inside the Bregman terms are genuine.
Edge cases and conventions:
- is arbitrary, including (empty sums, regret ).
- Nothing places the iterates in the interior of , and may have empty interior.
- The bound is claimed for every comparator in ; the loss vectors are entirely unconstrained.
- The iterate predicate is an assumption; the theorem does not assert such iterates exist.
- The dimension is arbitrary, including .
Human review
Confirmed by the mission captain (proposal self-audit).