Singular Relative Entropy Coding with Bits-Back Rejection Sampling

This paper introduces the Bits-Back Rejection Sampler (BBRS), a practical and simpler relative entropy code for singular channels that achieves the same sub-logarithmic asymptotic redundancy as previous theoretical work while offering better constants and implementability.

The Gist

The Big Picture: The "Secret Message" Problem

Imagine you and a friend are trying to send a secret message. You have a specific type of puzzle (a "channel") where the rules are a bit tricky.

• The Goal: You want to send a piece of data (let's call it Y) that depends on a secret input you have (X).
• The Constraint: You want to use as few bits (0s and 1s) as possible to send Y.
• The Catch: You and your friend share some random "noise" (like a deck of shuffled cards) beforehand, but you can't talk to each other during the process.

In the world of information theory, there is a theoretical "speed limit" on how few bits you can use. This limit is called Mutual Information. It's like the absolute minimum amount of "stuff" you must send to get the job done.

For a long time, scientists knew that while you could get close to this speed limit, you usually had to pay a small "tax" (extra bits) to make it work. This tax was roughly the size of a logarithm (a slow-growing number).

The Special Case: "Singular" Channels

The paper focuses on a special type of puzzle called a Singular Channel.

• Analogy: Imagine a machine that takes an input X and spits out Y. In a normal machine, if you change X slightly, the probability of getting a specific Y changes in a complex way.
• The Singular Twist: In a singular channel, changing X doesn't change the odds of the outcome; it only changes which outcomes are possible. It's like a vending machine where pressing "A" only lets you get a Coke or a Sprite, and pressing "B" only lets you get a Coke or a Fanta. The price (probability) of a Coke is the same in both cases, but the menu changes.

For these specific "Singular" puzzles, a previous team of researchers (Sriramu and Wagner) proved that you could actually eliminate that "tax" entirely. You could reach the perfect speed limit. However, their solution was like a theoretical blueprint for a flying car: it worked on paper, but it required impossible calculations and was too complex to ever build in real life.

The New Solution: The "Bits-Back" Rejection Sampler (BBRS)

The authors of this paper, Gergely Flamich and Spencer Hill, say: "Let's build a flying car that actually works." They created a new method called Bits-Back Rejection Sampling (BBRS).

Here is how it works, using a Magic Mailbox analogy:

1. The Problem with Standard "Rejection Sampling"

Imagine you want to pick a random card from a deck, but you only have a specific rule for which cards are "winners."

• Standard Method: You pull a card. Is it a winner? No? Throw it away and try again. Is it a winner? Yes! Keep it.
• The Cost: To tell your friend which card you kept, you have to send them the number of times you tried (e.g., "I tried 5 times, the 5th one was the winner"). This takes up a lot of bits.

2. The "Bits-Back" Trick

This is where the magic happens. The authors use a technique called Bits-Back Coding.

• The Setup: You have a stream of random bits (your "seed") that you are supposed to send to your friend.
• The Trick: Instead of just sending the card number, you use the card number to hide some of your random bits inside the message.
• The Recovery: When your friend receives the message, they decode the card. Because they know the rules of the game (the "Singular" nature of the channel), they can figure out exactly which random bits you hid inside. They "get their bits back."
• The Result: You effectively sent the card for free because you reclaimed the bits you used to encode it. It's like paying for a coffee with a coupon, but the store gives you the coupon back in change.

3. Why "Singular" Channels Make This Work

In a normal channel, the "rules" are too messy to perfectly reverse-engineer the hidden bits. But in a Singular Channel, the rules are so clean and predictable that the receiver can perfectly reconstruct the hidden bits.

• Analogy: Imagine a lock where the key shape is determined entirely by the door frame. If you know the door frame, you can instantly guess the key. In a singular channel, the "door frame" (the output Y) tells you exactly what the "key" (the hidden bits) was.

Why This Paper Matters

1. It's Practical: The previous "perfect" solution was a mathematical ghost. This new solution (BBRS) uses standard tools that engineers can actually build and run on computers today.
2. It's Simpler: The math behind this new method is much cleaner and easier to understand than the previous "impossible" code.
3. It's Efficient: It achieves the theoretical "perfect" speed (zero extra tax) for these specific channels, just like the ghostly blueprint did, but without the impossible requirements.

Summary in One Sentence

The authors built a new, practical "magic mailbox" that uses a clever trick called "bits-back" to send data through specific types of channels with zero wasted space, finally turning a theoretical dream into a working reality.

Technical Summary

1. Problem Statement

The paper addresses the problem of Relative Entropy Coding (REC), also known as channel simulation. The goal is to design a stochastic code that allows a sender to transmit a sample $Y$ drawn from a conditional distribution $P_{Y|X}$ to a receiver, given an input $X \sim P_X$ and shared common randomness $Z$, using the minimum number of bits possible.

• Theoretical Lower Bound: The fundamental limit for the expected codelength is the mutual information $I[X; Y]$.
• The Gap: General REC schemes (like Greedy Rejection Sampling) achieve a rate of $I[X; Y] + O(\log(I[X; Y]))$. This logarithmic gap is unavoidable for general channels.
• The Specific Challenge: The authors focus on Singular Channels, a class of channels where the conditional density ratio $dP_{Y|X}/dP_Y$ depends only on $Y$ and not on $X$ (almost surely).
  • Previous work by Sriramu and Wagner [1] proved that for singular channels, the asymptotic logarithmic redundancy can be reduced to zero (i.e., the rate approaches $I[X; Y]$ exactly as block length $n \to \infty$).
  • Limitations of Prior Work: The Sriramu-Wagner code is theoretically sound but practically intractable. It relies on computing quantities that are impossible to calculate even for simple problems, exhibits poor "one-shot" performance (large constants and sub-logarithmic terms), and lacks an intuitive explanation for why singularity eliminates the redundancy.

2. Methodology: Bits-Back Rejection Sampling (BBRS)

The authors propose a new stochastic code called Bits-Back Rejection Sampling (BBRS). This method combines Bits-Back Coding with Greedy Rejection Sampling (GRS) to exploit the properties of singular channels.

Core Concepts Used:

1. Singular Channels: Defined by the existence of a function $g$ such that $dP_{Y|X}/dP_Y = g(Y)$. This implies that once $Y$ is known, the "log-density ratio" $\Gamma = \log(dP_{Y|X}/dP_Y)$ can be deterministically recovered via $g(Y)$.
2. Greedy Rejection Sampling (GRS): A method to sample from a target distribution using a proposal distribution, optimizing acceptance probabilities at each step to minimize the expected number of proposals.
3. Bits-Back Coding: A technique where the encoder "borrows" bits from a message stream to encode a sample, and the decoder "returns" those bits by recovering the original stream state after decoding the sample.

The BBRS Algorithm:

The code operates in a two-part structure for a singular channel $X \to Y$:

1. Quantization of the Log-Density Ratio:
   The encoder computes the log-density ratio $\Gamma = \log \frac{dP_{Y|X}}{dP_Y}(Y|X)$. Since the channel is singular, $\Gamma$ is a function of $Y$ alone. The encoder quantizes this value to $\Gamma_\Delta$.

2. Encoding Phase (Sender):

   • Step A (Simulate $\Gamma$): The encoder simulates a value $\Gamma$ from the conditional distribution $P_{\Gamma|X}$.
   • Step B (Encode $\Gamma$ via GRS): Using shared randomness, the encoder uses GRS to generate a sample $Y' \sim P_{Y|\Gamma}$. The index $K$ of the accepted sample is encoded.
   • Step C (Bits-Back Recovery): Crucially, because the channel is singular, the decoder can recover $\Gamma$ from $Y'$ (since $\Gamma = Q_\Delta(\log g(Y'))$). The encoder knows the decoder will recover $\Gamma$, so the encoder uses bits-back coding: it decodes the acceptance decisions of the GRS process from the message stream, effectively "returning" the bits used to encode the GRS index.
   • Step D (Encode $Y$): Finally, the encoder sends the specific sample $Y$ conditioned on $X$ and the recovered $\Gamma$. Since $\Gamma$ is now known to both parties, standard rejection sampling is used with a known upper bound $M(\Gamma, X)$.

