Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The paper performs lossless image compression with invertible flows. The authors propose a way to convert flows to be numerically invertible, and a coder for uniform distributions.
main_review: I'm reviewing this paper from a compression perspective. I know the invertible flow literature on a high level only. With that in mind, the idea that is used to convert flows makes sense, and is novel as far as I know. I like the formulation of the paper, it is concise but understandable.

My main concern is that I do not understand the point and/or novelty of the proposed "Uniform Base Conversion System". I have two concerns:
- [Update: addressed by rebuttal] Are we using UBCS also to encoding the final $z$? It seems suboptimal to assume $z\sim U$. Could you elaborate on the distribution used for z? If it's not uniform, what coder do you use?
- [Update: addressed by rebuttal]  The goal is to compress symbols that are uniformly distributed according to $U(0, R)$. To me it seems many of the existing algorithms should be fast if adapted to this assumption. In particular, if there exists an $r$ such that $R=2^r$, you can write a simple algorithm in C that does not use any multiplication, just bitshifts and additions, that should be blazingly fast. For other $R$, I'm sure that the tabled variant of ANS, tANS, should also allow for very fast encoding and decodings, as it also does not use any multiplications -- in contrast to the presented algorithm. It seems unfair to compare to a particular implementation of rANS. Overall, this is maybe a nit-picky point, as the proposed variant is faster than the compared rANS, but it just seems that with a bit more tinkering, an even much faster variant could have been found. In light of what exists, claims of novelty should probably be toned down. Also, L293, "... binary search protocol required at decode time ..." seems unfair, as AC can trivially be adapted to use a lookup table for fixed uniform distributions.

Given the comments on improved/practical speed in the Introduction, I would have liked to see a table with runtimes on full-resolution datasets such as CLIC.pro.

Minor comments:
- L82: why is a triple equality used.
- L85: Footnote could be inlined. 
- L185 could use a restatement of $\delta$ and $-\log \delta = kd$
limitations_and_societal_impact: The paper addresses this.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The two key contributions in this work are:

1) A construction method for low-error discretized approximations to a wide class of continuous normalizing flow layers
2) An entropy coding method the discrete uniform distribution that the authors call Uniform Base Conversion Systems (UBCS) that is simple to implement and is very fast.

The authors combine these two contributions in their experiments and achieve state-of-the-art compression ratios on the standard lossless image compression benchmark datasets (ImageNet, Cifar10, CLIC, DIV2K), while also achieving large gains in terms of compression speed compared to other methods.

main_review: # Strengths
There are several novel ideas presented in the paper. The modular scale transform (MST) is simple, easy to implement and the authors show using some results from [1] that it has desirable properties. Then, the authors show how MST can be used as the fundamental building block for discrete approximations of general elementwise flows which then leads to autoregressive and 1 x 1 convolutional flows, the correctness and efficiency of which is all guaranteed by the correctness and efficiency of MST.

The authors adopt some ideas from [2] to remove the overhead introduced by the quantization mesh and call it bits-back dequantization.
The authors introduce Uniform Base Conversion Systems (UBCS). While a very simple scheme, it is very fast and just the right entropy coding method to use in conjunction with the discrete flow approximation proposed by the authors.

The experimental method in this work is standard for learned lossless image compression, and the authors achieve very good results on all considered datasets. Concretely, they match or slightly improve the current state-of-the-art compression performance on all datasets, while achieving a large improvement in terms of run-time compared to other methods.

The paper is well-written with a logical and easy-to-follow layout. Nice submission overall.

[1] Shifeng Zhang, Chen Zhang, Ning Kang, and Zhenguo Li. iVPF: Numerical invertible volume preserving flow for efficient lossless compression. arXiv 2021

[2] Jonathan Ho, Evan Lohn, and Pieter Abbeel. Compression with flows via local bits-back coding. NeurIPS 2019

# Weaknesses
There are no major weaknesses that I could spot. There are some minor issues, concretely:
- In the abstract it says "We first develop UBCS, ...", but in fact it is developed after the introduction of iFlow.
- On several occasions (e.g. in Algorithms 1 and 4) the authors mention "decoding" an object from a distribution.
  I believe that the authors here refer to the fact that entropy coding methods can be viewed as "invertible samplers",
  where "decoding" can be identified with sampling the probability distribution at hand using the currently available bit stream.
  I don't think this is clarified anywhere in the main text, and I also don't think that this is common terminology in the wider community. Therefore I would suggest that the authors either clarify it or change their wording.
- Footnote 2: I think the language used is imprecise, I think the authors mean that the intervals must _partition_ the domain of $f$.
- Could the authors clarify what the relevance of Eq (4) is? Is it to show that $R$ in the MST implementation of Eq (3) will have the appropriate magnitude so that Prop (2) holds?
- Line 59: "Jacabian matrix"
- Line 115: subscript of $z$ in $\bar{z}_l = f(\bar{x}_h)$ should be $h$.

limitations_and_societal_impact: They have.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes iFlow - a method to improve lossless compression using flow-based generative models. Specifically, the paper proposes two novel methods, the Modular Scale Transform (MST) and Uniform Base Conversion Systems (UBCS). MST is a method of obtaining a numerically invertible scale transform, to be used as a building block for flow layers. UBCS is a codec for uniformly distributed symbols, designed for speed.

