Accelerating Relative Entropy Coding with Space Partitioning

Summary

The authors provide a formalization on how to introduce search heuristics for channel-simulation (sometimes called "relative entropy coding" in the ML literature). The encoder and decoder agree a priori on a binning scheme that divides the support of the prior/public distribution, which is used to control the search during encoding. Disclaimer: while I'm familiar with the basic literature (e.g. REC, PFRL, ORC), I haven't kept up with the literature since 2022. I'm more than willing to change my scores if the authors point out I missed something or didn't fully understand the contributions.

Strengths

- The paper is nicely written. This is notably a complicated topic to understand and I feel the authors made quite a didactic effort. - The excess code-length is bounded for the distributions found in practice for NTC.

Weaknesses

- Line 21: I feel this statement is misleading. In the first scenario (lines 14 to 20), the actual value taken on by the random variable is what is being transmitted. Meanwhile, in channel-simulation, all we care about is that the received quantity be distributed according to $Q_{Z | X}$. These are fundamentally different problems. The comparison would make some sense if, in the first scenario, the decoder is necessarily stochastic, as decoding can be seen as sampling from some posterior distribution over the data conditioned on the latent.

Questions

- Line 66: Why is it important for the state $S$ to be random? I don't see this being used anywhere. - Line 213: The non-exactness here is with respect to $Q$. REC-like algorithms are usually formulated to be used in the latent space, i.e., the encoder wants to send a sample from $Q_{Z | X}$, but what we care a about from a practical standpoint is to transmit the data $X$ according to some rate-distortion trade-off. Shouldn't this discussion be formulated around the data space (maybe this is too hard of a problem?)? - Regarding the binning prior $\pi$. The target distribution is a function of $X$, i.e., $Q_{Z | X}$. Isn't it hard to pick a good $\pi$ given this distribution is constantly changing?

Rating

7

Confidence

3

Soundness

4

Presentation

4

Contribution

3

Limitations

- Line 267: The results are computationally intensive, and thus impractical, even for MNIST. Requiring the value of mutual information to be known by encoder/decoder seems a bit much (the authors mention this in the limitations section).

Summary

**Global disclaimer:** I am very unfamiliar with the topic of the paper. I did my best to try and read the literature and understand as much as I could but my input may be very limited. **Summary:** The paper focus on relative entropy coding (REC) algorithms and propose to circumvent a major pitfall which is the prohibitive encoding time. Indeed the commonly used PFR algorithm requires to sample points until finding a good enough alignment with the target distribution. Efficient algorithms only exist in dimension 1. The authors propose to refine the algorithm by partitioning the search space into bins that will better drive the sampling from the coding to the target distribution. The author then theoretically prove that their approach by is founded (Theorem 3.1), and derive precise codelength bounds for the space partition algorithm. They also discuss a generic partitionning strategy. Finally, a benchmark highlight the benefits of the space partition approach for compression against the standard PFR algorithm on toy example and real datasets.

Strengths

The paper is very didactic, well written and is quite nice to read. The proposed approached is well structured and detailed (sections 3.1). The theory exposed in the paper is sound and the proof seem correct to me. The benchmark is well made and honest. Finally the appendix is very helpful, I particularly appreciated appendix B that shed some light on the partition strategy.

Weaknesses

The idea is finally quite elementary: dividing the space once for all into bins. The proofs are "elementary" (still technical) refinements from the classical PFR theory (starting point is often [Li and El Gamal, 2018] and [ Flamich, 2024]).

Questions

- How the bounds from Theorem 3.1 do compare with the bound from [Li and El Gamal, 2018, Theorem 1] in the same setting, i.e. when $J=1$? More generally, could we recover a bound such as Proposition 3.2 but with a dependence in $J$. - The number of intervals for each axis is justified in Appendix B, but could the author give more details about how these interval are constructed? - The proposed approach to the construction of the bins follow depends on the chosen representation. Would it be possible to automatically find a transformation prior to the bining that would provide better results while keeping the same strategy? - Is there a way to update $\pi$ along the algorithm, using e.g. the Gumbel trick and gradient based method? - It would be interesting to add an ablation study on the number of intervals per axis. - Table 1 shows some improvements in number of steps but it would be interesting to have the same thing in time. Could you elaborate about Figure 3, I do not understand what is meant by runtime here.

Rating

8

Confidence

2

Soundness

3

Presentation

4

Contribution

2

Limitations

The approach is not fully generic and despite very good success on some examples, it could fail on other as clearly explained in Appendix B. Typos: the punctuation missing in the maths of the appendix **Proposed score:** My rating is based on the fact that the paper is sound, the maths are correct but the scope of the idea is quite simple. I do believe that this work is well presented, interesting and worth publication. On the other hand I am not familiar with this field. As such, I propose a score of 5/10 (a weak accept) but I am very open to discussion with the authors and the other reviewers.

Summary

The paper proposes a space partioning technique to speed up relative entropy coding. In entropy coding the sender first transforms X into a representation Z that they encode. This particular step can done by Poisson functional representation (PFR). Unfortunately, PFR’s random runtime can be a significant drawback. To circumvent this issue, the author propose a space partitioning scheme to reduce runtime in practical scenarios. This can be seen (sic) as a search heuristic to a standard REC algorithm The author then proceed to give a theoretical analysis of the method and support their improvement with numerical results.

Strengths

The paper adresses an important practical problem with many important application. The algorithm and theoretical results are stated clearly. The context and related work is clear to the reviewer (who is not an expert in the field). The numerics show clearly the advantage/improvements yielded by the technique.

Weaknesses

Although the proposed technique is "simple and efficient", it lacks discussion whether the binning technique impacts the final result (besides codelength).

Questions

- it is unclear to the reviewer how the grid should be set. -it is unclear to the reviewer how the choice of prior for the binning distribution influences the algorithm. - the weakness section raises a question that I would like to see adressed: how is the binning technique impacting the final result (besides codelength). I agree that the uniform distribution seems like a natural choice, but it would be good to discuss the choice of prior here I will happily increase my grade if those questions are properly adressed.

Rating

7

Confidence

2

Soundness

3

Presentation

3

Contribution

3

Limitations

The authors recognize some clear limitations of their approach in the conclusion section. In particular, the approach proposed by the authors is too limited and does not extend to all possible practical cases. The reviewer agrees with those limitations, although still believes they should not be an obstacle for publication. as this work is a "first step" in this direction.