BanditAlgorithm.ftrl_simplex_exp_weights_regret
Proved(Regret on the simplex, Proposition 28.7) Let be the probability simplex and for all . FTRL (= mirror descent = exponential weights here, Example 28.3/Eq. (28.5); the book states the proposition for mirror descent and notes the identical FTRL bound via Theorem 28.5) with the unnormalised negentropy potential
on domain and learning rate satisfies
for every simplex comparator .
import Definitions.Def_OnlineLinearOptimization open RealInnerProductSpace
theorem BanditAlgorithm.ftrl_simplex_exp_weights_regret
(d n : ℕ) (y a : ℕ → EuclideanSpace ℝ (Fin d))
(hy : ∀ t, ∀ i, y t i ∈ Set.Icc (0 : ℝ) 1)
(hiter : IsFTRLIterates (Real.sqrt (2 * Real.log d / n))
(fun v : EuclideanSpace ℝ (Fin d) => ∑ i, (v i * Real.log (v i) - v i))
{v : EuclideanSpace ℝ (Fin d) | ∀ i, 0 ≤ v i}
{v : EuclideanSpace ℝ (Fin d) | (∀ i, 0 ≤ v i) ∧ ∑ i, v i = 1}
y a) :
∀ a₀ ∈ {v : EuclideanSpace ℝ (Fin d) | (∀ i, 0 ≤ v i) ∧ ∑ i, v i = 1},
oloRegret a y n a₀ ≤ Real.sqrt (2 * n * Real.log d) := by
sorry
Read-back
What the Lean code literally says, in plain math · claude-fable-5
Work in with the Euclidean inner product . Let be the probability simplex, the nonnegative orthant, and the unnormalized negative entropy ( = natural logarithm). Set the learning rate . For iterates , losses and comparator , the regret is .
The theorem asserts: for every ,
Hypotheses:
- are arbitrary natural numbers (no positivity assumed on either).
- Every loss coordinate lies in : for every and every (all rounds, not only ).
- are FTRL iterates at rate with regularizer , domain , and constraint set : and for all ; for every , and minimizes over (value value at every point; no uniqueness; the existence of such iterates is assumed, not proved).
Edge cases and conventions:
- If the simplex is empty (the empty sum is ), so the iterate hypothesis is unsatisfiable and the statement is vacuous; the conclusion also quantifies over an empty set.
- If then , so and the asserted bound is ; the FTRL predicate places no sign restriction on , so is admissible in it.
- If the expression uses the real-division-by-zero convention and equals , so ; the regret is the empty sum and the bound is .
- In , terms at evaluate to via the convention ; is a total function on .
- The bound is deterministic and holds for the specific fixed in the iterate hypothesis; nothing is claimed for other learning rates.
Confirmed by the mission captain (proposal self-audit).