Summary
This paper presents a new algorithm, Greedy Rejection Coding (GRC), for Relative Entropy Coding (REC). REC is an alternative to entropy coding and quantization, which naturally interfaces with continuous variables and has applications in data compression. Current REC algorithms have faced challenges like slow runtimes or restrictive assumptions, hindering their widespread use. The new GRC method, along with its two variants GRCS and GRCD, generalizes a previous rejection sampling-based algorithm to arbitrary probability spaces and partitioning schemes. The authors demonstrate that GRC terminates almost surely, producing unbiased samples, and that GRCS has an optimal expected runtime and codelength for a wide range of one-dimensional problems. The effectiveness of GRC is showcased in a compression pipeline with variational autoencoders on the MNIST dataset, where it outperforms in compression efficiency.
Strengths
1. The paper introduces a new approach, Greedy Rejection Coding (GRC), to the field of rate-distortion compression (REC). The authors build on the rejection algorithm from Harsha et al., extending it to arbitrary probability spaces and partitioning processes. Theoretical results show that the GRC method is accurate and terminates successfully under certain general assumptions.
2. The authors validate their ideas with a proof-of-concept implementation using Variational Autoencoders (VAEs) on the MNIST dataset. They compare them against previous methods like A* coding. Their experiments validate the theoretical underpinnings of the algorithms and show improvements over prior work.
3. The paper deals with the challenge of coding overhead in compression problems. The authors propose a principled modification to the Evidence Lower Bound (ELBO) and entropy coding of GRCD's indices using a ζ distribution as innovative ways to improve compression efficiency.
Weaknesses
1. **Dependency on CDF:** A major limitation of the proposed Greedy Rejection Coding (GRC) approach is that it requires the ability to evaluate the cumulative distribution function (CDF) of the distribution Q. This could potentially limit the algorithm's practicality in situations where the CDF is difficult or computationally expensive to calculate.
2. **Applicability to Multivariate Distributions:** The paper mentions that the current approaches assume target-proposal pairs over the real line. This might limit the effectiveness of the proposed algorithm when dealing with multivariate distributions, as they are decomposed into univariate conditionals, resulting in additional coding overhead per dimension.
3. **Lack of Generalizability to Other Datasets:** The empirical validation of the approach is based on synthetic data and one real-world dataset (MNIST). How well the proposed approach would generalize to more complex datasets or tasks is unclear.
4. **Overhead Mitigation Measures:** The proposed methods to reduce the overhead, such as a modified ELBO and entropy coding using a ζ distribution, could add complexity to the algorithm. Moreover, it's not yet fully clear how much improvement they can bring in diverse scenarios.
5. **Efficiency Analysis:** While the paper discusses the runtime of the proposed algorithm compared to existing methods, it does not provide a detailed computational efficiency analysis. Therefore, it might be unclear how the proposed algorithm would perform under different computational resources.
Questions
Please see the Weaknesses.
Rating
5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
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.
Limitations
This work does not pose any ethical concerns.