Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: This paper presents a method for adapting a learned compression model to improve the lossless compression rate over a set of data to be transmitted, e.g. a set of images. The method assumes a generative model has been optimized over a large dataset, and several models are explored empirically including HiLLoC and IDF++. The model represents a distribution over data items that can be used as the entropy model for a lossless compression algorithm (Huffman coding, arithmetic coding, ANS, etc.). The core idea in OSOA is to divide the data to be compressed into separate batches and to adapt the pre-trained model on each batch before coding the next batch.

The authors show that this approach reduces total bit rate, outperforms training and transferring a separate model for each batch (at least in several cases), that the method can be adapted to FIFO and FILO algorithms (e.g. range coding vs ANS), and that there is a trade-off between runtime and compression rate based on early stopping of the update algorithm.
main_review: Originality = 2/5. While I haven't see this kind of online adaptation before for deep generative models, it does follow the general pattern of "backward adaptation", which is very common in image and video coding.

Quality = 4/5. The authors do support their claims with various empirical evaluations including comparison multiple methods for fine-tuning a model. What's not clear is that benefits of OSOA hold up for larger images (or other large data items). This can be seen in Table 2, where OSOA provides a huge rate savings for small images (32x32) since the effective bpd of the model is large compared to the 1024 pixels in each image. For 128x128 images, however, the bpd of the model is smaller (now there are 16,384 pixels) so the most aggressive finetuning approach maintains a small rate advantage of OSOA. OSOA may have a runtime advantage in this case, but it's a less clear net advantage.

Clarity = 4/5. The paper was fairly easy to follow but could use another round of editing. Perhaps restructuring how the FIFO and FILO variations are presented could help, e.g. present just the simpler FIFO case first so that readers understand the overall structure, and then discuss what changes for FILO.

Significance = 2/5. Although I think the problem setting is interesting, the relatively low novelty (at least at a conceptual level) hinders overall significance.
limitations_and_societal_impact: yes

I thought the authors did a very good job pointing out potential societal impacts "hidden" in the generative models. Although the models are used for compression, they could be extracted and sampled, which could leak information from the training set (see Figure 3). This is a great point and warning on the part of the authors.
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: This work proposes an adaptive compression scheme that leverages a pre-trained deep generative model (DGM).  Specifically, the authors consider compressing a sequence of many (~thousands or more) samples and propose to periodically update the underlying DGM, so that the DGM gradually becomes a better fit for the dataset at hand.  The main contributions of this work are in its formulation as well as experimental results.
main_review: ### Strengths
I find the overall idea of online updating the underlying model interesting.  As authors mention, this could be useful for archival purposes where encoding/decoding speed is not crucial, but the compression ratio is critical. 

### Concerns
- **Novelty:** I do not find the proposed formulation to be a sufficient contribution.  Using an entropy model that is adaptive has a long history.  Context-adaptive entropy coders have long been studied [2], and even the online adaptation of the model was explored in [1].  [1] is particularly relevant to this work because it also studies the compression performance of a deep learning model when counting the communication cost of model parameters.  The discovery is that online adaptation of the model leads to a better compression than the two-part scheme that one obtains from a VAE with a prior over model parameters.  Given this, the idea of periodically updating the underlying entropy model during compression seems to be a rather minor extension.
   - I also find that OSOA is compatible with both FIFO and FILO entropy coders (e.g. AC vs. ANS) to be an implementation detail that is irrelevant to the overall paper.  This is because OSOA assumes the existence of a model-specific coder (denoted "inbuilt algorithm of the framework" in the Supplementary Material) and thus is essentially agnostic to the details of it.
  - I am confused by the name of the method as well.  Specifically, what is "one-shot" about the proposed method? The model updates happen periodically for the total of $T$ times over the course of encoding/decoding.  

- **Experiments:** While the experimental results are sensible, they do not seem particularly informative.  It seems that they were designed primarily to study the effects of various hyperparameters.  More specifically:
  - Figure 2 (left) does not provide much information, since the ReTrain model is trained from scratch, whereas OSOA benefits from the pre-trained checkpoint.   A similar observation could be made about Figure 2 (middle, right) -- the longer you run OSOA, the more the model is essentially trained on the compressed data.  Thus, it's expected that the gap between OSOA and FineTune would gradually decrease.
  - The effect of `updates/batch` presented in Sec 4.2 shows that updating the model parameters more leads to better bpd.  This result is completely expected, as DGMs are generally trained for many (10s ~ 100s) epochs over the dataset.  

- **Writing quality:** The overall writing quality of the paper could be improved.  Aside from confusing/unnatural sentences, the paper also contains some vague claims.  For example, Sec 4.3 discusses the mismatch between the goal of DGM training and lossless compression.  As an illustrative example, it mentions the cases where a likelihood-based model assigns high likelihood on out-of-distribution samples.   While this seemingly counterintuitive phenomenon is indeed real, I disagree that there is a mismatch in the objectives of DGM training and lossless compression.  A likelihood-based model (e.g. a normalizing flow) is trained to maximize its likelihood on the training dataset, which directly corresponds to its compression performance of the said dataset.  _This is irrespective of how the model performs on another dataset._   


