Greedy Poisson Rejection Sampling
0
➖
Sign in to get full access
This paper solves a key data compression problem called one-shot channel simulation. The goal is to efficiently encode samples from a target distribution using a coding distribution, minimizing the average number of bits needed.
The authors present a new algorithm, greedy Poisson rejection sampling (GPRS), that optimally solves this problem for certain one-dimensional cases. GPRS works by cleverly searching over points in a Poisson process to perform rejection sampling.
The paper proves the correctness and analyzes the runtime of different versions of GPRS. Experiments show that GPRS significantly outperforms the previous best method, A* coding.
One-shot channel simulation has applications in neural data compression and differential privacy. The authors' fast, broadly applicable solution in GPRS could enable wider use of these techniques as an alternative to slower quantization-based methods.
This summary was produced with help from an AI and may contain inaccuracies - check out the links to read the original source documents!
Related Papers
➖
0
Greedy Poisson Rejection Sampling
Gergely Flamich
One-shot channel simulation is a fundamental data compression problem concerned with encoding a single sample from a target distribution $Q$ using a coding distribution $P$ using as few bits as possible on average. Algorithms that solve this problem find applications in neural data compression and differential privacy and can serve as a more efficient alternative to quantization-based methods. Sadly, existing solutions are too slow or have limited applicability, preventing widespread adoption. In this paper, we conclusively solve one-shot channel simulation for one-dimensional problems where the target-proposal density ratio is unimodal by describing an algorithm with optimal runtime. We achieve this by constructing a rejection sampling procedure equivalent to greedily searching over the points of a Poisson process. Hence, we call our algorithm greedy Poisson rejection sampling (GPRS) and analyze the correctness and time complexity of several of its variants. Finally, we empirically verify our theorems, demonstrating that GPRS significantly outperforms the current state-of-the-art method, A* coding. Our code is available at https://github.com/gergely-flamich/greedy-poisson-rejection-sampling.
Read more4/1/2024
📉
0
Some Notes on the Sample Complexity of Approximate Channel Simulation
Gergely Flamich, Lennie Wells
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_infty[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 $D_{KL}[Q Vert P]$, we can exploit global-bound, depth-limited A* coding to ensure $mathrm{TV}[Q Vert P] leq epsilon$ and maintain optimal coding performance with a sample complexity of only $exp_2big((D_{KL}[Q Vert P] + o(1)) big/ epsilonbig)$.
Read more5/16/2024
0
Diffusion Rejection Sampling
Byeonghu Na, Yeongmin Kim, Minsang Park, Donghyeok Shin, Wanmo Kang, Il-Chul Moon
Recent advances in powerful pre-trained diffusion models encourage the development of methods to improve the sampling performance under well-trained diffusion models. This paper introduces Diffusion Rejection Sampling (DiffRS), which uses a rejection sampling scheme that aligns the sampling transition kernels with the true ones at each timestep. The proposed method can be viewed as a mechanism that evaluates the quality of samples at each intermediate timestep and refines them with varying effort depending on the sample. Theoretical analysis shows that DiffRS can achieve a tighter bound on sampling error compared to pre-trained models. Empirical results demonstrate the state-of-the-art performance of DiffRS on the benchmark datasets and the effectiveness of DiffRS for fast diffusion samplers and large-scale text-to-image diffusion models. Our code is available at https://github.com/aailabkaist/DiffRS.
Read more5/29/2024
🌀
0
Enhancing Channel Estimation in Quantized Systems with a Generative Prior
Benedikt Fesl, Aziz Banna, Wolfgang Utschick
Channel estimation in quantized systems is challenging, particularly in low-resolution systems. In this work, we propose to leverage a Gaussian mixture model (GMM) as generative prior, capturing the channel distribution of the propagation environment, to enhance a classical estimation technique based on the expectation-maximization (EM) algorithm for one-bit quantization. Thereby, a maximum a posteriori (MAP) estimate of the most responsible mixture component is inferred for a quantized received signal, which is subsequently utilized in the EM algorithm as side information. Numerical results demonstrate the significant performance improvement of our proposed approach over both a simplistic Gaussian prior and current state-of-the-art channel estimators. Furthermore, the proposed estimation framework exhibits adaptability to higher resolution systems and alternative generative priors.
Read more5/7/2024