Theorem 8 — quantile sketches: , and quantiles give an -approximation with bits
ProvedMomentSearch.Supplement.theorem_8binary-searchdistributionally-robust-searchkolmogorov-distancep2o-gran-per-chapterp2o-plan-paperp2o-v1quantilessketching
Let .
- For every integer and every , let be the -quantiles of and let place mass at each (adding masses when quantiles repeat). Then and
- There are absolute constants such that for every and : the -quantile sketch takes finitely many values on , at most of them for some integer (a sketch of bits); and for every , Coarse Greedy with parameter and nominal distribution built from the quantiles of (for any choice of -medians) satisfies
This shows that the information-theoretic lower bound of Theorem 6 is tight up to constant factors, both in the number of bits and in the approximation ratio.
Differences from the source:
- encoding: the q-quantiles of p suffice to construct a distribution π → π := quantileDist n q (quantileSketch n q p), a function of the quantile tuple alone; reason: this is the paper's construction (mass 1/q at each quantile, p.9 and p.18)
- reading: a sketch of O(n^ε log n) bits → the image of the quantile sketch on Δ_n is finite with at most 2^b elements, for an integer b ≤ C₁ n^ε log₂ n, C₁ absolute; reason: §3.1 (p.7): encodable with b bits means |σ(Δ_n)| ≤ 2^b
- reading: guarantees an O(1/ε)-approximation via Coarse Greedy → ∃ C₂ > 0 absolute: for every p ∈ Δ_n and every median rule, cost_p of Coarse Greedy with parameter ε and nominal π(quantiles of p) is ≤ (C₂/ε)·OPT(p); reason: the proof (p.18) applies Theorem 5 to the ball of radius n^{−ε} around π; Coarse Greedy fixes no median, so every rule is covered
- encoding: distribution p on [n]₀ (part 1) → n ≥ 2 as a hypothesis; reason: the paper's standing assumption n ≥ 2 (§2.1)
Preamble
import Mathlib import Definitions.Def_MomentSearch_OPT import Definitions.Def_MomentSearch_Supplement_cdf import Definitions.Def_MomentSearch_Supplement_coarseGreedy import Definitions.Def_MomentSearch_Supplement_quantileDist
Formal statement
namespace MomentSearch.Supplement
open MomentSearch
/-- **Theorem 8** (Quantile upper bound) (Megow, Stein, Verschae, *Distributionally Robust Search: The Power of Information and the Limits of Moments*, arXiv:2611.04559 (held version, sha256 fbfa4b43…), Theorem 8, p.9 (PDF p.11); restated with proof
App. B.2, p.18 (PDF p.20)).
1. For every `n ≥ 2`, every integer `q ≥ 1` and every `p ∈ Δ_n`, the distribution `π`
placing mass `1/q` at each `q`-quantile of `p` (adding masses when quantiles repeat) lies
in `Δ_n` and satisfies `d_K(p, π) ≤ 1/q`; `π` is computed from the quantiles alone.
2. There are absolute constants `C₁, C₂ > 0` such that for `n ≥ 2`, `ε ∈ (0, 1)` and
`q = ⌈n^ε⌉`: the `q`-quantile sketch takes at most `2^b` values on `Δ_n` for some integer
`b ≤ C₁ n^ε log₂ n` (a sketch of `O(n^ε log n)` bits), and for every `p ∈ Δ_n` Coarse Greedy
with parameter `ε` and nominal distribution `π` (any choice of `π`-medians) satisfies
`cost_p ≤ (C₂/ε)·OPT(p)` (an `O(1/ε)`-approximation).
**Formalization Note.** `O(·)` are absolute constants chosen before `n`, `ε`, `p`. The
`q`-quantiles are `x_ℓ = min{t ∈ [n]₀ : P(t) ≥ ℓ/q}`, `ℓ = 1, …, q`. `log` is base 2. -/
theorem theorem_8 :
(∀ (n : ℕ), 2 ≤ n → ∀ q : ℕ, 1 ≤ q → ∀ p ∈ stdSimplex ℝ (Fin n),
quantileDist n q (quantileSketch n q p) ∈ stdSimplex ℝ (Fin n) ∧
kolDist p (quantileDist n q (quantileSketch n q p)) ≤ 1 / q) ∧
∃ C₁ C₂ : ℝ, 0 < C₁ ∧ 0 < C₂ ∧
∀ (n : ℕ), 2 ≤ n → ∀ ε : ℝ, 0 < ε → ε < 1 →
(quantileSketch n ⌈(n : ℝ) ^ ε⌉₊ '' stdSimplex ℝ (Fin n)).Finite ∧
(∃ b : ℕ, (b : ℝ) ≤ C₁ * (n : ℝ) ^ ε * Real.logb 2 n ∧
(quantileSketch n ⌈(n : ℝ) ^ ε⌉₊ '' stdSimplex ℝ (Fin n)).ncard ≤ 2 ^ b) ∧
∀ p ∈ stdSimplex ℝ (Fin n), ∀ med : ℕ → ℕ → ℕ,
IsMedianRule (quantileDist n ⌈(n : ℝ) ^ ε⌉₊ (quantileSketch n ⌈(n : ℝ) ^ ε⌉₊ p)) med →
cost p (coarseGreedy
(quantileDist n ⌈(n : ℝ) ^ ε⌉₊ (quantileSketch n ⌈(n : ℝ) ^ ε⌉₊ p)) ε med) ≤
C₂ / ε * OPT 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 8, p.9 (PDF p.11); restated with proof App. B.2, p.18 (PDF p.20)