Greedy Poisson Rejection Sampling

Summary

The paper proposes a new relative entropy coding algorithm for compression without quantization. Compression without quantization is an exciting line of research that tries to eliminate training-test mismatches in learned compression by avoiding discrete representations altogether. Consequently, one can losslessly compress data in a continuous latent variable model, such as a VAE, without quantizing the latent representation. The downside of existing algorithms for relative entropy coding is that their runtimes are intolerably slow. The paper makes a big step towards more runtime efficiency by designing new efficient rejection sampling approaches for transmitting samples from a variational posterior, especially in cases where the likelihood ratio between prior and posterior is uni-modal.

Strengths

+ Relative entropy coding is a somewhat under-appreciated but up-and-coming field of research at the intersection between information theory and machine learning. There are only a few papers in this domain. (For example, recent advances made compression in diffusion models possible [Theis et al., 2022].)  + The paper significantly improves runtime efficiency for these algorithms, paving the way toward its scalable deployment. Compared to runtime complexities exponential in the Renyi divergence, it achieves a runtime *linear* in the KL divergence between the target and proposal distributions. Notably, the involved algorithm is conceptually much simpler (and in practice faster) than relative entropy coding with A* coding, which achieves the same asymptotic scaling.  + Beyond its base version, the paper also proposes two computationally much more efficient extensions: parallel GPRS and branch&bound GPRS. Both approaches rely on non-trivial mathematical insights, e.g., additivity of a Poisson process.  + Moreover, in one-dimensional channel simulation problems where the density ratio is unimodal, the algorithm displays the theoretically-optimal runtime (unlike existing approaches such as A* sampling) + The paper shows a nice combination of solid empirical results and theory. For example, most claims on the runtime complexities and theoretical guarantees (finite runtime) are proven rigorously.

Weaknesses

See questions below. There are no immediate weaknesses evident, but some clarifying questions need to be addressed.

Questions

