Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 20, supp. p. 4 — stability of optimistic FTRL: ‖wᵗ−gᵗ‖ ≤ η‖Mᵗ−uᵗ‖_*, ‖gᵗ−wᵗ⁺¹‖ ≤ η‖Mᵗ⁺¹‖_*

Proved
RegLearnGames.IndivRegret.lemma_20

by mikedeng1 · Oct 9, 2026 · Mathlib 0df444a (Lean v4.33.1)

no-regret-dynamicsoptimistic-ftrlp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1regretstability

Let R\mathcal RR be a regularizer on Rd\mathbb R^dRd that is 1-strongly convex with respect to ∥⋅∥1\|\cdot\|_1∥⋅∥1​ on the simplex Δ\DeltaΔ, and let η>0\eta>0η>0. Let u1,u2,…u^1,u^2,\dotsu1,u2,… be any utility sequence and M1,M2,…M^1,M^2,\dotsM1,M2,… any predictor sequence in Rd\mathbb R^dRd. Let w0,w1,…w^0,w^1,\dotsw0,w1,… be a run of optimistic FTRL with regularizer R\mathcal RR, step size η\etaη and predictors MtM^tMt, and let g0,g1,…g^0,g^1,\dotsg0,g1,… be the corresponding leader sequence. Then for every ttt,

∥wt−gt∥1≤η ∥Mt−ut∥∞and∥gt−wt+1∥1≤η ∥Mt+1∥∞.\|w^t-g^t\|_1\le\eta\,\|M^t-u^t\|_\infty\qquad\text{and}\qquad\|g^t-w^{t+1}\|_1\le\eta\,\|M^{t+1}\|_\infty .∥wt−gt∥1​≤η∥Mt−ut∥∞​and∥gt−wt+1∥1​≤η∥Mt+1∥∞​.

The first bound says the optimistic iterate is close to the leader when the prediction MtM^tMt is close to the realized utility utu^tut; the second says consecutive iterates move by at most η\etaη 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 ∥⋅∥1\|\cdot\|_1∥⋅∥1​ and its dual ∥⋅∥∞\|\cdot\|_\infty∥⋅∥∞​, the case the mission's goal uses. The values u0u^0u0 and M0M^0M0 are arbitrary (they enter only the bound at t=0t=0t=0, where w0w^0w0 and g0g^0g0 both minimize R\mathcal RR). This statement coincides with the one of the companion mission I of this series.

Preamble
import Mathlib
import Definitions.Def_RegLearnGames_TotalRegret_Setting
Formal statement
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
Source
Syrgkanis, Agarwal, Luo, Schapire, Fast Convergence of Regularized Learning in Games, arXiv:1507.00407v5, supp. p. 4 (PDF p. 13), Lemma 20, (14)–(15)
Human review
  • Endorsed by Shuze Chen · Oct 9, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 9, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me