Communication cost bounds for exact sampling from complex distributions
Exact Sampling Under Campbell Cost via Rényi Channel Simulation Divergence
Information Theory
Summary
This paper looks at how to efficiently pick exact samples from one probability distribution when you start with samples from another. The authors introduce a new mathematical measure that helps understand the minimum communication needed between a sender and receiver who share sample data. They provide a method that nearly achieves this minimum cost and give more precise estimates when many samples are involved. Essentially, it advances our understanding of how to communicate exact random choices with minimal messaging.
What this means in practice
- •For communication engineers: Optimize protocols that require exact random sampling with minimal data transmission cost under exponential cost constraints.
- •For data compression teams: Design coding schemes that achieve close to theoretical lower bounds for transmitting exact samples from target distributions.
A theory result. No direct application yet.
Authors
Yijun Fan, Aaron B. Wagner
Abstract
We study the communication cost of exact sampling under Campbell's exponential coding criterion. Given a target distribution $P$ and a proposal distribution $Q$, the sender and receiver share i.i.d. $Q$-distributed samples, and the sender communicates an index so that the selected sample has distribution exactly $P$. We introduce a new information measure Rényi channel simulation divergence $R_α(P\Vert Q)$, a Rényi generalization of the channel simulation divergence. We then show that it lower bounds the Campbell cost of every exact sampler and is achievable, via a new layered sampling scheme, within an additive constant depending only on the Campbell parameter. This yields a tighter one-shot characterization than previous bounds based on Rényi divergences of different orders. For i.i.d. product distributions, under suitable non-degeneracy and moment conditions, we further show that the gap beyond the leading Rényi-divergence term is $\frac{1}{2}\log n+O(1)$.