BanditAlgorithm.mirror_descent_regret_bound
Provedmirror-descentonline-learningregret
(Mirror descent regret bound, Theorem 28.4) Let , be Legendre with domain , and a non-empty convex set with . If are the (well-defined) mirror-descent iterates with unprojected dual iterates , then for any comparator , both
and (the Eq. (28.6)-conditioned second form, the condition being internalised in the iterate predicate as existence of the dual iterates)
Preamble
import Definitions.Def_OnlineLinearOptimization open RealInnerProductSpace
Formal statement
theorem BanditAlgorithm.mirror_descent_regret_bound
{d : ℕ} {η : ℝ} (hη : 0 < η)
{F : EuclideanSpace ℝ (Fin d) → ℝ} {D 𝒜 : Set (EuclideanSpace ℝ (Fin d))}
(hF : IsLegendre F D) (h𝒜conv : Convex ℝ 𝒜) (h𝒜ne : 𝒜.Nonempty)
(hmeet : (interior D ∩ 𝒜).Nonempty)
(y a ã : ℕ → EuclideanSpace ℝ (Fin d)) (n : ℕ)
(hiter : IsMirrorDescentIterates η F D 𝒜 y a ã) :
∀ 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))) ∧
(oloRegret a y n a₀ ≤
(1 / η) * (F a₀ - F (a 0) +
∑ t ∈ Finset.range n, bregmanDiv F (a t) (ã (t + 1)))) := by
sorry
Source
L&S Theorem 28.4, p.331