Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem A.7 — binary information contraction

Open
ZOGlobalLB.Supplement.theorem_A_7

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

information-theorymutual-informationp2o-gran-per-chapterp2o-plan-paperp2o-v1relative-entropy

Let PXYP_{XY}PXY​ be a joint probability law, let Q=PX⊗PYQ=P_X\otimes P_YQ=PX​⊗PY​ be the product of its marginals, and let E⊆X×YE\subseteq\mathcal X\times\mathcal YE⊆X×Y be measurable. Set p=PXY(E)p=P_{XY}(E)p=PXY​(E) and assume q=Q(E)∈(0,1)q=Q(E)\in(0,1)q=Q(E)∈(0,1). Then

I(X;Y)=DKL(PXY∥Q)≥DKL(Ber⁡(p)∥Ber⁡(q))≥plog⁡(1/q)−log⁡2.I(X;Y)=D_{\mathrm{KL}}(P_{XY}\Vert Q) \ge D_{\mathrm{KL}}(\operatorname{Ber}(p)\Vert\operatorname{Ber}(q)) \ge p\log(1/q)-\log 2.I(X;Y)=DKL​(PXY​∥Q)≥DKL​(Ber(p)∥Ber(q))≥plog(1/q)−log2.

The first inequality is binary data processing for the event indicator; logarithms are natural.

Differences from the source:

  • encoding: random elements X,YX,YX,Y and their joint law → the two coordinate projections on the probability space carrying PXYP_{XY}PXY​; 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 [0,∞][0,\infty][0,∞] (coerced to extended reals for comparison) and the last inequality in R\mathbb RR; reason: preserves +∞+\infty+∞ while q∈(0,1)q\in(0,1)q∈(0,1) 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

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