Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Run-level processes for Lemma G.26: shifted and normalized loss-difference fields, the projective body, and compensated scalar variables

Definition
IAFTRL_G26_run

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

bandit-algorithmslinear-banditsonline-learning

This bundle defines the processes built from a GIA-FTRL run RRR (cumulative loss estimate Sn=∑j<nθ^jS_n=\sum_{j<n}\hat\theta_jSn​=∑j<n​θ^j​, corrupted loss vectors θj\theta_jθj​) that are fed into the abstract interfaces.

  • Fx R T n is the run filtration Gn\mathcal G_nGn​ for n<Tn<Tn<T, extended by the full σ\sigmaσ-algebra at n=Tn=Tn=T.
  • An=∑j<n∥θj−θ∥AA_n=\sum_{j<n}\|\theta_j-\theta\|_{\mathcal A}An​=∑j<n​∥θj​−θ∥A​ (Acum), and cW is the shift of the remaining-budget field Wn(a)=(a−a∗)⊤Sn−2(C−An)W_n(a)=(a-a^*)^\top S_n-2(C-A_n)Wn​(a)=(a−a∗)⊤Sn​−2(C−An​) of Lemma G.30.
  • Sharp 𝒜 ℬ θ astar bundles the standing hypotheses of the sharp instance: 1≤d1\le d1≤d, compactness, B\mathcal BB generates A\mathcal AA, A\mathcal AA in the unit ball and spanning, dim⁡K≥1\dim\mathcal K\ge1dimK≥1, ∥θ∥A≤1\|\theta\|_{\mathcal A}\le1∥θ∥A​≤1, a∗a^*a∗ the unique optimal action, and sharpness. H.sig is a chosen sharpness modulus ς\varsigmaς, Δ(a)=(a−a∗)⊤θ\Delta(a)=(a-a^*)^\top\thetaΔ(a)=(a−a∗)⊤θ is gap.
  • The projective body of Lemma G.16:
Uθ={Δ(a)−1(a−a∗):a∈K∖{a∗}}‾,Dθ={λu:λ∈[0,1], u∈Uθ}.U_\theta=\overline{\big\{\Delta(a)^{-1}(a-a^*):a\in\mathcal K\setminus\{a^*\}\big\}},\qquad D_\theta=\{\lambda u:\lambda\in[0,1],\ u\in U_\theta\}.Uθ​={Δ(a)−1(a−a∗):a∈K∖{a∗}}​,Dθ​={λu:λ∈[0,1], u∈Uθ​}.

Lam1 is a constant Λ1\Lambda_1Λ1​ for the projective extension (G.306), and kb =ς−2+ς−1+1=\varsigma^{-2}+\varsigma^{-1}+1=ς−2+ς−1+1.

  • goodS ℬ e j* n S states that the atom j∗j^*j∗ of a∗a^*a∗ is the strict minimizer of the penalized reference problem (3.4) at round nnn and score SSS. js is the index of a∗a^*a∗ among the first-occurrence atoms, hs its prior penalty, and D0 the sum of the inverse S\mathcal SS-distances of the earlier atoms.
  • cN is the shift −Λ(C−An)-\Lambda(C-A_n)−Λ(C−An​) of the normalized field Wnu(u)=u⊤Sn−Λ(C−An)W^u_n(u)=u^\top S_n-\Lambda(C-A_n)Wnu​(u)=u⊤Sn​−Λ(C−An​) on DθD_\thetaDθ​. JN m n is the event that the reference was strictly a∗a^*a∗ at every round in [m,n][m,n][m,n].
  • Compensated scalar variables: En(w)=∑j<nw⊤(θj−θ)E_n(w)=\sum_{j<n}w^\top(\theta_j-\theta)En​(w)=∑j<n​w⊤(θj​−θ) (Ecor),
YnF(a)=(a−a∗)⊤Sn−En(a−a∗)+2C+2τn (YF),Yn†(u)=u⊤Sn−En(u)+ΛC+2τn (YN),Y^F_n(a)=(a-a^*)^\top S_n-E_n(a-a^*)+2C+2\tau_n\ (\texttt{YF}),\qquad Y^\dagger_n(u)=u^\top S_n-E_n(u)+\Lambda C+2\tau_n\ (\texttt{YN}),YnF​(a)=(a−a∗)⊤Sn​−En​(a−a∗)+2C+2τn​ (YF),Yn†​(u)=u⊤Sn​−En​(u)+ΛC+2τn​ (YN),

