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

Channel simulation has recently emerged as a useful component in machine learning systems where samples from a prescribed probability distribution are to be compressed. We study the simulation of discrete-to-continuous channels and present a scheme which performs exact simulation using a fixed-size shared random pool containing one or more samples from each potential target distribution. Unlike sampling-based schemes which generate a potentially unbounded sequence of independent samples from a proposal distribution, the number of samples used by our algorithm is finite and fixed in advance. To the best of our knowledge, this is the first exact scheme with such a property for general discrete-to-continuous channels. The key ingredient in our approach is a latent permutation which hides the correspondence between the shared random samples and their generating distributions. We also provide a flexible tradeoff between the number of generated samples and the compression rate. Exploiting the structure exposed by our algorithm, we use polar and multilevel coding to scale to long blocklengths in $O(n\log n)$ time to benefit from reduced per-symbol overhead. In our experiments, exact simulation remains fast at large blocklengths, and for input alphabet sizes up to $N=16$; for larger alphabets our approach further admits a Sinkhorn-Knopp approximation of the posterior induced by the latent permutation. We give applications to variable-rate compression with stochastic VQ-VAEs and differentially private distributed mean estimation via exact simulation of the Gaussian mechanism, showing gains over baselines in both wall-clock speed and communication rate.