# Some Notes on the Sample Complexity of Approximate Channel Simulation

arXiv: https://arxiv.org/abs/2405.04363 · HTML: https://mlsanity.com/paper/2405.04363/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 25 references that are in the map.
- First posted on arXiv 7 May 2024.

## Builds on (most cited first, 14 of 14)

- [The Perception-Distortion Tradeoff](https://mlsanity.com/paper/1711.06077/) (2017)
- [High-Fidelity Generative Image Compression](https://mlsanity.com/paper/2006.09965/) (2020)
- [A* Sampling](https://mlsanity.com/paper/1411.0030/) (2014)
- [Lossy Compression with Gaussian Diffusion](https://mlsanity.com/paper/2206.08889/) (2022)
- [Universally Quantized Neural Compression](https://mlsanity.com/paper/2006.09952/) (2020)
- [Minimal Random Code Learning: Getting Bits Back from Compressed Model Parameters](https://mlsanity.com/paper/1810.00440/) (2018)
- [Compressing Images by Encoding Their Latent Representations with Relative Entropy Coding](https://mlsanity.com/paper/2010.01185/) (2020)
- [Algorithms for the Communication of Samples](https://mlsanity.com/paper/2110.12805/) (2021)
- [On the advantages of stochastic encoders](https://mlsanity.com/paper/2102.09270/) (2021)
- [Compression with Bayesian Implicit Neural Representations](https://mlsanity.com/paper/2305.19185/) (2023)
- [Optimal Compression of Locally Differentially Private Mechanisms](https://mlsanity.com/paper/2111.00092/) (2021)
- [The Sample Complexity of Approximate Rejection Sampling with Applications to Smoothed Online Learning](https://mlsanity.com/paper/2302.04658/) (2023)
- [What makes an image realistic?](https://mlsanity.com/paper/2403.04493/) (2024)
- [RECOMBINER: Robust and Enhanced Compression with Bayesian Implicit Neural Representations](https://mlsanity.com/paper/2309.17182/) (2023)

## Built on by (most cited first, 4 of 4)

- [Accelerating Relative Entropy Coding with Space Partitioning](https://mlsanity.com/paper/2405.12203/) (2024)
- [Scalable Differentially Private Data Compression via Diffusion and Stochastic Codes](https://mlsanity.com/paper/2607.03392/) (2026)
- [Accelerating Diffusion Sampling via Speculative Draft Trees](https://mlsanity.com/paper/2609.17691/) (2026)
- [Partition Function Estimation under Bounded f-Divergence](https://mlsanity.com/paper/2602.23535/) (2026)

## Abstract (arXiv)

Channel simulation algorithms can efficiently encode random samples from a prescribed target distribution Q and find applications in machine learning-based lossy data compression. However, algorithms that encode exact samples usually have random runtime, limiting their applicability when a consistent encoding time is desirable. Thus, this paper considers approximate schemes with a fixed runtime instead. First, we strengthen a result of Agustsson and Theis and show that there is a class of pairs of target distribution Q and coding distribution P, for which the runtime of any approximate scheme scales at least super-polynomially in D_∞[Q Vert P]. We then show, by contrast, that if we have access to an unnormalised Radon-Nikodym derivative r propto dQ/dP and knowledge of DKL[Q Vert P], we can exploit global-bound, depth-limited A* coding to ensure TV[Q Vert P] ≤ ε and maintain optimal coding performance with a sample complexity of only exp2big((DKL[Q Vert P] + o(1)) big/ εbig).