A short sketch has a hard fibre of sparse inputs
ProvedMomentSearch.Supplement.sparse_sketch_hard_fibreinformation-theorysearch
Let and . A deterministic sketch of the probability simplex has at most messages, where . Then one message has the following property. For every ordered search tree , there is a distribution with sketch , supported on at most positions, such that
The message is fixed before the tree is chosen.
Preamble
import Mathlib import Definitions.Def_MomentSearch_OPT
Formal statement
theorem MomentSearch.Supplement.sparse_sketch_hard_fibre {n q k : ℕ} (hn : 2 ≤ n) (hq : 0 < q)
(X : Type) (σ : (Fin n → ℝ) → X)
(hk : (k : ℝ) ≤ (q : ℝ) / 2 * Real.logb 2 n)
(hfin : (σ '' stdSimplex ℝ (Fin n)).Finite)
(hcard : (σ '' stdSimplex ℝ (Fin n)).ncard ≤ 2^k) :
∃ x ∈ σ '' stdSimplex ℝ (Fin n), ∀ T : MomentSearch.Strategy n,
∃ p ∈ stdSimplex ℝ (Fin n), σ p = x ∧
(Function.support p).ncard ≤ q ∧ Real.logb 2 n / 4 ≤ MomentSearch.cost p T := by sorrySource
Megow, Stein, Verschae, Distributionally Robust Search: The Power of Information and the Limits of Moments, arXiv:2611.04559 (held version, sha256 fbfa4b43350dfaea073a9c0a9a0850a9955ea82082a7163a2db90cc48b9339e3), Theorem 6, p.8 (PDF p.10)