Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemmas C.14, C.24, C.26, C.30 (v1) — good events with per-action inverse and positive local moments

Proved
IAFTRL.lemma_C_30_local_moments

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

bandit-algorithmslinear-banditsonline-learning

This is the probabilistic core of the corrupted stochastic analysis of IA-FTRL, stated one action at a time: predictable good events, their separation and failure sum, and the inverse and positive local moments of the estimated cumulative loss differences on those events.

Setting. Let d≥1d\ge1d≥1 and let A={a1,…,aK}\mathcal A=\{a_1,\dots,a_K\}A={a1​,…,aK​} be a finite action set in the Euclidean unit ball of Rd\mathbb R^dRd that spans Rd\mathbb R^dRd. Let θ\thetaθ satisfy ∥θ∥A≤1\|\theta\|_{\mathcal A}\le1∥θ∥A​≤1 with a unique optimal action a∗a^*a∗, gaps Δ(a)=(a−a∗)⊤θ\Delta(a)=(a-a^*)^\top\thetaΔ(a)=(a−a∗)⊤θ, and let Δ0∈(0,1]\Delta_0\in(0,1]Δ0​∈(0,1] satisfy Δ0≤Δ(a)\Delta_0\le\Delta(a)Δ0​≤Δ(a) for all a≠a∗a\ne a^*a=a∗. Consider an execution of IA-FTRL for T≥1T\ge1T≥1 rounds in the corrupted stochastic regime with budget C≥0C\ge0C≥0, with loss estimates θ^s\hat\theta_sθ^s​. Write

Xt,a=(a−a∗)⊤∑s<tθ^sX_{t,a}=(a-a^*)^\top\sum_{s<t}\hat\theta_sXt,a​=(a−a∗)⊤s<t∑​θ^s​

for the estimated cumulative loss difference before round t+1t+1t+1, and cR=dlog⁡(eK)c_R=\sqrt{d\log(eK)}cR​=dlog(eK)​.

Claim. There is an absolute constant c0>0c_0>0c0​>0 such that, for every such instance, there is a constant MMM (independent of TTT, CCC and the run) with the following property. For every run there are a moment order P∈NP\in\mathbb NP∈N with P≥8P\ge8P≥8 and K≤2PK\le2^PK≤2P, measurable events G0,G1,…G_0,G_1,\dotsG0​,G1​,… and numbers Ψt≥1\Psi_t\ge1Ψt​≥1 such that, for all t<Tt<Tt<T and all a≠a∗a\ne a^*a=a∗:

  1. on GtG_tGt​: Xt,a≥4 (t+1)3/4X_{t,a}\ge4\,(t+1)^{3/4}Xt,a​≥4(t+1)3/4;
  2. cR∑t<TP(Gtc)t+1≤c0dlog⁡K Δ0−128/255C+M\displaystyle c_R\sum_{t<T}\frac{P(G_t^{c})}{\sqrt{t+1}}\le c_0\sqrt{d\log K}\,\Delta_0^{-128/255}\sqrt C+McR​t<T∑​t+1​P(Gtc​)​≤c0​dlogK​Δ0−128/255​C​+M;
  3. (inverse local moment) E[1Gt((t+1)Δ(a)Xt,a)P]≤8P\displaystyle E\Big[\mathbf 1_{G_t}\Big(\frac{(t+1)\Delta(a)}{X_{t,a}}\Big)^P\Big]\le 8^PE[1Gt​​(Xt,a​(t+1)Δ(a)​)P]≤8P;
  4. (positive local moment) E[1Gt(Xt,a(t+1)Δ(a))P]≤(8Ψt)P\displaystyle E\Big[\mathbf 1_{G_t}\Big(\frac{X_{t,a}}{(t+1)\Delta(a)}\Big)^P\Big]\le (8\Psi_t)^PE[1Gt​​((t+1)Δ(a)Xt,a​​)P]≤(8Ψt​)P;
  5. (bounded distortion) Ψt≤M\Psi_t\le MΨt​≤M and ∑t<TΨt−1t+1≤M\displaystyle\sum_{t<T}\frac{\Psi_t-1}{t+1}\le Mt<T∑​t+1Ψt​−1​≤M,

where the random variables in 3–4 are integrable.