with alive events IW (no negative crossing of WWW since m0m_0m0​) and IN (reference a∗a^*a∗ and no normalized negative crossing since mmm), as in (G.523), (G.597) and (G.636).

  • Constants: kk d =1024(d+1)=1024(d+1)=1024(d+1) (moment order P=4kP=4kP=4k), cK d (the absolute-envelope constant), the buffer tauB z s =(s+1)7/8+4z=(s+1)^{7/8}+4z=(s+1)7/8+4z, and root8 x =x1/8=x^{1/8}=x1/8.

These objects instantiate the interfaces of the body bundle for the run-level estimates in Lemmas G.26–G.30.

Definition code
import Mathlib
import Definitions.Def_IAFTRL_LinEnv
import Definitions.Def_IAFTRL_GIAFTRL
import Definitions.Def_IAFTRL_G26_body

-- ===== Solutions.G26.RunK =====

/-! ### The loss-difference field on `K` satisfies the field interface (Lemma G.10) -/

open MeasureTheory ProbabilityTheory Set IAFTRL Matrix

namespace G26R

open G26

variable {d : ℕ} {𝒜 ℬ : Set (Fin d → ℝ)} {e : ℕ → Fin d → ℚ}

section

variable (hd : 1 ≤ d) (hℬ : IsCompact ℬ) (hgen : IsGenerator 𝒜 ℬ) (hspan : Submodule.span ℝ 𝒜 = ⊤)
include hd hℬ hgen hspan

end

end G26R

namespace G26R

open G26

variable {d : ℕ} {𝒜 ℬ : Set (Fin d → ℝ)} {e : ℕ → Fin d → ℚ}
variable {Ω : Type*} [mΩ : MeasurableSpace Ω] {P : Measure Ω} [IsProbabilityMeasure P]
  {T : ℕ} {R : GRun d Ω}

/-- the filtration extended by `mΩ` at the horizon -/
def Fx (R : GRun d Ω) (T : ℕ) (n : ℕ) : MeasurableSpace Ω := if n < T then R.G n else mΩ

end G26R


-- ===== Solutions.G26.RunW =====

/-! ### The remaining-budget shifted field on `K` (Lemma G.30) -/

open MeasureTheory ProbabilityTheory Set IAFTRL Matrix

namespace G26R

open G26

variable {d : ℕ}

/-- the realized cumulative corruption `A_n = Σ_{j<n} ‖θ_j − θ‖_𝒜` -/
noncomputable def Acum {Ω : Type*} (𝒜 : Set (Fin d → ℝ)) (R : GRun d Ω) (θ : Fin d → ℝ) (n : ℕ)
    (ω : Ω) : ℝ :=
  ∑ j ∈ Finset.range n, setNorm 𝒜 (R.θs j ω - θ)

/-- the shift of the remaining-budget field -/
noncomputable def cW {Ω : Type*} (𝒜 : Set (Fin d → ℝ)) (R : GRun d Ω) (θ astar : Fin d → ℝ) (C : ℝ)
    (n : ℕ) (ω : Ω) : ℝ :=
  -(astar ⬝ᵥ R.cumEst n ω) - 2 * (C - Acum 𝒜 R θ n ω)

variable {𝒜 ℬ : Set (Fin d → ℝ)} {e : ℕ → Fin d → ℚ}
variable {Ω : Type*} [mΩ : MeasurableSpace Ω] {P : Measure Ω} [IsProbabilityMeasure P]
  {T : ℕ} {R : GRun d Ω}

end G26R

namespace G26R

open G26

variable {d : ℕ} {𝒜 ℬ : Set (Fin d → ℝ)} {e : ℕ → Fin d → ℚ}
variable {Ω : Type*} [mΩ : MeasurableSpace Ω] {P : Measure Ω} [IsProbabilityMeasure P]
  {T : ℕ} {R : GRun d Ω}

end G26R


-- ===== Solutions.G26.Geo =====

/-! ### The projective body of normalized directions (Lemma G.16) -/

open MeasureTheory ProbabilityTheory Set IAFTRL

namespace G26G

open G26

variable {d : ℕ}

