Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Absolute envelope of a field-interface affine field: E[1_J max_D |Z_n|^P] = O(n^P)

Proved
G26.FI.absMax_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,ℓ,h,0)\mathrm{FI}(\beta,B,\ell,h,0)FI(β,B,ℓ,h,0) holds with −2≤ℓ-2\le\ell−2≤ℓ and h≤2h\le2h≤2. Let P≥4P\ge4P≥4 be even with j≤Pj\le Pj≤P, 220P≤B2^{20}P\le B220P≤B, βn>0\beta_n>0βn​>0 and βn≤b(n+1)\beta_n\le b(n+1)βn​≤b(n+1) for all nnn, and suppose the field starts at zero: ∫DZ0P dσ=0\int_DZ_0^P\,d\sigma=0∫D​Z0P​dσ=0 for every ω\omegaω. Then for every n≤Tn\le Tn≤T,

E[1Jn(max⁡u∈D∣Zn(u)∣)P]≤2P 4j Cabs(P,b,B) (n+1)P,\mathbb E\Big[\mathbf 1_{J_n}\big(\max_{u\in D}|Z_n(u)|\big)^P\Big]\le2^P\,4^{j}\,C_{\rm abs}(P,b,B)\,(n+1)^P,E[1Jn​​(u∈Dmax​∣Zn​(u)∣)P]≤2P4jCabs​(P,b,B)(n+1)P,

where Cabs(P,b,B)=max⁡{0,Kabs(P,b,B)/(P−3−1152P2/B)}C_{\rm abs}(P,b,B)=\max\{0,K_{\rm abs}(P,b,B)/(P-3-1152P^2/B)\}Cabs​(P,b,B)=max{0,Kabs​(P,b,B)/(P−3−1152P2/B)} (Cabs P b B 0).

The absolute integral moment Gn=∫D∣Zn∣PdσG_n=\int_D|Z_n|^Pd\sigmaGn​=∫D​∣Zn​∣Pdσ satisfies the recurrence (G.488), whose solution starting at zero is O(nP)O(n^P)O(nP); Lemma J.11 converts the integral moment of the affine function into its maximum over DDD at the cost 2P4j2^P4^j2P4j. This is the envelope E[max⁡∣Xs∣P]≤RPsP\mathbb E[\max|X_s|^P]\le R^Ps^PE[max∣Xs​∣P]≤RPsP of Lemmas G.15, G.28 and G.30.

Formalization Note Rounds are 0-based; the constants are explicit.

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.absMax_env [IsProbabilityMeasure μ] (I : FI D μ F T V c J β B lo hi 0)
    (hlo : -2 ≤ lo) (hhi : hi ≤ 2) {P : ℕ} (hP : 4 ≤ P) (hev : Even P) (hjP : rdim D ≤ P)
    (hB : 2 ^ 20 * (P : ℝ) ≤ B) {b : ℝ} (hβ : ∀ n, 0 < β n)
    (hβb : ∀ n, β n ≤ b * ((n : ℝ) + 1)) (h0 : ∀ ω, Gf D V c P 0 ω = 0) {n : ℕ} (hn : n ≤ T) :
    ∫ ω, (J n).indicator (fun ω => absMax D (V n ω) (c n ω) ^ P) ω ∂μ ≤
      2 ^ P * 4 ^ rdim D * Cabs P b B 0 * ((n : ℝ) + 1) ^ P := 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, Lemma G.25 (G.488) and the bound E[G_s] ≤ C_G s^P (p.170), combined with 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