Lemma G.11 — comparison law of the convolution reference
ProvedIAFTRL.lemma_G_11bandit-algorithmslinear-banditsonline-learning
Setting. Let be a compact spanning action set and a compact generator of it, with of affine dimension . Let be the reference measure (3.3) of GIA-FTRL. Here is the law of the mean of i.i.d. points drawn from the normalized -dimensional Hausdorff measure on .
Claim. For every and every integer there is a probability measure supported on with and
The log-density is integrable.
Idea. Pass to the shrunken copy with . Its -dimensional volume fraction is . Hence , and .
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