🤖 machine learning

Scalable Discrete-to-Continuous Channel Simulation for Compression and Privacy

This paper introduces a scalable, fixed-runtime scheme for exact and approximate discrete-to-continuous channel simulation that leverages latent permutations, exponential races, and polar coding to achieve efficient compression and privacy-preserving communication with $O(n \log n)$ complexity.

Original authors: Joseph Rowan, Buu Phan, Ashish J. Khisti

Published 2026-09-14

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Joseph Rowan, Buu Phan, Ashish J. Khisti

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

In the digital world, information is often treated as a series of discrete steps, like beads on a string. But the real world is continuous, a smooth flow of sound, light, and motion. When computers try to understand or transmit this smooth reality, they must first chop it into those discrete steps, a process that inevitably loses some detail. To fix this, engineers often add a layer of controlled noise back into the system, a technique that helps preserve the essence of the original signal while keeping the data manageable. This balancing act is at the heart of modern machine learning and secure communication. However, there is a persistent problem: simulating this specific type of noise, where a discrete input becomes a continuous output, has been incredibly difficult to do efficiently. Existing methods often require an unpredictable amount of time or an impossible number of shared random numbers to work correctly, making them too slow for real-world use.

A team of researchers at the University of Toronto has developed a new way to solve this problem, creating a system that can simulate these complex channels with a fixed, predictable amount of effort. Their approach, which they call the permuted scheme, fundamentally changes how computers select the right random noise to add to a signal. Instead of generating a long list of random samples and hoping one of them fits the bill, their method generates exactly one sample for every possible type of input, then shuffles them randomly before making a selection. This simple act of rearranging the samples allows the system to compress the information much more efficiently than before. The researchers proved that this method works perfectly for exact simulations and can be scaled up to handle massive amounts of data using techniques borrowed from error-correcting codes, a field that ensures data survives transmission over noisy lines.

The power of this new method lies in its ability to handle long sequences of data without getting bogged down. In many applications, such as compressing images or protecting private data in a network, it is beneficial to process thousands of data points together rather than one by one. Previous methods would become exponentially slower as the number of data points grew, quickly becoming impractical. The new system, however, scales efficiently, meaning the time it takes to process the data grows only slightly as the amount of data increases. This allows the researchers to simulate channels involving thousands of variables in a matter of seconds, a task that would have taken much longer or been impossible with older techniques. They demonstrated this by compressing images from a standard dataset, showing that their method could achieve high-quality results with less data than traditional approaches, all while maintaining the ability to adjust the compression level on the fly without retraining the system.

Beyond image compression, the team applied their method to the critical field of privacy. In a scenario where many people want to share their data with a central server without revealing their individual information, a technique called differential privacy is used to add noise to the data. The researchers showed that their new simulation method could generate this privacy-preserving noise exactly and quickly, even when dealing with large groups of people and high-dimensional data. They tested this with a setup involving one hundred thousand simulated users, each sharing a vector of data, and found that their system could communicate the necessary information using significantly fewer bits than previous methods. This reduction in communication cost is vital for systems that rely on fast, efficient data exchange, such as federated learning where models are trained across many devices.

The researchers also explored the limits of their approach, noting that while the method is exact for smaller sets of possibilities, it relies on a mathematical approximation when the number of possible inputs becomes very large. In their experiments with image compression, where the number of possible values was two hundred and fifty-six, they used an iterative algorithm to approximate the necessary probabilities. This approximation was fast and proved sufficient to produce high-quality results, suggesting that the method is robust enough for practical applications even when perfect mathematical precision is traded for speed. The work does not claim to solve every problem in data compression or privacy, but it provides a reliable, scalable tool that removes a major bottleneck in how machines handle the transition from discrete data to continuous reality. By making these simulations faster and more predictable, the researchers have opened the door for more efficient and private machine learning systems that can operate at the scale required by modern technology.

Technical Summary: Scalable Discrete-to-Continuous Channel Simulation for Compression and Privacy

1. Problem Statement

The paper addresses the challenge of channel simulation, where an encoder observes a source $X$ and communicates with a decoder to generate an output $Y$ following a prescribed conditional distribution $P_{Y|X}$ . The goal is to minimize the communication cost (expected bit-length of the message) while utilizing shared randomness.

While significant progress has been made in simulating channels with discrete outputs (e.g., using the Exponential Functional Representation or rejection sampling), simulating discrete-to-continuous channels (where $X$ is discrete and $Y$ is continuous) remains difficult. Existing general methods, such as the Poisson Functional Representation (PFR) or rejection sampling, suffer from critical limitations:

High Computational Cost: Many algorithms require generating an infinite number of samples in the worst case or have running times that scale exponentially with the blocklength.
Variable Stopping Times: Some schemes rely on random stopping times, making runtime unpredictable.
Scalability: Extending these methods to high-dimensional vectors (long blocklengths) is often impractical due to exponential complexity.

The authors specifically target the case where $X$ is a finite alphabet and $Y$ is continuous, a scenario common in neural compression (e.g., VQ-VAEs with continuous latents) and privacy-preserving distributed learning (e.g., Gaussian mechanisms).

2. Methodology

The Permuted Scheme (One-Shot)

The core contribution is a "permuted scheme" that achieves exact or approximate simulation using a fixed number of shared random samples, independent of the input or channel choice.

