Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma G.26 — good events, ratio moments and the weighted failure bound for corrupted GIA-FTRL

Proved
IAFTRL.lemma_G_26

by Canzhe Zhao · Nov 17, 2026 · Mathlib 0df444a (Lean v4.33.1)

bandit-algorithmslinear-banditsonline-learning

Setting. The sharp corrupted instance of Proposition 3.1 / G.1. Here A\mathcal AA is a compact action set in the Euclidean unit ball that spans Rd\mathbb R^dRd, and B⊆A\mathcal B\subseteq\mathcal AB⊆A is a compact generator (A⊆Conv B\mathcal A\subseteq\mathrm{Conv}\,\mathcal BA⊆ConvB) with k=dim⁡K≥1k=\dim\mathcal K\ge1k=dimK≥1, where K=Conv B\mathcal K=\mathrm{Conv}\,\mathcal BK=ConvB. The direction enumeration e:N→Qde:\mathbb N\to\mathbb Q^de:N→Qd is surjective, and ∥θ∥A≤1\|\theta\|_{\mathcal A}\le1∥θ∥A​≤1. The action a∗∈Aa^*\in\mathcal Aa∗∈A is the unique optimal action, the instance is sharp, and Δ(a)=(a−a∗)⊤θ\Delta(a)=(a-a^*)^\top\thetaΔ(a)=(a−a∗)⊤θ. The reference measure is μ=∑j∈Jπjδbj+ωμμ16\mu=\sum_{j\in J}\pi_j\delta_{b_j}+\omega_\mu\mu_{16}μ=∑j∈J​πj​δbj​​+ωμ​μ16​ of (3.3), and the learning rate is βn=16d+n\beta_n=16d+\sqrt nβn​=16d+n​.

Claim (interface form). There is a constant WWW, depending only on the instance, with the following property. Take any GIA-FTRL run of T≥1T\ge1T≥1 rounds in the corrupted regime with budget C≥0C\ge0C≥0, with cumulative estimates Xt(a)=(a−a∗)⊤∑s<tθ^sX_t(a)=(a-a^*)^\top\sum_{s<t}\hat\theta_sXt​(a)=(a−a∗)⊤∑s<t​θ^s​ (paper round ttt). This run admits measurable events GtG_tGt​ and measurable ratios Lt,UtL_t,U_tLt​,Ut​, both zero off GtG_tGt​, satisfying the following.

  1. Pointwise comparisons. On GtG_tGt​, Lt≥1L_t\ge1Lt​≥1, Ut≥0U_t\ge0Ut​≥0, and for all a∈Ka\in\mathcal Ka∈K:
Xt(a)≥4t7/8Δ(a),Δ(a)Lt≤Xt(a)t≤UtΔ(a).X_t(a)\ge4t^{7/8}\Delta(a),\qquad\frac{\Delta(a)}{L_t}\le\frac{X_t(a)}{t}\le U_t\Delta(a).Xt​(a)≥4t7/8Δ(a),Lt​Δ(a)​≤tXt​(a)​≤Ut​Δ(a).
  1. Ratio moments. E[LtrUt]≤64r+1\mathbb E[L_t^rU_t]\le64^{r+1}E[Ltr​Ut​]≤64r+1 for r=1,3,5r=1,3,5r=1,3,5.
  2. Weighted failure bound.
∑t=1Tt−1/2 P(Gtc)≤W(1+Clog⁡(e+C)).\sum_{t=1}^{T}t^{-1/2}\,\mathbb P(G_t^c)\le W\big(1+\sqrt C\log(e+C)\big).t=1∑T​t−1/2P(Gtc​)≤W(1+C​log(e+C)).

Formalization Note. Rounds are 0-based in Lean: run round ttt is paper round t+1t+1t+1. This is Gt=GtcorG_t=G_t^{\rm cor}Gt​=Gtcor​ of Lemma G.26, with Lt=1Gtmax⁡{1,mf−1}L_t=\mathbf 1_{G_t}\max\{1,m_f^{-1}\}Lt​=1Gt​​max{1,mf−1​} and Ut=1GtRfU_t=\mathbf 1_{G_t}R_fUt​=1Gt​​Rf​. Item 1 is (G.552) and (G.554), item 2 is (G.551), and item 3 is (G.525) combined with (G.11).

Preamble
import Mathlib
import Definitions.Def_IAFTRL_LinEnv
import Definitions.Def_IAFTRL_GIAFTRL
Formal statement
namespace IAFTRL

open MeasureTheory

