Lemma A.8, p. 71 — D²_H(Rad(μ₁), Rad(μ₂)) ≤ ((μ₁−μ₂)²/2)(1/(2+μ₁+μ₂) + 1/(2−μ₁−μ₂)); ≤ (μ₁−μ₂)² on [−½, ½]; D²_H(Rad(μ), Rad(0)) ≤ ¾μ²
ProvedStatComplexityDM.LinearLB.rad_hellinger_boundshellinger-distanceinformation-theoryp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1rademacher-distribution
Let be the Rademacher distribution on with mean , i.e. and , and let be the squared Hellinger distance. Then:
- For all ,
- For all , .
- For all , .
The third bound is the information property of the hard family in the linear bandit lower bound (Proposition 6.2): a model whose mean differs from that of by is at squared Hellinger distance from it.
Formalization Note In the first bound, a denominator vanishes only when ; there both sides are (Lean's convention gives right-hand side ), so the literal division form is stated. Outcomes are encoded on Bool.
Preamble
import Mathlib import Definitions.Def_FoundationsRL_GeneralDM_Divergences import Definitions.Def_StatComplexityDM_LinearLB_Setting
Formal statement
namespace StatComplexityDM.LinearLB
open FoundationsRL.GeneralDM
/-- Lemma A.8 (arXiv:2112.13487v3, p. 71): squared Hellinger distance between Rademacher
distributions, all three displays. -/
theorem rad_hellinger_bounds :
(∀ μ₁ μ₂ : ℝ, μ₁ ∈ Set.Icc (-1 : ℝ) 1 → μ₂ ∈ Set.Icc (-1 : ℝ) 1 →
hellingerSq (rad μ₁) (rad μ₂) ≤
(μ₁ - μ₂) ^ 2 / 2 * (1 / (2 + μ₁ + μ₂) + 1 / (2 - μ₁ - μ₂))) ∧
(∀ μ₁ μ₂ : ℝ, μ₁ ∈ Set.Icc (-1 / 2 : ℝ) (1 / 2) → μ₂ ∈ Set.Icc (-1 / 2 : ℝ) (1 / 2) →
hellingerSq (rad μ₁) (rad μ₂) ≤ (μ₁ - μ₂) ^ 2) ∧
(∀ μ : ℝ, μ ∈ Set.Icc (-1 : ℝ) 1 →
hellingerSq (rad μ) (rad 0) ≤ 3 / 4 * μ ^ 2) := by sorry
end StatComplexityDM.LinearLB
Source
arXiv:2112.13487v3, Lemma A.8, p. 71
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.