The authors demonstrate that the MST results in superior bitrates when compared to similar techniques, and that UBCS is faster for coding uniform symbols than competing entropy codecs.
main_review: The results in this work appear to be quite interesting. There does appear to be an advance in coding rate and compression speed for lossless compression using flow models (or even any probabilistic generative model, since flow models are currently the SOTA). The realisation that the majority of the coding can be done via uniformly distributed symbols is neat, and then showing that a simple codec (UBCS) can code these close to the Shannon entropy much faster than a modern codec like rANS is I think an important realisation. This could potentially have important ramifications for the field of learned lossless compression as previous works have not utilised this. For example [1] uses a uniform codec for the latents since a Gaussian is discretised into buckets of uniform probability. They use rANS for the coding though, which appears not to be optimal in terms of speed.

This work is in general well-written and precise in its statements. Results are given clearly and theorems and motivations are well laid out.

The concern I have with this work is that it is extremely close in content to [2]. [2] is a recent paper but it is cited and clearly built upon in this work. One of the major contributions of this work is the MST, which the authors admit is inspired by MAT (just changing affine to scalar) from [2]. They look very similar to me, and although the schemes are clearly slightly different I can't quite work out why MST is superior, and it doesn't seem to be stated in this paper. Could the authors comment and make clear exactly why MST is an iteration over MAT?

Much like in [2], after describing the MST, time is then taken to show that various flow compression schemes can be implemented using these numerically invertible flows. It doesn't appear that much has changed between these derivations.

UBCS is still a novelty, but it is in someways quite a simple revelation - we can code uniform symbols fast. The codec itself is straightforward. This is not a bad thing, but with the rest of the paper being very closely related to another work, it does detract from the overall novelty somewhat.

If the authors addressed exactly the motivation for MST over MAT then I consider upgrading my score.

Edit: after response I am upgrading my score as per the above.

[1] Practical Lossless Compression with Latent Variables using Bits Back Coding
James Townsend, Tom Bird, David Barber
ICLR 2019

[2] iVPF: Numerical Invertible Volume Preserving Flow for Efficient Lossless Compression
Shifeng Zhang, Chen Zhang, Ning Kang, Zhenguo Li
CVPR 2021

limitations_and_societal_impact: They have addressed the limitations. I don't see any negative societal impact.
review_title: null

final_score: rating: 9: Top 15% of accepted NeurIPS papers, strong accept
review_content: summary: This paper proposes a lossless image compression method based on normalizing flows. In order for this class of flows to be useful for compression, they need to be working in the quantized domain, and (of course) have to be invertible. The authors present an extension to a much more general class of functions that can be used in the composition formulation of the flow, therefore being able to achieve higher rates of compression than what was possible before. Additional contributions include using a variant of bits-back coding to achieve higher compression rates, and a much faster entropy coding method that vastly outperforms rANS.
main_review: This paper could be the start of a many more papers using flows for compression. Thus far there are very few papers published in this area that use normalizing flows due to the very challenging nature of the problem. The key blocking factor that this paper addresses is how to use more general composable functions than what was possible before (which were very weak functions). This improvement might make this paper a turning point in utilization of this class of methods.

While I did try to do my best to understand the entirety of the paper, I did not follow the proofs closely as I am not super-familiar with the vast amount of background knowledge needed to understand methods ranging from flows, which I am familiar with, to entropy coding and bits-back coding (which I am much less familiar with). I budgeted about 3 hours for this paper, and it was really not enough to get fully up to speed with everything needed here. 

With that said, the main body of the paper was very clearly written, and I wish more papers were as well written as this one. The supplementary materials contain a vast amount of proofs, and I think this is very welcomed given the vast quantity of information presented in this work.

The results are state o the art, and the only criticism I can find is that the decoding/encoding time is only listed for toy problems. With that said, the number of baselines, including state of the art classical codecs is very impressive and very welcomed.
limitations_and_societal_impact: This looks ok.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper introduces a new normalizing flow method for lossless compression. The key innovation is a new family of techniques to convert a continuous flow into a discrete bijector, which can transform binary codes without information loss. The authors compare compression performance and encoding speed with a large family of state-of-the-art neural compression methods.
main_review: The authors introduce a method to convert normalizing flows into discrete bijectors that can be used for lossless compression. This allows for the use of a trained continuous flow for lossless compression without lossy quantization of the encoded latent code. Specifically, the authors introduce the "modular scale transform", which approximate element-wise scalar multiplications with integer multiplications and divisions plus a remainder that is encoded separately and follows a uniform distribution. 

I premise that my expertise in the area is limited. So said, the work seems to be solid and the theoretical results straightforward. The main innovation is the modular scale transform, which is a very simple trick. This simplicity however is not necessarily a problem as far as the innovation is original. In the following, I will list the main strengths and weaknesses of the paper. 

Strengths:
- The main innovation is simple and elegant and has a wide applicability. The modular scale transform is used to approximate arbitrary monotonic transformation through locally-linear approximations and then complex normalizing flow layers using a similar approach.
- The experiments are performed on a rather large number of datasets and comparison are made with a large number of relevant baselines.

Weakness:
- The main contribution is a very simple trick. Given that the field is young, I can image that it is original. However, it is possible that a very similar method is already in wide use in a related literature. Given my scarce familiarity with the compression literature, I trust the judgment of the other reviewers on this matter. 
- The experiments are difficult to interpret as the authors do not provide error bars on their result. I suggest to use a bootstrap technique in order to quantify the statistical variability of the performance.



limitations_and_societal_impact: Limitations and social impact are  discussed, albeit briefly.
review_title: null

Meta-review: The main concerns by the reviewers were adequately addressed during the rebuttal and subsequent discussion between the authors and reviewers. The reviewers unanimously vote for accepting this paper. 

The metareviewer sincerely thanks the authors and reviewers for engaging into fruitful discussions.
Decision: Accept (Spotlight)