Theorem 28 — randomized sketches of bits with randomized search rules still lose a factor
ProvedMomentSearch.Supplement.theorem_28binary-searchdistributionally-robust-searchinformation-theoretic-lower-boundp2o-gran-per-chapterp2o-plan-paperp2o-v1randomized-algorithmssketching
There is a universal constant such that for every fixed there exists with the following property for all . Let be a random seed on a probability space , independent of the input distribution and of the target. For every seed let be a sketch with and let be the correct deterministic search strategy chosen on message . Then there is a distribution with
The information-theoretic lower bound of Theorem 6 therefore survives randomization of both the sketch and the search rule; the comparator is unchanged.
Differences from the source:
- encoding: E_R[cost_p(S_R(σ_R(p)))] for a random seed R → the Bochner integral ∫ cost_p(S_r(σ_r(p))) dμ(r) over a probability space (Ω, μ), Ω : Type, under the hypothesis that r ↦ cost_p(S_r(σ_r(p))) is measurable for every p ∈ Δ_n; reason: the hypothesis only makes E_R defined; the cost is bounded, so a measurable cost is integrable and the integral is the expectation
- encoding: σ_r : Δ_n → {0,1}^k and S_r(x) a correct deterministic strategy → σ : Ω → (Fin n → ℝ) → (Fin k → Bool) and S : Ω → (Fin k → Bool) → Strategy n; reason: only values on Δ_n are used; the published Strategy type contains exactly the correct deterministic strategies
- reading: γ_rand > 0 is a universal constant → ∃ γ > 0 chosen before ε, n₀ and n; reason: universal means independent of ε, n, k and the randomized pair; only n₀ depends on ε
Preamble
import Mathlib import Definitions.Def_MomentSearch_OPT
Formal statement
namespace MomentSearch.Supplement
open MomentSearch MeasureTheory
/-- **Theorem 28** (Randomized information-theoretic lower bound) (Megow, Stein, Verschae, *Distributionally Robust Search: The Power of Information and the Limits of Moments*, arXiv:2611.04559 (held version, sha256 fbfa4b43…), Theorem 28, p.36
(PDF p.38)).
There is a universal constant `γ_rand > 0` such that for every fixed `ε ∈ (0, 1/4)` there is
`n₀(ε)` with the following property for all `n ≥ n₀(ε)`. Let `R` be a random seed on a
probability space `(Ω, μ)`, independent of the input distribution and the target; for each seed
`r` let `σ_r : Δ_n → {0,1}^k` be a sketch with `k ≤ ½ n^ε log₂ n`, and `S_r(x)` the correct
deterministic search strategy chosen on message `x`. Then some distribution `p ∈ Δ_n` satisfies
`E_R[cost_p(S_R(σ_R(p)))] ≥ (γ_rand/ε) · OPT(p)`.
**Formalization Note.** `E_R` is the Bochner integral over `μ`. The hypothesis that
`r ↦ cost_p(S_r(σ_r(p)))` is measurable for every `p ∈ Δ_n` only makes the expectation defined: the
cost is bounded (by `n` times the depth of a tree on `n` vertices), so a measurable cost is
integrable. `p` is chosen after the randomized pair `(σ, S)` and does not depend on the seed.
Strategies are the published `MomentSearch.Strategy` (correct by construction). -/
theorem theorem_28 :
∃ γ : ℝ, 0 < γ ∧
∀ ε : ℝ, 0 < ε → ε < 1 / 4 →
∃ n₀ : ℕ, ∀ n : ℕ, n₀ ≤ n →
∀ (k : ℕ), (k : ℝ) ≤ 1 / 2 * (n : ℝ) ^ ε * Real.logb 2 n →
∀ (Ω : Type) [MeasurableSpace Ω] (μ : Measure Ω) [IsProbabilityMeasure μ]
(σ : Ω → (Fin n → ℝ) → (Fin k → Bool)) (S : Ω → (Fin k → Bool) → Strategy n),
(∀ p ∈ stdSimplex ℝ (Fin n), Measurable (fun r => cost p (S r (σ r p)))) →
∃ p ∈ stdSimplex ℝ (Fin n),
γ / ε * OPT p ≤ ∫ r, cost p (S r (σ r p)) ∂μ := by sorry
end MomentSearch.Supplement
Source
Megow, Stein, Verschae, Distributionally Robust Search: The Power of Information and the Limits of Moments, arXiv:2611.04559 (held version, sha256 fbfa4b43350dfaea073a9c0a9a0850a9955ea82082a7163a2db90cc48b9339e3), Theorem 28, p.36 (PDF p.38)