🔢 mathematics

Communication Complexity of Exact Sampling under Rényi Information

This paper establishes the optimal asymptotic communication cost for exact sampling under exponential cost (Campbell's average codeword length) by deriving tight lower and upper bounds characterized by Rényi divergence, demonstrating that noncausal samplers strictly outperform causal ones in this regime, unlike in the case of expected message length.

Original authors: Spencer Hill, Fady Alajaji, Tamás Linder

Published 2026-04-03

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Spencer Hill, Fady Alajaji, Tamás Linder

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a chef (the Sender) who wants to send a specific, secret recipe (a sample) to a friend (the Receiver).

Here's the catch: You both have a giant, shared cookbook filled with thousands of random, unrelated recipes (this is your Shared Randomness). You don't want to mail the whole secret recipe because it might be too long or complex. Instead, you want to send your friend a simple note saying, "Go to page number K in our shared cookbook, and that page will have the exact secret recipe you need."

The goal of this paper is to figure out the shortest possible note you can send to make this work perfectly every time.

The Problem: How Short Can the Note Be?

In the past, scientists asked: "What is the average length of the note?" (e.g., "Usually, I send a 5-word note, but sometimes 20 words"). They found that the average length depends on how different your secret recipe is from the random ones in the cookbook.

But this paper asks a different, more practical question: "What if we really hate long notes?"

Imagine you are sending this note over a very slow, expensive connection, or you have a tiny mailbox that bursts if the note is too long. In this scenario, a single 100-word note is much worse than ten 10-word notes, even if the average is the same. You want to minimize the risk of a "burst" (overflow).

To measure this, the authors use a special "cost meter" called Campbell's Cost. It doesn't just count words; it punishes long notes exponentially. A 10-word note might cost 10 points, but a 20-word note might cost 1,000 points.

The Big Discovery: "Looking Ahead" vs. "One Step at a Time"

The paper compares two types of chefs (algorithms) trying to find the right page number K:

The Causal Chef (The Impatient One): This chef opens the cookbook page by page, starting from page 1. They check: "Is this the right recipe? No? Okay, check page 2." They stop as soon as they find a match. They never look at page 100 until they've checked pages 1 through 99.
The Non-Causal Chef (The Visionary): This chef is allowed to flip through the entire cookbook instantly, find the best possible match, and then just tell the friend the page number. They can "look ahead."

The Surprising Result:

For the "Average" cost: Both chefs are equally good. It doesn't matter if you look ahead or not; the average note length is the same.
For the "Expensive/Long Note" cost: The Visionary Chef wins by a huge margin. The Impatient Chef is forced to sometimes dig deep into the book (finding a match on page 1,000), which creates a very long, expensive note. The Visionary Chef can skip the bad pages and pick a match that results in a short note.

The paper proves that if you care about avoiding those rare, super-long notes, you must use the "Visionary" approach. The "Impatient" approach is mathematically doomed to be much more expensive in this specific scenario.

The Math Magic: Renyi Divergence

The authors use a fancy mathematical tool called Rényi Divergence to measure "how different" the secret recipe is from the random ones in the cookbook.

Think of Rényi Divergence as a "Difficulty Score."
If the secret recipe is very similar to the random ones, the score is low, and the note is short.
If the secret recipe is totally unique, the score is high, and the note is long.

The paper provides a new formula that tells you exactly how long your note must be based on this Difficulty Score. They found a "Lower Bound" (the absolute best you could possibly do) and an "Upper Bound" (a method that gets very close to that best).

The "Poisson" Trick

To get close to the perfect note length, the authors use a clever trick called the Poisson Functional Representation.

Imagine the cookbook pages are sprinkled with invisible "stars" (random points). The secret recipe is also sprinkled with stars. The trick is to find the page where the stars align perfectly with the secret recipe. This method allows the Visionary Chef to find the optimal page number efficiently, ensuring the note sent to the friend is as short as possible, even when avoiding long notes is the priority.

Why Does This Matter?

This isn't just about recipes. This applies to:

Deep Learning: Compressing massive AI models.
Data Buffers: Preventing computer memory from overflowing when data packets are too long.
Communication: Sending data over channels where long messages are extremely costly or likely to fail.

Summary in a Nutshell

The Goal: Send a secret item by pointing to a shared list, minimizing the risk of sending a "too long" message.
The Old Way: Just try to make the average message short.
The New Way: Make sure you never have to send a huge message, even if it means the average is slightly higher.
The Lesson: To avoid huge messages, you need to be able to "look ahead" and pick the best option immediately, rather than checking items one by one. The paper proves this mathematically and gives you the exact formulas to calculate the best possible message length.

In short: If you hate long messages, don't just check things one by one. Look at the whole picture first.

1. Problem Statement

The paper addresses the problem of exact sampling (also known as channel simulation or relative entropy coding) under an exponential communication cost.

Setup: A sender and receiver share a source of common randomness $\{U_i\}_{i \ge 1}$ drawn i.i.d. from a proposal distribution $Q$ . The sender wishes to communicate an index $K$ such that the $K$ -th sample $U_K$ follows a target distribution $P$ (i.e., $U_K \sim P$ ).
Objective: Minimize the communication cost of transmitting the index $K$ .
Cost Metric: Unlike previous works focusing on the expected message length (Shannon entropy), this paper minimizes the Campbell cost (average codeword length of order $t$ $t$ ), defined as:
$L(t) = \frac{1}{t} \log \left( \mathbb{E}[2^{t l(C(K))}] \right)$
where $l(C(K))$ $l (C (K))$ is the length of the codeword for $K$ $K$ .
- As $t \to 0$ , $L(t)$ converges to the expected message length $\mathbb{E}[l(C(K))]$ .
- For $t > 0$ , this cost penalizes long codewords exponentially, which is critical for applications prone to buffer overflow.
Key Question: What is the fundamental limit of $L(t)$ for exact sampling, and how does it relate to Rényi divergence? Furthermore, how do causal samplers (sequential, stopping-time based) compare to noncausal samplers (which can look ahead in the sequence)?

2. Methodology

The authors employ a combination of information-theoretic inequalities, probabilistic representations, and coding theory.

Rényi Information Measures: The analysis is framed using Rényi entropy $H_\alpha$ and Rényi divergence $D_\alpha(P||Q)$ , where the order $\alpha$ is linked to the cost parameter $t$ by $\alpha = \frac{1}{1+t}$ .
Poisson Functional Representation (PFR): A central tool used is the PFR introduced by Li and El Gamal. This noncausal method defines the index $K$ as:
$K := \arg \min_{i \ge 1} \frac{T_i}{\frac{dP}{dQ}(U_i)}$
where $\{T_i\}$ is a rate-one Poisson process. This representation allows for the derivation of tight bounds on the moments of $K$ .
Moment Bounds: The proofs rely heavily on establishing lower and upper bounds for the moments $\mathbb{E}[K^\alpha]$ $E [K^{α}]$ and $\mathbb{E}[(g(K))^\alpha]$ $E [(g (K))^{α}]$ for bijections $g$ $g$ .
- Lower Bound: Derived by extending results from Liu and Verdú, showing that any sampling algorithm must satisfy specific moment constraints related to $D_{\alpha+1}(P||Q)$ .
- Upper Bound: Constructed by encoding the index $K$ generated by the PFR using specific variable-length codes (e.g., Elias omega codes or optimized prefix codes) and bounding the resulting Campbell cost.
Asymptotic Analysis: The paper extends one-shot results to the asymptotic regime where the target is a product distribution $P^{\otimes n}$ and the common randomness is $Q^{\otimes n}$ .

3. Key Contributions

A. Lower Bounds on Campbell Cost

The authors establish a fundamental lower bound for any exact sampling algorithm (causal or noncausal):
$L(t) \ge \max \left\{ D_{1/\alpha}(P||Q) + \frac{\alpha}{1-\alpha}\log(\alpha) - 1, \quad D_{2-\alpha}(P||Q) + \frac{1}{1-\alpha}\log\left(\frac{1}{2-\alpha}\right) \right\}$
where $\alpha = \frac{1}{1+t}$ .

The dominant term is the Rényi divergence of order $1/\alpha$ , i.e., $D_{1/\alpha}(P||Q)$ .
This generalizes the known lower bound $\mathbb{E}[l(C(K))] \ge D(P||Q)$ (which is recovered as $t \to 0, \alpha \to 1$ ).

B. Upper Bounds via Poisson Functional Representation

Using the PFR, the authors prove an upper bound that is tight within a small constant gap:
$L(t) \le (1+\epsilon) D_{\frac{1+\epsilon(1-\alpha)}{\alpha}}(P||Q) + c_1(\alpha, \epsilon)$

The leading Rényi divergence term has an order very close to $1/\alpha$ (the order of the lower bound).
The constant term $c_1(\alpha, \epsilon)$ is finite but grows as $\alpha \to 0$ .
Numerical examples show the upper and lower bounds are typically within 5–10 bits of each other.

C. Operational Universal Coding

The paper provides a constructive procedure using universal codes (like Elias omega codes) that yields an upper bound:
$L(t) \le D_{\frac{2-\alpha}{\alpha}}(P||Q) + (1+\epsilon)\log(D(P||Q)+1) + c_2(\epsilon)$
This bound reduces to the Harsha et al. result as $\alpha \to 1$ .

D. Asymptotic Optimality and Causal vs. Noncausal Gap

Optimal Rate: For i.i.d. sequences, the optimal asymptotic Campbell cost per sample is exactly:
$\lim_{n \to \infty} \frac{L^*_n(t)}{n} = D_{1/\alpha}(P||Q)$
Causal vs. Noncausal: A major finding is the strict separation between causal and noncausal samplers under exponential cost.
- Noncausal samplers achieve the optimal rate $D_{1/\alpha}(P||Q)$ .
- Causal samplers (which process the shared randomness sequentially) have a strictly worse asymptotic rate, bounded below by $D_\beta(P||Q)$ where $\beta > 1/\alpha$ .
- In some cases (e.g., Gaussian distributions with different means), the asymptotic cost for causal samplers is infinite for certain $t$ , whereas noncausal samplers remain finite. This contrasts sharply with the expected message length case ( $t=0$ ), where both types achieve the same rate $D(P||Q)$ .

E. Channel Simulation Generalization

The results are extended to channel simulation, establishing a Rényi-generalized Strong Functional Representation Lemma. The Rényi conditional entropy $H_\alpha(Y|Z)$ is upper-bounded by the Sibson $\alpha$ -mutual information $I^s_\alpha(X;Y)$ .

4. Results and Numerical Examples

Distributions: The authors analyze Normal and Laplacian distributions.
Gap Analysis: For both distributions, the derived upper and lower bounds are extremely close (within 5–10 bits) across a wide range of $\alpha$ (specifically $0.2 < \alpha < 1$ ).
Behavior at Extremes:
- As $\alpha \to 1$ ( $t \to 0$ ), the bounds converge to the standard expected message length results.
- As $\alpha \to 0$ ( $t \to \infty$ ), the cost grows significantly, and the specific order of the Rényi divergence becomes critical.
Computational Tractability: The proposed bounds have closed-form expressions for many standard distributions, whereas computing the exact Rényi entropy of the index $K$ ( $H_\alpha(K)$ ) is often computationally intractable for heavy-tailed distributions.

5. Significance

Theoretical Advancement: This work bridges the gap between linear communication costs (Shannon) and exponential costs (Campbell), providing the first tight characterization of exact sampling under exponential penalties.
Practical Relevance: The exponential cost model is crucial for systems with strict latency or buffer constraints (e.g., deep learning compression, real-time communication) where long codewords are catastrophic.
Fundamental Limit of Causality: The paper reveals a fundamental limitation of causal algorithms in the context of exponential costs. While causality does not hurt performance in terms of expected length, it incurs a severe penalty when long messages are penalized. This suggests that for high-reliability, low-latency applications, noncausal (or "look-ahead") strategies are theoretically necessary.
New Tools: The extension of the Strong Functional Representation Lemma to Rényi information measures opens new avenues for analyzing one-shot coding problems, variable-length lossy source coding, and multiple description coding under non-linear cost functions.

In summary, the paper characterizes the exact asymptotic cost of sampling under exponential penalties, proving that the optimal rate is governed by the Rényi divergence of order $1/\alpha$ , and demonstrating that noncausal sampling is strictly superior to causal sampling in this regime.