§6.6, p. 81 — Exponentiated Gradient regret on the simplex
ProvedModernOnlineLearning.ToX.eg_regret_6_6exponentiated-gradientonline-learningp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1regret
Let and . Run Exponentiated Gradient from the uniform point on against losses , choosing a subgradient at each prediction . Then for every fixed ,
This is the regret estimate used with Theorem 16.4 to obtain the finite-class bound in Corollary 16.7.
Formalization Note Losses are represented by real-valued functions and the chosen subgradient satisfies the subgradient inequality for every comparator in the simplex. This records exactly the part of the book's extended-valued subgradient condition used by the regret estimate. The infinity norm is the maximum coordinate absolute value. The run predicate explicitly fixes the uniform initial point and the update rule of Algorithm 6.2.
Preamble
import Mathlib import Definitions.Def_ModernOnlineLearning_ToX_Algorithms
Formal statement
namespace ModernOnlineLearning.ToX
/-- The unnumbered EG regret display of §6.6, p. 81.
`IsEGRun` is Algorithm 6.2, p. 80; each `g t` is a subgradient of
the round's loss at `x t`. -/
theorem eg_regret_6_6 {d T : ℕ} [NeZero d] (hT : 1 ≤ T)
(η : ℝ) (g x : ℕ → Fin d → ℝ)
(loss : ℕ → (Fin d → ℝ) → ℝ)
(hRun : IsEGRun T η g x)
(hsub : ∀ t ∈ Finset.Icc 1 T, ∀ y ∈ simplex d,
loss t (x t) + pairing (g t) (y - x t) ≤ loss t y) :
∀ u ∈ simplex d,
(∑ t ∈ Finset.Icc 1 T, (loss t (x t) - loss t u)) ≤
Real.log (d : ℝ) / η +
η / 2 * ∑ t ∈ Finset.Icc 1 T,
(Finset.univ.sup' Finset.univ_nonempty
(fun i : Fin d => |g t i|)) ^ 2 := by sorry
end ModernOnlineLearning.ToX
Source
Orabona, arXiv:1912.13213v10, §6.6, p. 81, first display after Lemma 6.33; Algorithm 6.2, p. 80
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.