/-- the standing hypotheses of the sharp corrupted setting -/
structure Sharp (𝒜 ℬ : Set (Fin d → ℝ)) (θ astar : Fin d → ℝ) : Prop where
  hd : 1 ≤ d
  h𝒜 : IsCompact 𝒜
  hℬ : IsCompact ℬ
  hgen : IsGenerator 𝒜 ℬ
  hball : ∀ a ∈ 𝒜, a ⬝ᵥ a ≤ 1
  hspan : Submodule.span ℝ 𝒜 = ⊤
  hk : 1 ≤ kdim ℬ
  hθ : setNorm 𝒜 θ ≤ 1
  hastar : astar ∈ 𝒜
  huniq : ∀ a ∈ 𝒜, a ≠ astar → astar ⬝ᵥ θ < a ⬝ᵥ θ
  hsharp : IsSharp 𝒜 θ astar

variable {𝒜 ℬ : Set (Fin d → ℝ)} {θ astar : Fin d → ℝ}

/-- the gap `Δ(a) = (a − a*)ᵀθ` -/
def gap (θ astar a : Fin d → ℝ) : ℝ := (a - astar) ⬝ᵥ θ

namespace Sharp

variable (H : Sharp 𝒜 ℬ θ astar)
include H

/-- the sharpness modulus -/
noncomputable def sig : ℝ := Classical.choose H.hsharp

end Sharp

/-- the normalized direction of an action -/
noncomputable def ndir (θ astar a : Fin d → ℝ) : Fin d → ℝ := (gap θ astar a)⁻¹ • (a - astar)

/-- normalized directions of positive-gap actions -/
def U0 (ℬ : Set (Fin d → ℝ)) (θ astar : Fin d → ℝ) : Set (Fin d → ℝ) :=
  ndir θ astar '' (Kset ℬ \ {astar})

/-- the projective body `U_θ` -/
def UT (ℬ : Set (Fin d → ℝ)) (θ astar : Fin d → ℝ) : Set (Fin d → ℝ) := closure (U0 ℬ θ astar)

/-- the cone body `D_θ = {λu : λ ∈ [0,1], u ∈ U_θ}` -/
def DT (ℬ : Set (Fin d → ℝ)) (θ astar : Fin d → ℝ) : Set (Fin d → ℝ) :=
  (fun q : ℝ × (Fin d → ℝ) => q.1 • q.2) '' (Icc (0 : ℝ) 1 ×ˢ UT ℬ θ astar)

namespace Sharp

variable (H : Sharp 𝒜 ℬ θ astar)
include H

end Sharp

end G26G


-- ===== Solutions.G26.RefGood =====

/-! ### A measurable sufficient condition for the reference to be `a*` -/

open MeasureTheory ProbabilityTheory Set IAFTRL

namespace G26G

open G26

variable {d : ℕ} {𝒜 ℬ : Set (Fin d → ℝ)} {e : ℕ → Fin d → ℚ} {θ astar : Fin d → ℝ}

/-- strict optimality of the atom `j*` in the penalized reference problem (3.4) -/
def goodS (ℬ : Set (Fin d → ℝ)) (e : ℕ → Fin d → ℚ) (js : ℕ) (n : ℕ) (S : Fin d → ℝ) : Prop :=
  ∀ i ∈ Jset ℬ e, i ≠ js →
    cand ℬ e js ⬝ᵥ S + gbeta d n * hPen ℬ e js < cand ℬ e i ⬝ᵥ S + gbeta d n * hPen ℬ e i

namespace Sharp

variable (H : Sharp 𝒜 ℬ θ astar) (he : Function.Surjective e)
include H he

omit H he in
/-- the index of `a*` among the reference atoms -/
noncomputable def js (ℬ : Set (Fin d → ℝ)) (e : ℕ → Fin d → ℚ) (astar : Fin d → ℝ) : ℕ :=
  open Classical in
  if h : ∃ m ∈ Jset ℬ e, cand ℬ e m = astar then Classical.choose h else 0

/-- the prior penalty of `a*` -/
noncomputable def hs (_H : Sharp 𝒜 ℬ θ astar) (_he : Function.Surjective e) : ℝ :=
  hPen ℬ e (js ℬ e astar)

open Classical in
/-- the inverse distances of the earlier atoms -/
noncomputable def D0 (_H : Sharp 𝒜 ℬ θ astar) (_he : Function.Surjective e) : ℝ :=
  ∑ i ∈ (Finset.range (js ℬ e astar)).filter (· ∈ Jset ℬ e), (sNorm ℬ (cand ℬ e i - astar))⁻¹