Mechanism: Instead of generating a sequence of independent samples from a proposal distribution and selecting one, the scheme generates exactly one sample from each potential target distribution $P_{Y|X}(\cdot | x)$ for $x \in \mathcal{X}$ .
Random Permutation: A uniform random permutation $\Pi$ is applied to these samples. This breaks the deterministic mapping between the sample index and the distribution that generated it.
Selection: The encoder observes $X=x$ and selects an index $K$ based on the posterior probability $P_{K|X, \bar{U}^N}(k | x, \bar{u}^N)$ , which depends on the permuted samples $\bar{U}^N$ . The decoder, knowing the shared randomness (samples and permutation), reconstructs $K$ and outputs $Y = \bar{U}_K$ .
Communication: The index $K$ is communicated using a coordinated sampling strategy (Exponential Functional Representation) with a shared exponential race, achieving a message length bounded by the conditional mutual information $I(X; Y | \bar{U}^N)$ .

Approximation for Large Alphabets

Computing the exact posterior distribution requires calculating the matrix permanent, which is #P-complete. For large input alphabets (e.g., $N=256$ ), the authors employ the Sinkhorn-Knopp algorithm to approximate the posterior. This allows the scheme to scale to larger alphabets while maintaining competitive rate-distortion performance, albeit with approximate simulation.

Scaling to Long Blocklengths (Multi-Shot)

To handle high-dimensional vectors (large $n$ ), the authors integrate techniques from modern coding theory:

Polar Coding: For binary inputs ( $N=2$ ), the permuted scheme is reformulated as simulating a binary-symmetric channel with side information. A modified PolarSim algorithm is used, which operates in $O(n \log n)$ time.
Multilevel Coding (MLC): For larger alphabets ( $N > 2$ ), the scheme is extended using MLC. The $N$ -ary index is decomposed into $\log N$ binary levels. Each level is simulated independently using the polar coding framework, allowing the total complexity to scale as $O(n \log n)$ .

3. Key Contributions

Fixed-Sample Simulation: Introduction of a method for exact and approximate simulation of discrete-to-continuous channels using a fixed number of shared random samples ( $2|X|$ for exact, or more for approximation), ensuring runtime independence from the channel and input.
Scalability via Coding Theory: Demonstration of how polar codes and multilevel coding can be incorporated into the permuted scheme to handle long blocklengths efficiently ( $O(n \log n)$ ), overcoming the exponential complexity of previous general methods.
Approximation via Sinkhorn-Knopp: Application of Sinkhorn-Knopp iterations to approximate the posterior distribution for large input alphabets, enabling practical deployment in neural compression tasks where exact simulation is computationally prohibitive.
Application to Variable-Rate Compression: A framework for variable-rate lossy compression using stochastic VQ-VAEs without retraining, allowing a single model to sweep a continuous range of rate-distortion operating points.
Application to Differential Privacy: A scheme for communication-efficient distributed mean estimation (DME) with Central Differential Privacy (CDP) via the exact simulation of the Gaussian mechanism, supporting larger alphabets (up to 16-ary) than previous exact methods.

4. Experimental Results

Variable-Rate Image Compression (VQ-VAEs)

Setup: The authors applied the scheme to compress CIFAR-10 images (upscaled to $64 \times 64$ ) using a stochastic VQ-VAE with a codebook size of $N=256$ .
Performance: The polar-MLC scheme achieved rates between 1.6 and 7.8 bits/latent. It outperformed Importance Sampling (IS) baselines with varying chunk sizes and approached the performance of individually trained deterministic VQ-VAEs with fixed codebooks.
Efficiency: The method processed blocks of 8192 latent variables, demonstrating the ability to amortize overhead at long blocklengths.

Distributed Mean Estimation (DME) with CDP

Setup: The scheme simulated the Gaussian mechanism for CDP with $10^5$ clients, 512-dimensional vectors, and a 16-ary alphabet.
Performance: The polar-MLC scheme achieved lower communication rates across the privacy spectrum ( $\epsilon \in [0.05, 30]$ ) compared to the PFR baseline.
Speed: The polar-MLC algorithm processed 128 blocks of 4096 samples in approximately 3 seconds on a CPU, whereas PFR required significantly more time and was limited to smaller chunk sizes due to computational constraints.

5. Significance and Claims

The paper claims that while general channel simulation remains computationally difficult, searching for scalable constructions on narrower, practically relevant classes of channels (specifically discrete-to-continuous) is a promising direction.

Practicality: The proposed scheme offers a deterministic runtime and fixed sample complexity, making it suitable for real-world applications where infinite or variable stopping times are unacceptable.
Flexibility: By decoupling the simulation mechanism from the specific channel parameters through the use of shared randomness and permutation, the method provides a flexible tradeoff between the number of generated samples and the compression rate.
Exactness vs. Approximation: The work highlights that exact simulation is feasible for moderate alphabet sizes (e.g., $N \le 16$ ) using matrix permanents, while Sinkhorn-Knopp approximations suffice for larger alphabets (e.g., $N=256$ ) in compression tasks without significant performance degradation.
Privacy: The ability to exactly simulate the Gaussian mechanism on discrete inputs up to 16-ary alphabets provides a rigorous foundation for privacy-preserving distributed learning, avoiding the biases inherent in approximate methods like rejection sampling or dithered quantization.

The authors conclude that their approach successfully bridges the gap between theoretical channel simulation bounds and practical, scalable implementation in machine learning and privacy systems.