2024/01/29 by Daniel Goč, Gergely Flamich, Goc, Daniel +1 · 2 citations
Computer Science · Engineering · #68Q25 #Advanced MIMO Systems Optimization #Error Correcting Code Techniques #F.2 #FOS: Computer and information sciences #G.3 #Information Theory (cs.IT) #Wireless Communication Security Techniques
paper · pdf · doi:10.48550/arxiv.2401.16579
openalex publication_date 2024/01/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
One-shot channel simulation has recently emerged as a promising alternative to quantization and entropy coding in machine-learning-based lossy data compression schemes. However, while there are several potential applications of channel simulation - lossy compression with realism constraints or differential privacy, to name a few - little is known about its fundamental limitations. In this paper, we restrict our attention to a subclass of channel simulation protocols called causal rejection samplers (CRS), establish new, tighter lower bounds on their expected runtime and codelength, and demonstrate the bounds' achievability. Concretely, for an arbitrary CRS, let Q and P denote a target and proposal distribution supplied as input, and let K be the number of samples examined by the algorithm. We show that the expected runtime 𝔼[K] of any CRS scales at least as exp2(D_∞[Q || P]), where D_∞[Q || P] is the Rényi ∞-divergence. Regarding the codelength, we show that DKL[Q || P] ≤ DCS[Q || P] ≤ ℍ[K], where DCS[Q || P] is a new quantity we call the channel simulation divergence. Furthermore, we prove that our new lower bound, unlike the DKL[Q || P] lower bound, is achievable tightly, i.e. there is a CRS such that ℍ[K] ≤ DCS[Q || P] + log2 (e + 1). Finally, we conduct numerical studies of the asymptotic scaling of the codelength of Gaussian and Laplace channel simulation algorithms.