* Could the authors discuss in depth the commonalities and differences to a recent paper with a similar title, “adaptive greedy rejection sampling” (https://arxiv.org/pdf/2304.10407.pdf) that the authors already mentioned?  * The presentation at the beginning of Section 3 is very dense. For example, for an arbitrary P and Q, how is w_p approximated—analytically or based on samples? How does that affect the numerical solvability of Eq. 2? * It appears that the stretching function sigma is learned anew for every datum. How does this aspect affect the runtime, and is it respected in the scaling analysis? A discussion would be adequate.  * Parallelization and branch & bound: it appears that the parallelization affects the cost to *encode* data only, but not to *decode* data. Provided this is correct, could the authors explain why the encoding step is a bigger concern than decoding? In practice (e.g., video streaming), one mostly cares about reducing *decoding* complexity.  * Could the authors also comment on how they propose to simulate from the Poisson process restricted to subregions? It is unclear why this saves in runtime performance since sampling from a spatially-restricted Poisson process again amounts to rejection sampling.  Writing suggestion: * It took me a long time to understand why a temporal poisson process construction was used, where the original communication problem is time-independent. Maybe just say early on that including a temporal poisson process replaces rejection sampling with a deterministic criterion, a trick that was previously proposed for numerical integration (Maddison).

Rating

9: Very Strong Accept: Technically flawless paper with groundbreaking impact on at least one area of AI/ML and excellent impact on multiple areas of AI/ML, with flawless evaluation, resources, and reproducibility, and no unaddressed ethical considerations.

Confidence

5: You are absolutely certain about your assessment. You are very familiar with the related work and checked the math/other details carefully.

Soundness

4 excellent

Presentation

3 good

Contribution

4 excellent

Limitations

Limitations in terms of scaling and speed are sufficiently addressed. Societal impacts are a less important topic for general-purpose data transmission protocols.

Summary

The paper addresses the problem of representing a target distribution using the least possible number of bits. The authors refined the idea of encoding a sample from the target distribution as the first sample from the proposal distribution that passes a rejection sampling condition. The refined approach is shown to achieve runtime optimality.

Strengths

The idea of using a Poisson process to encode a target distribution is powerful. The strategy is well known but further investigations and attempts to make it more feasible could have an impact in various domains.

Weaknesses

The authors' technical contribution. could have been outlined more precisely. It is hard to understand why the new strategy is expected to be better than the A* algorithm or naive rejection sampling. The authors should have explained why "a criterion that does depend on the time variable" is better. In the introduction, the authors say that the distribution is assumed to be unimodal and 1 dimensional. This is a strong assumption and it is unclear why the proposed method requires it. Similar assumptions are made in Flemich 22. The authors may have specified whether these are also required in Maddison 16. The authors should have found a way of testing the algorithm on real-world data. The text could be more curated and structured.

Questions

- What are the requirements the target and proposal distributions should fulfil? Why do the distributions need to be 1-dimensional? Is this only for theoretical purposes (i.e. to estimate the runtime bounds)? Or would it be also a practical constraint? - How expansive is it to solve the ODE for computing \sigma? Should this be included in the total runtime? - How is the density ratio estimated? Is the method feasible if the target distribution is unavailable? - What are the key differences between the proposed algorithm, A*, and the approach described in Maddison 16? Why is rejection sampling supposed to be better than importance sampling? It would be good to include an intuitive explanation of why and when GPRS is faster.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

2 fair

Limitations

The authors do not discuss the limitation of the proposed approach. It is unclear what assumptions are required for the proofs. The theoretical runtime of related methods is not reported.

Summary

This paper focuses on the channel simulation problem, which finds applications in stochastic lossy compression. In contrast to the importance sampling approach A* coding (Flamich et.al. 2022) for channel simulation with Poisson processes, this work adopts a rejection sampling method. They demonstrate that the standard sampling approach may yield suboptimal code lengths. As an alternative, the authors propose a novel greedy rejection sampling algorithm called the Greedy Rejection Sampling (GPRS) algorithm. This algorithm composites the density ratio $r = \frac{dQ}{dP}$ with an invertible function referred to as the "stretch" function $\sigma$ that utilizes the temporal structure of the Poisson process without changing the target distribution. Theoretical findings establish the correctness and optimality of the proposed GPRS algorithm in terms of code length. Furthermore, the expected runtime of GPRS matches the runtime of standard rejection sampling. In addition to the vanilla GPRS, the authors introduce parallel and Branch-and-bound variants to further enhance the runtime of the algorithm. Specifically, the Branch-and-bound GPRS demonstrates a provable runtime improvement over A* coding when the density ratio exhibits unimodal characteristics. To validate the theoretical results, the authors conduct several toy experiments.

Strengths

- Mathematical derivations look rigorous. - This paper is well-written and easy to follow. - Theoretical results seem to be compelling. The authors successfully demonstrate, through rigorous analysis, that the GPRS algorithm outperforms both standard rejection sampling and A* coding in terms of either runtime or code length in some cases.

Weaknesses

- Some baselines and closely related works are not compared theoretically or empirically (See the first two bullets in Questions).

Questions

- GPRS is thoroughly compared to A* coding both theoretically and experimentally. However, it is unclear why the baseline standard rejection sampling (Algorithm 2) is not empirically compared in Section 4 to validate the theoretical assertion that GPRS enhances the code length efficiency compared to standard RS. - Additionally, while the more recent works dithered quantization methods (DQ) and greedy rejection coding (GRC) are briefly mentioned in the related works section, there is a lack of theoretical or empirical comparisons with GPRS. Although these methods may have distinct formulations and proof techniques, conducting some comparisons would be valuable in justifying the significance of GPRS and its potential advantages over alternative approaches. - GPRS needs to numerically solve an ODE for $\sigma^{-1}$ before the time steps. What about the extra cost in runtime?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

1: Your assessment is an educated guess. The submission is not in your area or the submission was difficult to understand. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

3 good

Contribution

3 good

Limitations

N/A

Summary

This paper investigates the problem of one-shot channel simulation, which can be used as lossy compression without involving quantization. A new rejection sampling algorithm called greedy Poisson rejection sampling (GPRS) is proposed. Then, a parallelized and a branch-and-bound variant is proposed. Those algorithms are analyzed regrading both correctness and runtime. Toy experiments on one-dimensional problems show that GPRS compares favourably against A* coding, the current state-of-the-art channel simulation protocol.

Strengths

The proposed GPRS is properly positioned against previous and concurrent works, and contains sufficient novelty. The proposed method has much better runtime complexity compared with previous SOTA A* coding. The manuscript is well written and enough background information is provided for general readers.

Weaknesses

Though this manuscript is a theoretical contribution, it would be better to discuss more about promising application scenarios and current gaps regarding both performance and efficiency, which can encourage more future works in this field and facilitate more applications of similar techniques.

Questions

L331-334, please explain in more detail about the application scenario of efficient channel simulation protocol for multivariate Gaussians.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

4 excellent

Contribution

3 good

Limitations

see above.

Summary

This paper proposes a new algorithm for lossy compression, using ideas from Poisson rejection sampling. Given a sample $y \sim P_y$, Alice wants to communicate the smallest number of bits possible such that Bob can simulate $x \sim P_{x | y}$, when Alice and Bob have access to the distribution $P_{x, y}$ (and shared randomness to allow simulation). The proposed algorithm achieves an almost optimal codelength by rejection sampling -- by introducing a temporal random variable t, Alice can communicate the hitting time $t$ for which $(t, X_t)$ lies under an appropriately defined function $\phi$. Variations of this algorithm are suggested: one variation is to parallelize using $L$ servers to reduce the runtime by a factor of $L$, and another binary search variant which gives an exponential improvement when the Radon-Nikodym derivative of $dP_{x|y} / dP_{x}$ is bounded.

Strengths

- The paper has several nice ideas from information theory, and seems to be the first that can provably achieve runtimes predicted by Li and El Gamal. - The algorithm is built on A* coding, but is more robust, in the sense that while the runtime of A* coding depends on the Renyi entropy between $P_{x|y}$ and $P{x}$, the runtime of the proposed algorithm is proportional to the KL divergence between them, which may be much smaller and finite even when the Renyi entropy is infinite.

Weaknesses

- The rejection sampler requires access to likelihoods of the conditional distribution and marginal, and hence it's not clear how much this can be generalized. - The inverse function in Eqn (2) is solved numerically. How would this be computed for distributions with harder CDFs? - All experiments are toy experiments on Gaussian, Binomial variables etc. - The experiments are for scalar random variables, and extending to higher dimensions would be extremely non-trivial. The authors state that extending this to multivariate Gaussians is an open problem. - The paper tries to establish connections with areas like generative modelling by arguing that source compression is useful in VAEs/ latent diffusion models, but this is probably not correct. The works of Theis et al for example use generative models for compression, not the other way around. Minor: - The name GPRS for a communication protocol is probably a poor choice given that it's an existing standard. - $\mathbb{V}$ in Theorem 3.1 is undefined.

Questions

Questions are listed in the weaknesses section. My main concern is that this is probably a poor fit for NeurIPS. The theorems are nice, but the impact to a NeurIPS audience is probably extremely limited, given that the algorithms are only feasible for explicit likelihood models and scalar random variables.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

There needs to be more discussion about the limitations of this work, especially if the authors are going to mention connections between the proposed algorithm and compression of neural networks. The connections to generative modelling are extremely weak.

Thanks for your response

I have read the authors' response. My rating remains high. I hope the authors use my feedback not only to respond to me as a reviewer but also adopt changes to improve the paper's clarity in terms of practical aspects of their algorithm, e.g., when it comes to the stretching function and calculating w_p. Overall, I congratulate the authors on their nice work.

Thank you for your answers

After reading the authors' answers and the other reviewers' comments, I am ready to support acceptance. I have raised my score accordingly. I still have concerns about the practical application of the scheme but recognise this is a theoretical work. Real data evaluation is probably not needed.