Theorem A.7 — binary information contraction
OpenZOGlobalLB.Supplement.theorem_A_7information-theorymutual-informationp2o-gran-per-chapterp2o-plan-paperp2o-v1relative-entropy
Let be a joint probability law, let be the product of its marginals, and let be measurable. Set and assume . Then
The first inequality is binary data processing for the event indicator; logarithms are natural.
Differences from the source:
- encoding: random elements and their joint law → the two coordinate projections on the probability space carrying ; reason: their joint and marginal laws are definitionally the same measures
- encoding: possibly infinite relative entropy followed by finite Bernoulli terms → the first two divergences in (coerced to extended reals for comparison) and the last inequality in ; reason: preserves while makes the Bernoulli expression finite
Preamble
import Mathlib import Definitions.Def_ThompsonTutorial_InfoRatio_mutualInfo import Definitions.Def_RegretBandits_Stochastic_klBernoulli open MeasureTheory ProbabilityTheory open scoped ENNReal EReal universe u v
Formal statement
namespace ZOGlobalLB
namespace Supplement
/-- **Theorem A.7 (Binary information contraction).** Xia, Yuan,
*On Global Joint Lower Bounds in Zeroth-Order Nonconvex Optimization*, arXiv:2610.19652,
Theorem A.7, p.36.
For a joint probability law `PXY`, its product of marginals `Q`, and a measurable event `E`
with `q = Q(E)` strictly between zero and one, mutual information equals
`D_KL(PXY ‖ Q)`, which is at least the Bernoulli divergence of the event probabilities, and
that divergence is at least `p log(1/q) - log 2`.
**Formalization Note.** Mutual information and the first two divergence terms retain `+∞` in
`ℝ≥0∞`. The final Bernoulli quantities are finite real numbers because `q ∈ (0,1)`. All logarithms
are natural. The random pair is represented by the identity coordinates on the joint-law space. -/
theorem theorem_A_7 (X : Type u) (Y : Type v) [MeasurableSpace X] [MeasurableSpace Y]
(PXY : Measure (X × Y)) [IsProbabilityMeasure PXY]
(E : Set (X × Y)) (hE : MeasurableSet E) :
let Q := (PXY.map Prod.fst).prod (PXY.map Prod.snd)
let p := (PXY E).toReal
let q := (Q E).toReal
0 < q → q < 1 →
(ThompsonTutorial.InfoRatio.mutualInfo PXY Prod.fst Prod.snd : EReal) =
(InformationTheory.klDiv PXY Q : EReal) ∧
(ENNReal.ofReal (RegretBandits.Stochastic.klBern p q) : EReal) ≤
(InformationTheory.klDiv PXY Q : EReal) ∧
p * Real.log (1 / q) - Real.log 2 ≤ RegretBandits.Stochastic.klBern p q := by sorry
end Supplement
end ZOGlobalLB
Source
Xia, Yuan, On Global Joint Lower Bounds in Zeroth-Order Nonconvex Optimization, arXiv:2610.19652, Theorem A.7, p.36