Lemma 20, supp. p. 4 — stability of optimistic FTRL: ‖wᵗ−gᵗ‖ ≤ η‖Mᵗ−uᵗ‖_* and ‖gᵗ−wᵗ⁺¹‖ ≤ η‖Mᵗ⁺¹‖_*
ProvedRegLearnGames.TotalRegret.lemma_20Let be the probability simplex, a regularizer that is 1-strongly convex with respect to on , and . Let and be arbitrary utility and predictor sequences in , let be any run of optimistic FTRL and any leader sequence for them. Then for every ,
These two stability inequalities say that the iterate is close to the leader when the prediction is accurate, and that one step of the algorithm moves the leader by at most times the size of the next prediction. Combined with Theorem 19 the first gives Proposition 7.
Formalization Note The paper writes the lemma for a general norm and its dual; here and . At both and minimize over (the values , play no role in either sequence), so the first inequality holds there as well; it is stated for every .
import Mathlib import Definitions.Def_RegLearnGames_TotalRegret_Setting
namespace RegLearnGames.TotalRegret
theorem lemma_20 {d : ℕ} (𝓡 : (Fin d → ℝ) → ℝ) (η : ℝ) (hη : 0 < η)
(h𝓡 : IsOneStronglyConvexL1 𝓡)
(M u w g : ℕ → Fin d → ℝ) (hw : IsOFTRL 𝓡 η M u w) (hg : IsLeader 𝓡 η u g) :
∀ t : ℕ, l1 (w t - g t) ≤ η * ‖M t - u t‖ ∧ l1 (g t - w (t + 1)) ≤ η * ‖M (t + 1)‖ := by sorry
end RegLearnGames.TotalRegret
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.