Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma G.11 — comparison law of the convolution reference

Proved
IAFTRL.lemma_G_11

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

bandit-algorithmslinear-banditsonline-learning

Setting. Let A⊆Bd\mathcal A\subseteq\mathbb B^dA⊆Bd be a compact spanning action set and B\mathcal BB a compact generator of it, with K=Conv(B)\mathcal K=\mathrm{Conv}(\mathcal B)K=Conv(B) of affine dimension k≥1k\ge1k≥1. Let μ=∑j∈Jπjδbj+ωμμ16\mu=\sum_{j\in J}\pi_j\delta_{b_j}+\omega_\mu\mu_{16}μ=∑j∈J​πj​δbj​​+ωμ​μ16​ be the reference measure (3.3) of GIA-FTRL. Here μ16\mu_{16}μ16​ is the law of the mean of 161616 i.i.d. points drawn from the normalized kkk-dimensional Hausdorff measure on K\mathcal KK.

Claim. For every u∈Ku\in\mathcal Ku∈K and every integer T≥1T\ge1T≥1 there is a probability measure qu,Tq_{u,T}qu,T​ supported on K\mathcal KK with qu,T≪μq_{u,T}\ll\muqu,T​≪μ and

DKL(qu,T,μ)=∫log⁡dqu,Tdμ dqu,T≤log⁡2+16klog⁡T,D_{\mathrm{KL}}(q_{u,T},\mu)=\int\log\frac{dq_{u,T}}{d\mu}\,dq_{u,T}\le\log2+16k\log T,DKL​(qu,T​,μ)=∫logdμdqu,T​​dqu,T​≤log2+16klogT, ∣(∫x qu,T(dx)−u) ⁣⊤ϑ∣≤2Tfor every ∥ϑ∥A≤1.\Big|\Big(\int x\,q_{u,T}(dx)-u\Big)^{\!\top}\vartheta\Big|\le\frac2T\quad\text{for every }\|\vartheta\|_{\mathcal A}\le1 .​(∫xqu,T​(dx)−u)⊤ϑ​≤T2​for every ∥ϑ∥A​≤1.

The log-density is integrable.

Idea. Pass to the shrunken copy Kε=u+ε(K−u)\mathcal K_\varepsilon=u+\varepsilon(\mathcal K-u)Kε​=u+ε(K−u) with ε=1/T\varepsilon=1/Tε=1/T. Its kkk-dimensional volume fraction is εk\varepsilon^kεk. Hence μ16(Kε)≥ε16k\mu_{16}(\mathcal K_\varepsilon)\ge\varepsilon^{16k}μ16​(Kε​)≥ε16k, and ωμ≥1/2\omega_\mu\ge1/2ωμ​≥1/2.

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

open MeasureTheory

/-- **Lemma G.11 (Adversarial comparator cost of the convolution reference).** Zhao–Tan,
*Best-of-Both-Worlds FTRL for Linear Bandits* (STOC submission version), Lemma G.11, p.143:
"For each `u ∈ 𝒦` and integer `T ≥ 1` there is a probability `q_{u,T}` such that
`D_KL(q_{u,T}, µ) ≤ log 2 + mk log T`, `|(∫ x q_{u,T}(dx) − u)ᵀϑ| ≤ 2/T` for every `‖ϑ‖_𝒜 ≤ 1`",
with `m = 16` and `µ` the reference measure (3.3).

`D_KL(q, µ)` is written as `∫ log (dq/dµ) dq`, with `q ≪ µ` and the log-density integrable; the
comparison law is supported on `𝒦 = Conv ℬ`. -/
theorem lemma_G_11 {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 ℬ)
    (u : Fin d → ℝ) (hu : u ∈ Kset ℬ) (T : ℕ) (hT : 1 ≤ T) :
    ∃ q : Measure (Fin d → ℝ), IsProbabilityMeasure q ∧ q (Kset ℬ)ᶜ = 0 ∧ q ≪ refMu ℬ e ∧
      Integrable (fun x => Real.log (q.rnDeriv (refMu ℬ e) x).toReal) q ∧
      ∫ x, Real.log (q.rnDeriv (refMu ℬ e) x).toReal ∂q ≤
        Real.log 2 + 16 * (kdim ℬ : ℝ) * Real.log T ∧
      ∀ ϑ : Fin d → ℝ, setNorm 𝒜 ϑ ≤ 1 →
        |((fun i => ∫ x, x i ∂q) - u) ⬝ᵥ ϑ| ≤ 2 / T := 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.2, Lemma G.11, pp. 143–144

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