#### Reference
[1] Blier, Léonard, and Yann Ollivier. "The description length of deep learning models." Proceedings of the 32nd International Conference on Neural Information Processing Systems. 2018.
[2] https://en.wikipedia.org/wiki/Context-adaptive_binary_arithmetic_coding
limitations_and_societal_impact: The authors thoroughly discuss potential societal impacts.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The paper introduces One-Shot Online Adaptation (OSOA) for lossless compression by generative models. This method allows a model to adapt to a test-time distribution that is different from the train-time distribution without having to transmit a re-trained model. The basic idea is that one can apply a deterministic learning procedure to the model for each batch in a sequence of batches being compressed. Since compression is done losslessly, the decoder can replicate the exact same training procedure, and thus have access to the same adapted model as was used for compression. The idea is validated in a thorough experimental study.
main_review: This paper is based on a really clever idea. Although there are some practical drawbacks (see below), I think this method can really improve compression results significantly. This is already confirmed by the experimental results in this paper, but can probably be pushed further.

The experiments are clean and simple and show a clear benefit of OSOA. Enough details are provided to enable reproducibility. 

The paper is fairly well written, although I think it can be made a bit easier to read still. Some details are hard to find, such as whether you count the cost of the model parameters as part of the bpd.

Although I think the basic idea of OSOA is new in the DGM compression literature, I’m quite sure the idea of adaptation / “online learning” is well known in the classical (non DL) compression literature. It would be good to refer to older works that use this idea.

Some downsides of OSOA, that would be good to discuss at more length in the paper
Getting deterministic training to work in practice, across different devices, will be very challenging
Not only encoding time, but also decoding time is greatly increased because it will require training.

Overall I think this is an innovative paper with a solid experimental validation, that is likely to spur further work in the DGM compression literature.

limitations_and_societal_impact: Some limitations could be better discussed (see above).
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper considers the task of online adaptation of pre-trained lossless compression models, while simultaneously using the updated model to compress the target dataset. The resulting framework, and new algorithm called OSOA, is based on the key insight that when losslessly compressing many batches of data, one can update the existing model on the data batches on the fly, so that the compression model better captures the target data statistics. Together with a FIFO codec (such as arithmetic coding) or FILO codec with a caching mechanism, the decoder can decode the data batches while replaying the model updates, so that the model update comes with no extra bitrate cost. Experiments demonstrate significant time and space savings of OSOA compared to the baselines of re-training or fine-tuning.

main_review: **Originality:**

Although the idea of adapting the model on the data being compressed is not entirely new (e.g., it's been used in traditional codecs like arithmetic coding), the paper successfully applies this idea to learned lossless compression based on deep generative models, which I believe is a novel contribution.



**Clarity:**

The writing can be improved, especially in the background section, where some of the text is sloppily written and might be misleading to a non-expert reader. Examples:
1. lines 77-79: "Another component in a DGM based lossless compression algorithm is the entropy coder, which converts the data symbols into code and the optimal codelength is the distribution" -- it'd be clearer to write "... into code *(bit-strings)* and the optimal *average* codelength is the diisttrubtion of the *ground truth data* distribution".
2. line 82: the statement "AC and ANS perform slightly slower than Huffman coding, they provide a code length closer to the optimal." is imprecise and possibly misleading.
3. The overall problem setup ("maximum likelihood training") can also benefit from more rigor, in order to establish the correct objective functions for the proposed adaptation process. Although not clearly specified, the "distributions" $p^*(x)$ and $p_\theta(x)$ in Eqs (1) and (2) are understood to be probability *density* functions (according to the context, and the subsequent discussion on discretization schemes), and therefore the MLE objectives (1) and (2) don't directly have compression interpretations. This can be fixed by either specifying that that data $x$ is assumed to be discrete, so that $p^*$ and $p_\theta$ are probability *mass* functions (so that (1) and (2) are compression costs), or take the dequantization approach (i.e., adding dequantization noise to the data) and modify (1) or (2) accordingly so that they correspond to upper bounds on the compression cost.


**Quality:**

The claims and evaluation methodology appear mostly sound. As noted above, the clarity of the paper can be improved.
On a related note, I have a clarifying question on the evaluation method: are the theoretical bpd values derived from the same training objectives as the base models (i.e., NELBO for VAE model and NLL for IDF++)?


**Significance:**

The paper tackles a relevant practical problem of deploying a trained compression model on out-of-distribution data. The proposed method broadly applies to generative models for lossless data compression, and should be of interest to most researchers and practitioners working in learned data compression. 



limitations_and_societal_impact: **Limitations**

1. As the authors noted, the fine-tuning baseline requires an extra model update transmission overhead compared to the proposed OSOA method; however with the naive strategy (storing the updates as 32-bit floats, without any entropy-cost-penalty on the updates), this overhead might be over-estimated. The model update overhead from fine-tuning can be significantly reduced with learned entropy coding, e.g., by adapting the technique of Rozendaal et al. (ICLR 2021) to overfit on the entire test batch in a lossless compression setting. A stronger fine-tuning baseline would make a more interesting comparison.
2. The requirement for the decoder to be able to carry out model training (and perform the exact same updates as the encoder) may limit the applicability of the method, e.g., to edge devices.
review_title: null

Meta-review: The paper proposes to use a deep generative model optimized over a large dataset as the entropy model for a lossless compression algorithm. The main idea is to divide the data to be compressed into separate batches and to adapt the pre-trained model on each batch before coding the next batch.
There are two reviewers opposing the acceptance of the paper and two reviewers who are for accepting it. The main drawbacks pointed out are:
- Potentially limited originality because “backward adaptation” is commonly used in image and video coding.
- Writing quality could be significantly improved.
- Some experiments seem to be less informative.
- Older (non-DL) literature is missing.

All reviewers appreciated the quality and clarity of the paper. Two reviewers especially valued the idea of adapting the model on data being compressed with deep generative models. The rebuttal was positively received by the reviewers. In my assessment, even though the originality of the paper is put in question, the paper is an interesting contribution to the field of data compression with deep generative modeling. Therefore, I tend to accept the paper.

Decision: Accept (Poster)