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
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 , both of
and
Hypotheses:
- .
- is a Legendre pair: is convex with convex on ; ; is differentiable at every point of and strictly convex there; and along any sequence in converging to a boundary point of , .
- is convex and nonempty, and .
- and are mirror-descent iterates for the losses at rate : minimizes over ; every ; each minimizes over ; each satisfies ; and each minimizes over ("minimizes" = value value at every point of the set; no uniqueness).
Edge cases and conventions:
- The horizon is an arbitrary natural number, including , in which case both sums are empty and the regret is .
- All Bregman terms take gradients at points (, ) that the iterate predicate places in , where the Legendre hypothesis makes genuinely differentiable; the Bregman divergence itself has no differentiability guard.
- The two bounds are asserted jointly (a conjunction), for every comparator in — not merely for a best comparator.
- The dimension is arbitrary, including .
- The iterate predicate is an assumption; the theorem asserts nothing about existence of such iterates.
Human review
Confirmed by the mission captain (proposal self-audit).