Lemma 20, supp. p. 4 — stability of optimistic FTRL: ‖wᵗ−gᵗ‖ ≤ η‖Mᵗ−uᵗ‖_*, ‖gᵗ−wᵗ⁺¹‖ ≤ η‖Mᵗ⁺¹‖_*
ProvedRegLearnGames.IndivRegret.lemma_20Let be a regularizer on that is 1-strongly convex with respect to on the simplex , and let . Let be any utility sequence and any predictor sequence in . Let be a run of optimistic FTRL with regularizer , step size and predictors , and let be the corresponding leader sequence. Then for every ,
The first bound says the optimistic iterate is close to the leader when the prediction is close to the realized utility ; the second says consecutive iterates move by at most times the size of the next prediction. Together they give the stability of optimistic FTRL used in Proposition 7 and in Corollary 12.
Formalization Note The paper states the lemma for a general norm; it is formalized for and its dual , the case the mission's goal uses. The values and are arbitrary (they enter only the bound at , where and both minimize ). This statement coincides with the one of the companion mission I of this series.
import Mathlib import Definitions.Def_RegLearnGames_TotalRegret_Setting
namespace RegLearnGames.IndivRegret
theorem lemma_20 {d : ℕ} (𝓡 : (Fin d → ℝ) → ℝ) (η : ℝ) (hη : 0 < η)
(h𝓡 : RegLearnGames.TotalRegret.IsOneStronglyConvexL1 𝓡) (M u w g : ℕ → Fin d → ℝ)
(hw : RegLearnGames.TotalRegret.IsOFTRL 𝓡 η M u w) (hg : RegLearnGames.TotalRegret.IsLeader 𝓡 η u g) :
∀ t, RegLearnGames.TotalRegret.l1 (w t - g t) ≤ η * ‖M t - u t‖ ∧ RegLearnGames.TotalRegret.l1 (g t - w (t + 1)) ≤ η * ‖M (t + 1)‖ := by sorry
end RegLearnGames.IndivRegret
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.