In the source, P=2⌈256+log⁡(2K)⌉P=2\lceil256+\log(2K)\rceilP=2⌈256+log(2K)⌉, so K1/P<2K^{1/P}<2K1/P<2. The events are those of Definition C.25 and are empty before T∘T_\circT∘​. Item 3 is the single-action form of (C.114a)–(C.114c), from Lemma C.30 and Xt,a≥12Yt,a†X_{t,a}\ge\frac12Y^\dagger_{t,a}Xt,a​≥21​Yt,a†​ on GtG_tGt​. Item 4 is the single-action form of (C.114d)–(C.114e), from Lemma C.14 and Xt,a≤Yt,a†X_{t,a}\le Y^\dagger_{t,a}Xt,a​≤Yt,a†​. The quantity Ψt=1+A0u01−κ0Δmin⁡−1(n0/t)σ0\Psi_t=1+A_0u_0^{1-\kappa_0}\Delta_{\min}^{-1}(n_0/t)^{\sigma_0}Ψt​=1+A0​u01−κ0​​Δmin−1​(n0​/t)σ0​ of (C.118) satisfies Ψt≤ΨΔmin⁡\Psi_t\le\Psi_{\Delta_{\min}}Ψt​≤ΨΔmin​​ and ∑t≥T∘(Ψt−1)/t≤3A0Δmin⁡−ε0\sum_{t\ge T_\circ}(\Psi_t-1)/t\le3A_0\Delta_{\min}^{-\varepsilon_0}∑t≥T∘​​(Ψt​−1)/t≤3A0​Δmin−ε0​​.

Lemma C.13's moment bounds on the gap ratios Lt,UtL_t,U_tLt​,Ut​ (IAFTRL.lemma_C_13_good_event) follow from these per-action bounds by a short argument: maximum-to-sum, the PPP-th root trick using K≤2PK\le2^PK≤2P, and generalized Hölder. So this statement is the remaining analytic content of the good-event layer.