/-- **Lemma G.26 (Uniform relative gaps, with a square-root-chargeable failure tail).** Zhao–Tan, *Best-of-Both-Worlds FTRL for Linear Bandits* (STOC submission version), Lemma G.26, pp.174–176:
"`Σ_{t≥1} t^{−1/2} P((G_t^cor)^c) ≤ W_θ √H`. On `G_t^cor` … the ratio moments hold with
`C_rat = 64` …", with (G.550)–(G.554): "`E[L_t^r U_t] ≤ C_rat^{r+1}` (r = 1, 3, 5),
`Δ(a)/L_t ≤ X_t(a)/t ≤ U_t Δ(a)`, `X_t(a) ≥ 4τ_t Δ(a) ≥ 4t^{7/8}Δ(a)`", and (G.11):
`√H ≤ 16[1 + √C log(e + C)]`.

Interface form, with 0-based rounds (run round `t` is the paper's round `t + 1`, with
`X_{t+1}(a) = (a − a*)ᵀ Σ_{s<t} θ̂_s`): in the sharp corrupted setting there is `W` such that
every run admits measurable good events `G_t` and ratios `L_t, U_t` (vanishing off `G_t`) with the
pointwise gap comparisons on `G_t`, the three product moments, and the weighted failure bound
`Σ_t (t+1)^{−1/2} P(G_tᶜ) ≤ W (1 + √C log(e + C))`. -/
theorem lemma_G_26 {d : ℕ} (hd : 1 ≤ d) (𝒜 ℬ : Set (Fin d → ℝ)) (e : ℕ → Fin d → ℚ)
    (h𝒜 : IsCompact 𝒜) (hℬ : IsCompact ℬ) (hgen : IsGenerator 𝒜 ℬ)
    (hball : ∀ a ∈ 𝒜, a ⬝ᵥ a ≤ 1) (hspan : Submodule.span ℝ 𝒜 = ⊤) (hk : 1 ≤ kdim ℬ)
    (he : Function.Surjective e) (θ astar : Fin d → ℝ) (hθ : setNorm 𝒜 θ ≤ 1)
    (hastar : astar ∈ 𝒜) (huniq : ∀ a ∈ 𝒜, a ≠ astar → astar ⬝ᵥ θ < a ⬝ᵥ θ)
    (hsharp : IsSharp 𝒜 θ astar) :
    ∃ W : ℝ, ∀ {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω) [IsProbabilityMeasure P]
        (T : ℕ) (C : ℝ) (R : GRun d Ω), 1 ≤ T → 0 ≤ C →
        IsGIAFTRLRun P 𝒜 ℬ e T R → IsCorruptedG P 𝒜 θ C T R →
        ∃ (G : ℕ → Set Ω) (L U : ℕ → Ω → ℝ),
          (∀ t, MeasurableSet (G t)) ∧ (∀ t, Measurable (L t)) ∧ (∀ t, Measurable (U t)) ∧
          (∀ t < T, ∀ ω ∈ G t, 1 ≤ L t ω ∧ 0 ≤ U t ω ∧ ∀ a ∈ Kset ℬ,
            4 * ((t + 1 : ℕ) : ℝ) ^ ((7 : ℝ) / 8) * ((a - astar) ⬝ᵥ θ) ≤
              (a - astar) ⬝ᵥ R.cumEst t ω ∧
            (a - astar) ⬝ᵥ θ ≤ L t ω * ((a - astar) ⬝ᵥ R.cumEst t ω / ((t : ℝ) + 1)) ∧
            (a - astar) ⬝ᵥ R.cumEst t ω / ((t : ℝ) + 1) ≤ U t ω * ((a - astar) ⬝ᵥ θ)) ∧
          (∀ t < T, ∀ ω ∉ G t, L t ω = 0 ∧ U t ω = 0) ∧
          (∀ t < T, ∀ r ∈ ({1, 3, 5} : Finset ℕ),
            Integrable (fun ω => L t ω ^ r * U t ω) P ∧
            ∫ ω, L t ω ^ r * U t ω ∂P ≤ 64 ^ (r + 1)) ∧
          ∑ t ∈ Finset.range T, (Real.sqrt ((t : ℝ) + 1))⁻¹ * (P (G t)ᶜ).toReal ≤
            W * (1 + Real.sqrt C * Real.log (Real.exp 1 + C)) := by sorry

end IAFTRL
Source
Zhao–Tan, Best-of-Both-Worlds FTRL for Linear Bandits: The Interplay of Information Acquisition, Corruption, and Geometry (STOC submission version; arXiv:2611.01299), Appendix G.6, Lemma G.26, (G.525) and (G.550)–(G.561), with (G.8)–(G.11)

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