end Sharp

end G26G


-- ===== Solutions.G26.RunN =====

/-! ### The normalized field on the cone body satisfies the field interface (Lemmas G.17, G.28) -/

open MeasureTheory ProbabilityTheory Set IAFTRL Matrix

namespace G26G

open G26 G26R

variable {d : ℕ} {𝒜 ℬ : Set (Fin d → ℝ)} {e : ℕ → Fin d → ℚ} {θ astar : Fin d → ℝ}

namespace Sharp

variable (H : Sharp 𝒜 ℬ θ astar)
include H

omit H in
/-- the constant of the projective extension (G.306) -/
noncomputable def Lam1 (ℬ : Set (Fin d → ℝ)) (θ astar : Fin d → ℝ) : ℝ :=
  open Classical in
  if h : ∃ Λ1 : ℝ, 0 < Λ1 ∧ ∀ (w : Fin d → ℝ) (M : ℝ),
      (∀ a ∈ Kset ℬ, |(a - astar) ⬝ᵥ w| ≤ M) → ∀ u ∈ DT ℬ θ astar, |u ⬝ᵥ w| ≤ Λ1 * M
  then Classical.choose h else 1

/-- the variance constant of the normalized field -/
noncomputable def kb : ℝ := H.sig⁻¹ ^ 2 + H.sig⁻¹ + 1

end Sharp

end G26G

namespace G26G

open G26 G26R

variable {d : ℕ} {𝒜 ℬ : Set (Fin d → ℝ)} {e : ℕ → Fin d → ℚ} {θ astar : Fin d → ℝ}
variable {Ω : Type*} [mΩ : MeasurableSpace Ω] {P : Measure Ω} [IsProbabilityMeasure P]
  {T : ℕ} {R : GRun d Ω}

/-- the remaining-budget shift of the normalized field -/
noncomputable def cN (𝒜 : Set (Fin d → ℝ)) (R : GRun d Ω) (θ : Fin d → ℝ) (l C : ℝ) (n : ℕ)
    (ω : Ω) : ℝ :=
  -(l * (C - Acum 𝒜 R θ n ω))

/-- the reference has been `a*` (strictly) at every round of `[m, n]` -/
def JN (ℬ : Set (Fin d → ℝ)) (e : ℕ → Fin d → ℚ) (js : ℕ) (R : GRun d Ω) (m n : ℕ) : Set Ω :=
  {ω | ∀ j, m ≤ j → j ≤ n → goodS ℬ e js (j + 1) (R.cumEst j ω)}

namespace Sharp

variable (H : Sharp 𝒜 ℬ θ astar)
include H

end Sharp

end G26G


-- ===== Solutions.G26.RunSI =====

/-! ### Compensated per-action scalar processes (Lemma G.29, (G.635)–(G.641)) -/

open MeasureTheory ProbabilityTheory Set IAFTRL Matrix

namespace G26G

open G26 G26R

variable {d : ℕ} {𝒜 ℬ : Set (Fin d → ℝ)} {e : ℕ → Fin d → ℚ} {θ astar : Fin d → ℝ}
variable {Ω : Type*} [mΩ : MeasurableSpace Ω] {P : Measure Ω} [IsProbabilityMeasure P]
  {T : ℕ} {R : GRun d Ω}

/-- the corruption accumulated in the direction `w` -/
noncomputable def Ecor (R : GRun d Ω) (θ w : Fin d → ℝ) (n : ℕ) (ω : Ω) : ℝ :=
  ∑ j ∈ Finset.range n, w ⬝ᵥ (R.θs j ω - θ)

/-- the compensated positive variable of an action, (G.636) -/
noncomputable def YF (R : GRun d Ω) (θ astar : Fin d → ℝ) (C : ℝ) (τ : ℕ → ℝ) (a : Fin d → ℝ)
    (n : ℕ) (ω : Ω) : ℝ :=
  (a - astar) ⬝ᵥ R.cumEst n ω - Ecor R θ (a - astar) n ω + 2 * C + 2 * τ n