3. Decoding Phase (Receiver):

   • The receiver decodes the GRS index to recover $Y'$.
   • Using the singularity property, the receiver computes $\Gamma = Q_\Delta(\log g(Y'))$.
   • The receiver "replays" the GRS process to recover the bits that were "borrowed" (the bits-back step), restoring the message stream state.
   • The receiver uses the recovered $\Gamma$ and the second part of the message to decode the final sample $Y$.

3. Key Contributions

1. Construction of BBRS: The authors introduce a practical, implementable stochastic code for singular channels that achieves zero asymptotic logarithmic redundancy.
2. Simpler Analysis: Unlike the complex, intractable proof of Sriramu and Wagner, BBRS offers a transparent analysis where the role of singularity is explicit: it allows the recovery of the log-density ratio $\Gamma$, enabling the bits-back mechanism to cancel out the cost of encoding $\Gamma$.
3. Improved Constants and One-Shot Performance: BBRS has significantly better constants and sub-logarithmic terms in its one-shot rate compared to the previous state-of-the-art.
4. Practical Implementability: The quantities required for BBRS (such as the density ratio and the function $g$) are computable in practice, unlike the theoretical constructs required by the Sriramu-Wagner code.

4. Results

The paper provides a rigorous rate analysis for BBRS:

• One-Shot Rate Bound: For a singular channel, the expected codelength $E[|enc(X, Z)|]$ is bounded by:
  $$E[|enc(X, Z)|] \le I[X; Y] + \log(H[\Gamma] + 1) + 2\Delta + 5$$
  Where $\Delta$ is the quantization precision and $H[\Gamma]$ is the entropy of the quantized log-density ratio.

• Asymptotic Redundancy:
  By applying the Central Limit Theorem to the log-density ratio over $n$ i.i.d. samples, the authors show that $H[\Gamma_n] \approx \frac{1}{2}\log n$.
  Consequently, the logarithmic redundancy $R_{log}$ is:
  $$R_{log} = \lim_{n \to \infty} \frac{E[|enc_n|] - nI[X; Y]}{\log n} = 0$$
  This confirms that for singular channels, the optimal rate is achievable, matching the theoretical lower bound without the $\frac{1}{2}\log n$ penalty seen in non-singular channels.

5. Significance

• Theoretical Clarity: The paper demystifies why singular channels allow for zero redundancy. It demonstrates that singularity acts as a deterministic "error-correction" mechanism that allows the receiver to reconstruct the necessary auxiliary information ($\Gamma$) without it being explicitly transmitted, thereby enabling the bits-back trick to recover the full cost.
• Practical Utility: By moving from an intractable theoretical construction to an implementable algorithm (BBRS), the paper bridges the gap between information-theoretic limits and practical coding schemes for specific channel types.
• Foundation for Future Work: The authors suggest that while BBRS relies on quantization, the framework opens the door for future research into eliminating this discretization or analyzing its precise impact on sampler behavior. It also clarifies that for non-singular channels, the $\frac{1}{2}\log n$ redundancy is inherent and can be achieved by simpler modifications to existing codes (like GRS or Poisson Functional Representation), making BBRS specifically valuable for the singular case.