Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 19, supp. p. 3 — optimistic FTRL regret ≤ R/η + Σ‖uᵗ−Mᵗ‖_*‖wᵗ−gᵗ‖ − (1/2η)Σ(‖wᵗ−gᵗ‖² + ‖wᵗ−gᵗ⁻¹‖²)

Proved
RegLearnGames.TotalRegret.theorem_19

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

online-learningoptimistic-ftrlp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1regret

Let Δ⊂Rd\Delta \subset \mathbb R^dΔ⊂Rd be the probability simplex, R\mathcal RR a regularizer that is 1-strongly convex with respect to ∥⋅∥1\|\cdot\|_1∥⋅∥1​ on Δ\DeltaΔ, η>0\eta > 0η>0 a step size, and RRR a bound on the range of R\mathcal RR on Δ\DeltaΔ: R(f)−R(g)≤R\mathcal R(f) - \mathcal R(g) \le RR(f)−R(g)≤R for all f,g∈Δf, g \in \Deltaf,g∈Δ. Let u1,u2,…u^1, u^2, \dotsu1,u2,… be an arbitrary utility sequence and M1,M2,…M^1, M^2, \dotsM1,M2,… an arbitrary predictor sequence in Rd\mathbb R^dRd, let w0,w1,…w^0, w^1, \dotsw0,w1,… be any run of optimistic FTRL on them, and let g0,g1,…g^0, g^1, \dotsg0,g1,… be any leader sequence, gT∈argmax⁡g∈Δ⟨g,∑t=1Tut⟩−R(g)/ηg^T \in \operatorname{argmax}_{g\in\Delta}\langle g, \sum_{t=1}^T u^t\rangle - \mathcal R(g)/\etagT∈argmaxg∈Δ​⟨g,∑t=1T​ut⟩−R(g)/η. Then for every horizon TTT and every comparator w∗∈Δw^* \in \Deltaw∗∈Δ,

∑t=1T⟨w∗−wt,ut⟩≤Rη+∑t=1T∥ut−Mt∥∗ ∥wt−gt∥−12η∑t=1T(∥wt−gt∥2+∥wt−gt−1∥2),\sum_{t=1}^T \langle w^* - w^t, u^t\rangle \le \frac{R}{\eta} + \sum_{t=1}^T \|u^t - M^t\|_*\,\|w^t - g^t\| - \frac{1}{2\eta}\sum_{t=1}^T \big(\|w^t - g^t\|^2 + \|w^t - g^{t-1}\|^2\big),t=1∑T​⟨w∗−wt,ut⟩≤ηR​+t=1∑T​∥ut−Mt∥∗​∥wt−gt∥−2η1​t=1∑T​(∥wt−gt∥2+∥wt−gt−1∥2),

where ∥⋅∥=∥⋅∥1\|\cdot\| = \|\cdot\|_1∥⋅∥=∥⋅∥1​ and ∥⋅∥∗=∥⋅∥∞\|\cdot\|_* = \|\cdot\|_\infty∥⋅∥∗​=∥⋅∥∞​.

This is the basic regret bound of optimistic FTRL. Its negative terms, which measure how far each iterate is from the leader, are what Proposition 7 converts into the negative movement term of the RVU property.

Formalization Note The paper states the result for a single player and a general norm with R=sup⁡fR(f)−inf⁡fR(f)R = \sup_f \mathcal R(f) - \inf_f \mathcal R(f)R=supf​R(f)−inff​R(f); here the norm is ℓ1\ell_1ℓ1​ (the case Theorem 4 and Corollary 8 use), and RRR is any upper bound on the range of R\mathcal RR over Δ\DeltaΔ, which includes the exact range. The utilities and predictors are arbitrary real vectors, as on the page.

Preamble
import Mathlib
import Definitions.Def_RegLearnGames_TotalRegret_Setting
Formal statement
namespace RegLearnGames.TotalRegret

theorem theorem_19 {d : ℕ} (𝓡 : (Fin d → ℝ) → ℝ) (η R : ℝ) (hη : 0 < η)
    (h𝓡 : IsOneStronglyConvexL1 𝓡)
    (hR : ∀ f ∈ stdSimplex ℝ (Fin d), ∀ g ∈ stdSimplex ℝ (Fin d), 𝓡 f - 𝓡 g ≤ R)
    (M u w g : ℕ → Fin d → ℝ) (hw : IsOFTRL 𝓡 η M u w) (hg : IsLeader 𝓡 η u g)
    (T : ℕ) (wstar : Fin d → ℝ) (hwstar : wstar ∈ stdSimplex ℝ (Fin d)) :
    ∑ t ∈ Finset.Icc 1 T, (wstar - w t) ⬝ᵥ u t ≤
      R / η + ∑ t ∈ Finset.Icc 1 T, ‖u t - M t‖ * l1 (w t - g t)
        - 1 / (2 * η) * ∑ t ∈ Finset.Icc 1 T, (l1 (w t - g t) ^ 2 + l1 (w t - g (t - 1)) ^ 2) := by sorry

end RegLearnGames.TotalRegret
Source
Syrgkanis, Agarwal, Luo, Schapire, Fast Convergence of Regularized Learning in Games, arXiv:1507.00407v5, supp. p. 3 (PDF p. 12), App. C, Theorem 19, inequality (11)
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