Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Crossing envelope: probability that the negative maximum of a field-interface field exceeds a level on a block

Proved
G26.FI.cross_env

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

bandit-algorithmslinear-banditsonline-learning

Throughout, D⊆RdD\subseteq\mathbb R^dD⊆Rd is a compact convex nonempty body with affine dimension j=dim⁡aff⁡Dj=\dim\operatorname{aff}Dj=dimaffD and normalized relative volume σ\sigmaσ (Hausdorff measure of dimension jjj, conditioned on DDD). On a probability space with sub-σ\sigmaσ-algebras (Fn)n≤T(\mathcal F_n)_{n\le T}(Fn​)n≤T​, increasing for n<Tn<Tn<T, the random affine field Zn(u)=u⊤Vn+cnZ_n(u)=u^\top V_n+c_nZn​(u)=u⊤Vn​+cn​ (u∈Du\in Du∈D) has Fn\mathcal F_nFn​-measurable Vn∈RdV_n\in\mathbb R^dVn​∈Rd, cn∈Rc_n\in\mathbb Rcn​∈R, and JnJ_nJn​ are Fn\mathcal F_nFn​-measurable alive events with Jn+1⊆JnJ_{n+1}\subseteq J_nJn+1​⊆Jn​. Write Nn=max⁡D(−Zn)N_n=\max_D(-Z_n)Nn​=maxD​(−Zn​) and ξn(u)=Zn+1(u)−Zn(u)\xi_n(u)=Z_{n+1}(u)-Z_n(u)ξn​(u)=Zn+1​(u)−Zn​(u). The field interface FI(β,B,ℓ,h,m0)\mathrm{FI}(\beta,B,\ell,h,m_0)FI(β,B,ℓ,h,m0​) asks that ZnZ_nZn​ be a.s. bounded on DDD, that Nn≥0N_n\ge0Nn​≥0 a.s., and that for m0≤n<Tm_0\le n<Tm0​≤n<T and u∈Du\in Du∈D, almost surely on JnJ_nJn​,

ℓ≤E[ξn(u)∣Fn]≤h,∣ξn(u)∣≤3βn+Zn(u)+2NnB,E[ξn(u)2∣Fn]≤10βn+2(Zn(u)+2Nn)2B(n+1).\ell\le\mathbb E[\xi_n(u)\mid\mathcal F_n]\le h,\qquad |\xi_n(u)|\le3\beta_n+\frac{Z_n(u)+2N_n}{B},\qquad \mathbb E[\xi_n(u)^2\mid\mathcal F_n]\le10\beta_n+\frac{2(Z_n(u)+2N_n)^2}{B(n+1)} .ℓ≤E[ξn​(u)∣Fn​]≤h,∣ξn​(u)∣≤3βn​+BZn​(u)+2Nn​​,E[ξn​(u)2∣Fn​]≤10βn​+B(n+1)2(Zn​(u)+2Nn​)2​.

Assume FI(β,B,0,h,m0)\mathrm{FI}(\beta,B,0,h,m_0)FI(β,B,0,h,m0​) holds (nonnegative drift) with h≥0h\ge0h≥0. Let k≥2k\ge2k≥2, j≤4kj\le4kj≤4k, 220⋅4k≤B2^{20}\cdot4k\le B220⋅4k≤B, b≥0b\ge0b≥0, βn≥1\beta_n\ge1βn​≥1, βn2≤b2(n+1)\beta_n^2\le b^2(n+1)βn2​≤b2(n+1), and let W∈NW\in\mathbb NW∈N satisfy W≥1+1024(4k)2/BW\ge1+1024(4k)^2/BW≥1+1024(4k)2/B. Fix vvv, m0≤m≤N≤Tm_0\le m\le N\le Tm0​≤m≤N≤T and 1≤λ≤ρ1\le\lambda\le\rho1≤λ≤ρ. Let Zˉ=frz(Z,A)\bar Z=\mathrm{frz}(Z,A)Zˉ=frz(Z,A) be the field frozen at its first crossing after vvv, i.e. at the survival rule As=Js∩{s<v or Ns≤λ}A_s=J_s\cap\{s<v\text{ or }N_s\le\lambda\}As​=Js​∩{s<v or Ns​≤λ}. Let pAp_ApA​ bound P(max⁡D∣ZˉN∣>ρ)\mathbb P(\max_D|\bar Z_N|>\rho)P(maxD​∣ZˉN​∣>ρ), and let F0F_0F0​ bound E∫D(−Zˉm)+4kdσ\mathbb E\int_D(-\bar Z_m)_+^{4k}d\sigmaE∫D​(−Zˉm​)+4k​dσ. Then

