p. 5, the claim before Corollary 12 — optimistic FTRL with Mᵗ = uᵗ⁻¹ and utilities in [0,1] is stable with κ = 2η
ProvedRegLearnGames.IndivRegret.oftrl_stabilityno-regret-dynamicsoptimistic-ftrlp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1stability
Let be a regularizer on that is 1-strongly convex with respect to on the simplex , and let . Let be a utility sequence with every entry in , and let be a run of optimistic FTRL with regularizer , step size and one-step recency bias . Then for every ,
This is the stability property with that the paper invokes, citing Lemma 20, to apply Theorem 11 to optimistic FTRL; it is the step that turns the regret bound of Theorem 11 into the rate of Corollary 12.
Formalization Note The bound is the paper's standing assumption (§2), which makes every utility vector lie in ; it is what bounds and by . At the predictor is , so the bound at is about the first move from . The norm is .
Preamble
import Mathlib import Definitions.Def_RegLearnGames_TotalRegret_Setting
Formal statement
namespace RegLearnGames.IndivRegret
theorem oftrl_stability {d : ℕ} (𝓡 : (Fin d → ℝ) → ℝ) (η : ℝ) (hη : 0 < η)
(h𝓡 : RegLearnGames.TotalRegret.IsOneStronglyConvexL1 𝓡) (u w : ℕ → Fin d → ℝ)
(hu : ∀ t x, u t x ∈ Set.Icc (0 : ℝ) 1)
(hw : RegLearnGames.TotalRegret.IsOFTRL 𝓡 η (fun T => u (T - 1)) u w) :
∀ t, RegLearnGames.TotalRegret.l1 (w t - w (t + 1)) ≤ 2 * η := by sorry
end RegLearnGames.IndivRegret
Source
Syrgkanis, Agarwal, Luo, Schapire, Fast Convergence of Regularized Learning in Games, arXiv:1507.00407v5, p. 5, §3.2, the sentence before Corollary 12 ("stability property with κ = 2η (see Lemma 20 in the appendix)")
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.