Lemma 10 (proof, last step) —
ProvedQuerySampleRev.kl_half_one_sub_deltakl-divergencelower-boundp2o-gran-per-chapterp2o-plan-paperp2o-v1pricing-queriesrevenue-maximizationsample-complexity
For , the Bernoulli KL divergence between parameters and satisfies
Logarithms are natural. This is the last inequality in the proof of Lemma 10, which converts a weighted binary KL bound into the information requirement.
Formalization Note The binary KL is ExploreFirst.FundIneq.klBer, valued in ; the real right-hand sides enter through (they are nonnegative for ).
Differences from the source:
- encoding: the real-valued identity and inequality → both stated for in with of the real right-hand sides; the factor is cancelled; reason: the right-hand sides are nonnegative for ; same content
Preamble
import Mathlib import Definitions.Def_ExploreFirst_FundIneq_Setting open scoped ENNReal
Formal statement
namespace QuerySampleRev
/-- **The last step of Lemma 10: `KL(1/2, 1 − δ) ≥ (1/16) log(1/δ)`.** Jin, Tang, Wang, Zhang,
*Query-Sample Tradeoffs for Revenue Maximization* (manuscript, sha256 c31ea3d3…), proof of Lemma 10,
p.23 (PDF 25): "The last inequality uses `KL(1/2, 1 − δ) = (1/2) log(1/(4δ(1 − δ)))` and `δ ≤ 1/4`", the
inequality being `W KL(1/2, 1 − δ) ≥ (W/16) log(1/δ)`.
For `0 < δ ≤ 1/4`, the Bernoulli KL divergence `KL(1/2, 1 − δ)` equals `(1/2) log(1/(4δ(1 − δ)))` and is at
least `(1/16) log(1/δ)` (natural logarithms). -/
theorem kl_half_one_sub_delta {δ : ℝ} (hδ0 : 0 < δ) (hδ : δ ≤ 1 / 4) :
ExploreFirst.FundIneq.klBer (1 / 2) (1 - δ) =
ENNReal.ofReal (1 / 2 * Real.log (1 / (4 * δ * (1 - δ)))) ∧
ENNReal.ofReal (1 / 16 * Real.log (1 / δ)) ≤ ExploreFirst.FundIneq.klBer (1 / 2) (1 - δ) := by sorry
end QuerySampleRev
Source
Jin, Tang, Wang, Zhang, Query-Sample Tradeoffs for Revenue Maximization (manuscript, sha256 c31ea3d3…), proof of Lemma 10, p.23 (PDF p.25), last sentence
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.