/-- no negative crossing of the remaining-budget field since `m0` -/
def IW (𝒜 ℬ : Set (Fin d → ℝ)) (R : GRun d Ω) (θ astar : Fin d → ℝ) (C : ℝ) (τ : ℕ → ℝ)
    (m0 n : ℕ) : Set Ω :=
  {ω | ∀ j, m0 ≤ j → j ≤ n → negMax (Kset ℬ) (R.cumEst j ω) (cW 𝒜 R θ astar C j ω) ≤ τ j}

namespace Sharp

variable (H : Sharp 𝒜 ℬ θ astar)
include H

end Sharp

end G26G


-- ===== Solutions.G26.RunSIN =====

/-! ### Compensated normalized pointwise variables (Lemma G.28, (G.595)–(G.601)) -/

open MeasureTheory ProbabilityTheory Set IAFTRL Matrix

namespace G26G

open G26 G26R

variable {d : ℕ} {𝒜 ℬ : Set (Fin d → ℝ)} {e : ℕ → Fin d → ℚ} {θ astar : Fin d → ℝ}
variable {Ω : Type*} [mΩ : MeasurableSpace Ω] {P : Measure Ω} [IsProbabilityMeasure P]
  {T : ℕ} {R : GRun d Ω}

/-- the compensated normalized variable of a direction, (G.596) -/
noncomputable def YN (R : GRun d Ω) (θ : Fin d → ℝ) (l C : ℝ) (τ : ℕ → ℝ) (u : Fin d → ℝ)
    (n : ℕ) (ω : Ω) : ℝ :=
  u ⬝ᵥ R.cumEst n ω - Ecor R θ u n ω + l * C + 2 * τ n

/-- references strictly `a*` and no normalized negative crossing since `m` -/
def IN (𝒜 ℬ : Set (Fin d → ℝ)) (e : ℕ → Fin d → ℚ) (js : ℕ) (R : GRun d Ω) (θ astar : Fin d → ℝ)
    (l C : ℝ) (τ : ℕ → ℝ) (m n : ℕ) : Set Ω :=
  JN ℬ e js R m n ∩
    {ω | ∀ j, m ≤ j → j ≤ n → negMax (DT ℬ θ astar) (R.cumEst j ω) (cN 𝒜 R θ l C j ω) ≤ τ j}

namespace Sharp

variable (H : Sharp 𝒜 ℬ θ astar)
include H

end Sharp

end G26G


-- ===== Solutions.G26.RunEnv =====

/-! ### Envelopes of the run fields: absolute maxima and block crossings (Lemmas G.15, G.30) -/

open MeasureTheory ProbabilityTheory Set IAFTRL Matrix J11

namespace 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 : ℕ}

end G26

namespace G26G

open G26 G26R

variable {d : ℕ} {𝒜 ℬ : Set (Fin d → ℝ)} {e : ℕ → Fin d → ℚ} {θ astar : Fin d → ℝ}
variable {Ω : Type*} [mΩ : MeasurableSpace Ω] {P : Measure Ω} [IsProbabilityMeasure P]
  {T : ℕ} {R : GRun d Ω}

/-- the moment order `P = 4k`, `k = 1024(d+1)` -/
@[irreducible] def kk (d : ℕ) : ℕ := 1024 * (d + 1)

/-- the absolute-envelope constant -/
noncomputable def cK (d : ℕ) : ℝ :=
  2 ^ (4 * kk d) * 4 ^ d * Cabs (4 * kk d) (16 * d + 1) (gB d) 0

namespace Sharp

variable (H : Sharp 𝒜 ℬ θ astar)
include H

end Sharp

end G26G


-- ===== Solutions.G26.Params =====

/-! ### Thresholds: buffers `τ_s = (s+1)^{7/8} + 4z` and logarithmic gap cutoffs -/

open MeasureTheory ProbabilityTheory Set IAFTRL Matrix

namespace G26G

open G26 G26R

/-- the moving buffer with plateau `z` -/
noncomputable def tauB (z : ℝ) (s : ℕ) : ℝ := ((s : ℝ) + 1) ^ ((7 : ℝ) / 8) + 4 * z

/-- an eighth root -/
noncomputable def root8 (x : ℝ) : ℝ := Real.sqrt (Real.sqrt (Real.sqrt x))

end G26G

namespace G26G

end G26G

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.10 (p.138), Lemma G.16 (p.153), Lemma G.17 (p.154), Definition G.8 (p.173), Lemmas G.28–G.30 (pp.178–188), (G.595)–(G.601), (G.635)–(G.641)

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