Research map / Learning theory and algorithms / Sample complexity
Channel Simulation and Distributed Compression with Ensemble Rejection Sampling
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows rejection sampling (RS) and Ensemble Rejection Sampling (ERS) can achieve near-optimal channel simulation rates via a sorting-based coding scheme, and derives a distributed matching bound for ERS comparable to the Poisson Matching Lemma, applied to Wyner-Ziv image compression on MNIST.
Problem
Channel simulation and distributed matching (correlated sampling with limited communication) need Monte Carlo schemes that are unbiased, terminate with finite proposals, and achieve high matching probability; standard RS has low matching probability and PMC/PML needs infinite proposals.
Approach
A sorting-based encoding of the accepted proposal index (group index plus rank of the accepted uniform within the group) gives near-optimal coding cost for RS, and ERS (RS over batches of Gumbel-max IS proposals) is shown to have a distributed matching probability approaching PML while keeping samples unbiased.
Key results
- ERS matching probability converges to PML as batch size grows, and ERS with batch-index communication achieves higher matching probability than IS at the same average proposal count.
- On synthetic Gaussian sources at -23 dB target, ERS outperforms IML at distortion levels near target (below -22.6 dB) because IML samples are biased, and approaches PML.
- Standard RS reaches -17 dB at 10 bits when targeting -23 dB, far from target; the sorting-based RS coding cost bound is R <= I(X;Y) + log(I(X;Y)+1) + 9 bits.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use ERS instead of IML at distortion levels below -22.6 dB | Distributed compression on synthetic Gaussian sources · Synthetic Gaussian sources | distortion | Helped |
| Use ERS instead of IML below -22.8 dB | Distributed compression on synthetic Gaussian sources · Synthetic Gaussian sources | distortion | Helped |
| Use ERS instead of IML at appropriately chosen batch size and rate | Distributed compression on synthetic Gaussian sources · Synthetic Gaussian sources | distortion | Helped |
| Use standard RS instead of ERS | Distributed compression on synthetic Gaussian sources · Synthetic Gaussian sources | distortion | Hurt |
| Use ERS instead of IML with feedback | Distributed image compression · MNIST | rate-distortion performance | Helped |
| Use ERS instead of IML without feedback near the target distortion | Distributed image compression · MNIST | rate-distortion performance | Helped |
Surprising findings
- Standard RS and greedy RS can have matching probability approaching zero in constructed examples even when target densities are equal at the point, below PML's bound.
- IML's sample bias remains high even with a large number of proposals (4 omega), hurting rate-distortion performance.
Limitations
- Runtime is O(omega), which can be large when the bounding constant is large.
- Batch-index communication adds overhead (around 4 bits, reduced by joint compression of n samples).
- PML cannot be applied when the decoder's density ratio upper bound is unknown, so the practical method relies on a batch-index workaround.
Experimental setup
Datasets: MNIST synthetic Gaussian sources
Benchmarks: MNIST
Metrics: matching probability rate-distortion (dB) coding cost (bits) pixel MSE embedding MSE
Baselines: Poisson Matching Lemma Importance Matching Lemma standard rejection sampling NDIC
Builds on: Poisson Matching Lemma Importance Matching Lemma Ensemble Rejection Sampling Greedy Rejection Sampling Gumbel-max trick
Closest papers by meaning
- Universal Sample Coding (NeurIPS 2024 · similarity 0.87)
- List-Level Distribution Coupling with Applications to Speculative Decoding and Lossy Compression (NeurIPS 2025 · similarity 0.85)
- Beyond Communication Overhead: A Multilevel Monte Carlo Approach for Mitigating Compression Bias in Distributed Learning (ICML 2025 · similarity 0.84)
- Accelerated Sampling from Masked Diffusion Models via Entropy Bounded Unmasking (NeurIPS 2025 · similarity 0.84)
- Jump Your Steps: Optimizing Sampling Schedule of Discrete Diffusion Models (ICLR 2025 · similarity 0.83)
- Scalable Discrete Diffusion Samplers: Combinatorial Optimization and Statistical Physics (ICLR 2025 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.