P(∃s∈[v,N]: ω∈Js, Ns>λ)≤pA+24k4j(ρ/λ)jλ4k(Hneg(k,b,B) (N+1)3k+(N+1m+1)WF0).\mathbb P\big(\exists s\in[v,N]:\ \omega\in J_s,\ N_s>\lambda\big)\le p_A+\frac{2^{4k}4^{j}(\rho/\lambda)^{j}}{\lambda^{4k}}\Big(H_{\rm neg}(k,b,B)\,(N+1)^{3k}+\Big(\frac{N+1}{m+1}\Big)^{W}F_0\Big).P(∃s∈[v,N]: ω∈Js​, Ns​>λ)≤pA​+λ4k24k4j(ρ/λ)j​(Hneg​(k,b,B)(N+1)3k+(m+1N+1​)WF0​).

The negative integral moment of the frozen field satisfies the linear recurrence (G.490) from time mmm onward; Markov's inequality at the deterministic endpoint NNN, applied to the frozen negative maximum, controls the first crossing as in (G.423). Lemma J.11 converts the integral moment into the maximum on {max⁡D∣ZˉN∣≤ρ}\{\max_D|\bar Z_N|\le\rho\}{maxD​∣ZˉN​∣≤ρ}. This is the block-crossing bound used for the windows in Lemmas G.22, G.28 and G.29.

Formalization Note Hneg k b B is the particular-solution constant of the negative recurrence; rounds are 0-based.

Preamble
import Mathlib
import Definitions.Def_IAFTRL_LinEnv
import Definitions.Def_IAFTRL_GIAFTRL
import Definitions.Def_IAFTRL_G26_body
import Definitions.Def_IAFTRL_G26_run
import Definitions.Def_IAFTRL_G26_window

open MeasureTheory ProbabilityTheory Set IAFTRL Matrix J11
open G26
variable {d : ℕ} {Ω : Type*}
variable {D : Set (Fin d → ℝ)} [mΩ : MeasurableSpace Ω] {μ : Measure Ω}
  {F : ℕ → MeasurableSpace Ω} {T : ℕ} {V : ℕ → Ω → (Fin d → ℝ)} {c : ℕ → Ω → ℝ}
  {J : ℕ → Set Ω} {β : ℕ → ℝ} {B lo hi : ℝ} {m0 : ℕ}
Formal statement
theorem G26.FI.cross_env [IsProbabilityMeasure μ] (I : FI D μ F T V c J β B 0 hi m0) (hhi : 0 ≤ hi)
    {k : ℕ} (hk : 2 ≤ k) (hjP : rdim D ≤ 4 * k) (hB : 2 ^ 20 * (4 * k : ℝ) ≤ B) {b : ℝ}
    (hb : 0 ≤ b) (hβ1 : ∀ n, 1 ≤ β n) (hβb : ∀ n, β n ^ 2 ≤ b ^ 2 * ((n : ℝ) + 1)) {W : ℕ}
    (hW : 1 + 1024 * (4 * k : ℝ) ^ 2 / B ≤ W) {v N m : ℕ} (hm0 : m0 ≤ m) (hmN : m ≤ N)
    (hN : N ≤ T) {lam ρ : ℝ} (hlam : 1 ≤ lam) (hlρ : lam ≤ ρ) {pA F0 : ℝ}
    (hpA : μ.real {ω | ρ < absMax D (frz V (crossA D V c J v lam) N ω)
      (frz c (crossA D V c J v lam) N ω)} ≤ pA)
    (hF0 : ∫ ω, Ff D (frz V (crossA D V c J v lam)) (frz c (crossA D V c J v lam)) (4 * k) m ω ∂μ
      ≤ F0) :
    μ.real {ω | ∃ s, v ≤ s ∧ s ≤ N ∧ ω ∈ J s ∧ lam < negMax D (V s ω) (c s ω)} ≤
      pA + 2 ^ (4 * k) * 4 ^ rdim D * (ρ / lam) ^ rdim D / lam ^ (4 * k) *
        (Hneg k b B * ((N : ℝ) + 1) ^ (3 * k) + (((N : ℝ) + 1) / ((m : ℝ) + 1)) ^ W * F0) := by sorry
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, proof of Lemma G.22, (G.423) (p.165), with Lemma G.25 (G.490) (p.171) and Lemma J.11 (p.211)

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