Formalization Note Rounds are 0-based (Lean round ttt is the paper's round t+1t+1t+1). The moment order is called p in Lean, to avoid a clash with the measure P. PPP, the events and Ψ\PsiΨ are chosen after the run, while c0c_0c0​ is absolute and MMM depends only on the instance. Items 1–2 are exactly the conclusion of IAFTRL.lemma_C_24_good_event. For t<T∘t<T_\circt<T∘​ one may take Ψt=1\Psi_t=1Ψt​=1, since Gt=∅G_t=\emptysetGt​=∅ there. For K=1K=1K=1 there is no suboptimal action and Gt=ΩG_t=\OmegaGt​=Ω works.

Preamble
import Mathlib
import Definitions.Def_IAFTRL_IsActionSet
import Definitions.Def_IAFTRL_IsIAFTRLRun
import Definitions.Def_LinearBanditProtocol
import Definitions.Def_IAFTRL_actionNorm
import Definitions.Def_IAFTRL_IsUniqueMin
import Definitions.Def_IAFTRL_IsCorrupted
import Definitions.Def_IAFTRL_cR
import Definitions.Def_IAFTRL_Run_cumEst
Formal statement
namespace IAFTRL

open Matrix MeasureTheory

/-- **Predictable good events with per-action local moments.** Zhao–Tan, *Best-of-Both-Worlds FTRL
for Linear Bandits*, arXiv:2611.01299v1, Definition C.17 (`P = 2⌈256 + log(2K)⌉`, `k = K^{1/P}`),
Definition C.25, Lemma C.26 and Lemma C.24 with (C.4) (the good events, their separation and their
weighted failure sum), Lemma C.30 with (C.113)–(C.114c) (inverse local moments:
"`E[1_{G_t} L_t^P] ≤ 1 + Σ_{a≠a*} (2tΔ(a))^P E[I_t (Y†_{t,a})^{-P}] ≤ 1 + K8^P`"), and Lemma C.14 with
(C.114d)–(C.114e) (positive local moments: "`E[1_{G_t} (X_{t,a}/(tΔ(a)))^P] ≤ E[I_t (Y†_{t,a}/(tΔ(a)))^P]
≤ (8Ψ_t)^P`", "`Ψ_t ≤ Ψ_{Δmin}`, `Σ_{t≥T◦}(Ψ_t − 1)/t ≤ 3A₀Δ_min^{-ε₀}`"), with `G_t = ∅` for `t < T◦`.

For every instance of the corrupted stochastic regime there are an even moment order `P ≥ 8` with
`K ≤ 2^P`, measurable events `G_t` (Lean round `t`, paper round `t + 1`) and numbers `Ψ_t ≥ 1` such
that, with `X_{t,a} = (a − a*)^⊤ Σ_{s<t} θ̂_s`:
1. on `G_t`, `X_{t,a} ≥ 4(t + 1)^{3/4}` for `a ≠ a*`;
2. `c_R Σ_{t<T} P(G_t^c)/√(t+1) ≤ c₀ √(d log K) Δ₀^{-128/255} √C + M`;
3. `E[1_{G_t} ((t+1)Δ(a)/X_{t,a})^P] ≤ 8^P` for `a ≠ a*` (inverse local moment);
4. `E[1_{G_t} (X_{t,a}/((t+1)Δ(a)))^P] ≤ (8Ψ_t)^P` for `a ≠ a*` (positive local moment);
5. `Ψ_t ≤ M` and `Σ_{t<T} (Ψ_t − 1)/(t+1) ≤ M` (bounded accumulated distortion).

**Formalization Note.** `c₀` is absolute; `M` is chosen after `(d, K, 𝒜, θ, a*, Δ₀)` and before the
probability space, `T`, `C` and the run; `P`, the events and `Ψ` are chosen after the run (in the
source `P` depends only on `K`, and `K^{1/P} = k < 2`). Items 1–2 are those of
`IAFTRL.lemma_C_24_good_event`. Item 3 is (C.114a)–(C.114c) for a single action; item 4 is
(C.114d)–(C.114e) for a single action, with `Ψ_t` of (C.118); `Ψ_t := 1` for `t < T◦`, where
`G_t = ∅`. The integrands are stated with their integrability. -/
theorem lemma_C_30_local_moments : ∃ c₀ : ℝ, 0 < c₀ ∧
    ∀ {d K : ℕ}, 1 ≤ d → ∀ (arms : Fin K → Fin d → ℝ), IsActionSet arms →
      ∀ (θ : Fin d → ℝ) (jstar : Fin K) (Δ₀ : ℝ),
        actionNorm arms θ ≤ 1 → IsUniqueMin arms θ jstar → 0 < Δ₀ → Δ₀ ≤ 1 →
        (∀ j, j ≠ jstar → Δ₀ ≤ (arms j - arms jstar) ⬝ᵥ θ) →
        ∃ M : ℝ, ∀ {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω) [IsProbabilityMeasure P]
          (T : ℕ) (C : ℝ) (R : Run d K Ω), 1 ≤ T → 0 ≤ C →
          IsIAFTRLRun P arms T R → IsCorrupted P arms θ C T R →
          ∃ (G : ℕ → Set Ω) (p : ℕ) (Ψ : ℕ → ℝ), (∀ t, MeasurableSet (G t)) ∧
            8 ≤ p ∧ (K : ℝ) ≤ 2 ^ p ∧
            (∀ t < T, ∀ ω ∈ G t, ∀ a, a ≠ jstar →
              4 * (t + 1 : ℝ) ^ ((3 : ℝ) / 4) ≤ (arms a - arms jstar) ⬝ᵥ R.cumEst arms t ω) ∧
            cR d K * ∑ t ∈ Finset.range T, (P (G t)ᶜ).toReal / Real.sqrt (t + 1) ≤
              c₀ * (Real.sqrt ((d : ℝ) * Real.log K) * Δ₀ ^ (-(128 : ℝ) / 255) * Real.sqrt C) +
                M ∧
            (∀ t < T, ∀ a, a ≠ jstar →
              Integrable ((G t).indicator fun ω => ((t + 1 : ℝ) * ((arms a - arms jstar) ⬝ᵥ θ) /
                ((arms a - arms jstar) ⬝ᵥ R.cumEst arms t ω)) ^ p) P ∧
              ∫ ω, (G t).indicator (fun ω => ((t + 1 : ℝ) * ((arms a - arms jstar) ⬝ᵥ θ) /
                ((arms a - arms jstar) ⬝ᵥ R.cumEst arms t ω)) ^ p) ω ∂P ≤ 8 ^ p) ∧
            (∀ t < T, ∀ a, a ≠ jstar →
              Integrable ((G t).indicator fun ω => ((arms a - arms jstar) ⬝ᵥ R.cumEst arms t ω /
                ((t + 1 : ℝ) * ((arms a - arms jstar) ⬝ᵥ θ))) ^ p) P ∧
              ∫ ω, (G t).indicator (fun ω => ((arms a - arms jstar) ⬝ᵥ R.cumEst arms t ω /
                ((t + 1 : ℝ) * ((arms a - arms jstar) ⬝ᵥ θ))) ^ p) ω ∂P ≤ (8 * Ψ t) ^ p) ∧
            (∀ t < T, 1 ≤ Ψ t ∧ Ψ t ≤ M) ∧
            ∑ t ∈ Finset.range T, (Ψ t - 1) / (t + 1) ≤ M := by sorry

end IAFTRL
Source
Zhao–Tan, Best-of-Both-Worlds FTRL for Linear Bandits, arXiv:2611.01299v1, Definition C.17 (p.71), (C.113)–(C.114) in Lemma C.13 (p.66), Lemma C.14 (p.67), Lemma C.24 (p.77), Definition C.25 and Lemma C.26 (p.78), Lemma C.30 (p.82)

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