The Redundancy of Non-Singular Channel Simulation

Gergely Flamich, Sharang M. Sriramu, Aaron B. Wagner

Abstract

In modern lossy data compression, channel simulation has emerged as a powerful alternative to traditional quantization, particularly for its ability to preserve perceptual quality in generative models. This paper provides a fundamental characterization of the communication cost associated with this process. By analyzing "non-singular" channels—those with smooth conditional distributions—the authors establish a definitive lower bound for the extra communication cost, or redundancy, required to simulate a channel. They prove that this redundancy scales at a rate of $\frac{1}{2} \log n$ bits, matching existing upper bounds and completing a critical gap in information-theoretic literature.

Introduction

Traditional lossy compression relies on quantization, where a continuous input is mapped to the nearest discrete point in a predefined codebook. While efficient, this deterministic mapping often fails to capture the stochastic nuances of the original data, leading to artifacts. Modern machine learning approaches, such as neural compression, frequently utilize channel simulation. In this paradigm, Alice does not send a specific quantized value; instead, she transmits just enough information to allow Bob to generate a sample $Y$ from a specific conditional distribution $P_{Y|X}$ using shared randomness.

While the theoretical minimum average cost for this transmission is the Mutual Information $I(X;Y)$, practical simulation always incurs a "redundancy"—additional bits beyond this floor. While previous research characterized this redundancy for discrete or "singular" channels, a tight lower bound for continuous, non-singular channels remained an open problem until now.

Theoretical Framework and Methodology

The authors employ two distinct mathematical frameworks to derive robust bounds for channel simulation redundancy across both one-shot and asymptotic regimes.

1. One-Shot Analysis

To address the cost of a single channel use, the authors generalize the "channel simulation divergence" ($D_{CS}$) framework. A significant challenge in continuous settings is the handling of conditional Shannon entropy. The authors overcome this by employing Palm distributions, a tool from point process theory. This allows for a rigorous derivation of a one-shot lower bound (Theorem III.1) that applies to any pair of random variables $X, Y$ within a broad class of topological spaces (Polish spaces).

2. Asymptotic Analysis

To determine how the cost scales as the number of samples $n$ increases, the authors provide two independent proofs:

  • Central Limit Theorem (CLT) Approach: Utilizing the Lindeberg-Feller version of the CLT, they expand the channel simulation divergence as $n \to \infty$.
  • Large Deviations Theory: Using "tilted measures" and cumulant generating functions, they analyze the "tails" of the distribution. This proof demonstrates that the probability of successfully simulating the channel with fewer bits than the prescribed bound vanishes as $n$ grows.

Key Insights: The "Half-Log" Limit

The paper’s most significant contribution is the identification of the "Non-Singular Divide." The authors demonstrate a fundamental shift in complexity based on the nature of the channel:

  • Singular Channels: If the output is highly restricted or "jumpy" given the input, the redundancy is negligible.
  • Non-Singular Channels: For smoother, continuous channels, there is a mandatory "tax" of $\frac{1}{2} \log n$ bits.

This $\frac{1}{2} \log n$ term is a recurring motif in information theory, often appearing in the context of parameter estimation and the Minimum Description Length (MDL) principle. Its emergence here suggests that simulating a channel is fundamentally equivalent to the complexity of describing or "learning" the underlying conditional distribution.

Results and Implications

The core result is formalized in the proof that for $n$ independent and identically distributed (i.i.d.) samples, the normalized redundancy follows the limit:

$$\lim_{n \to \infty} \frac{R_n - I(X;Y)}{\frac{1}{n} \text{lb } n} \geq \frac{1}{2}$$

This confirms that the second-order cost of channel simulation is exactly $\frac{1}{2} \log n$ bits per block. Furthermore, the authors demonstrate that Channel Simulation Divergence is the superior metric for measuring efficiency in these tasks, providing a tighter and more accurate bound than the standard Kullback-Leibler (KL) divergence.

Conclusion and Future Directions

This work completes the theoretical characterization of non-singular channel simulation by providing the long-sought lower bound. However, several avenues for future research remain. While the lower bound is now established and matches known upper bounds, a single unified proof for the "achievability" (the upper bound) that covers all general non-singular cases remains a conjecture. Additionally, as this work is purely theoretical, the challenge of translating these insights into more efficient, real-world neural compression codecs remains an open engineering task. The discovery of the $\frac{1}{2} \log n$ tax provides a clear target for developers of next-generation generative compression tools.

Summary updated

BibTeX
@inproceedings{flamich2025redundancy,
  author = {Gergely Flamich and Sharang M. Sriramu and Aaron B. Wagner},
  title = {{The Redundancy of Non-Singular Channel Simulation}},
  booktitle = {ISIT},
  year = {2025},
  doi = {10.1109/isit63088.2025.11195647},
}
Figure