OSOA: One-Shot Online Adaptation of Deep Generative Models for Lossless Compression
Authors: Chen Zhang
Shifeng Zhang
Fabio Maria Carlucci
Zhenguo Li
Venue: NeurIPS 2021 Poster (2021)
Keywords: Deep Generative Models
Lossless Compression

Abstract: Explicit deep generative models (DGMs), e.g., VAEs and Normalizing Flows, have shown to offer an effective data modelling alternative for lossless compression. 
However, DGMs themselves normally require large storage space and thus contaminate the advantage brought by accurate data density estimation.
To eliminate the requirement of saving separate models for different target datasets, we propose a novel setting that starts from a pretrained deep generative model and compresses the data batches while adapting the model with a dynamical system for only one epoch.
We formalise this setting as that of One-Shot Online Adaptation (OSOA) of DGMs for lossless compression and propose a vanilla algorithm under this setting. 
Experimental results show that vanilla OSOA can save significant time versus training bespoke models and space versus using one model for all targets.
With the same adaptation step number or adaptation time, it is shown vanilla OSOA can exhibit better space efficiency, e.g., $47\%$ less space, than fine-tuning the pretrained model and saving the fine-tuned model.
Moreover, we showcase the potential of OSOA and motivate more sophisticated OSOA algorithms by showing further space or time efficiency with multiple updates per batch and early stopping.

OSOA: One-Shot Online Adaptation of Deep Generative Models for Lossless Compression
Chen Zhang
Shifeng Zhang
Fabio M. Carlucci'
Zhenguo Lit
Huawei Noah's Ark Lab
(chenzhang10, zhangshifeng4, 1i. (..zhhenuo)
Abstract
Explicit deep generative models (DGMs), e.g., VAEs and Normalizing Flows, have shown to offer an effective data modelling alternative for lossless compression. However, DGMs themselves normally require large storage space and thus contam- inate the advantage brought by accurate data density estimation. To eliminate the requirement of saving separate models for different target datasets, we propose a novel setting that starts from pretrained deep generative model and compresses the data batches while adapting the model with a dynamical system for only one epoch. We formalise this setting that of One-Shot Online Adaptation (OSOA) of DGMs for lossless compression and propose vanilla algorithm under this setting. Experimental results show that vanilla OSOA
significant time versus training bespoke models and space versus using one model for all targets. With the same adaptation step number or adaptation time, it is shown vanilla OSOA exhibit better space efficiency, e.g., 47% less space, than fine-tuning the pretrained model and saving the fine-tuned model. Moreover, of OSOA and motivate more sophisticated OSOA algorithms by showing further space time efficiency with multiple updates per batch and early stopping.
showcase the potential
Introduction
Lossless compression has always been an important part in the information and communications technology industry and has become more and more essential with the data explosion of the Big
Data era [10
39 40 8. Recently, large number of machine learning approaches, predominantly
deep generative models (DGMs), have been proposed for lossless compression [34 48
[9 I7
ST]. As indicated by Shannon's 's source coding theorem, the compression limit is determined by the entropy of the data's ground truth distribution [30]: any mismatch between an approximate distribution for coding and the unknown ground truth distribution will cause extra coding cost. is the powerful approximation ability of DGMs that enables more precise estimation of the ground truth distribution [23 24 29 and enables DGMs based compression algorithms outperform the conventional counter-parties in terms of the compression ratio.
However, in real production scenarios, both space and time efficiencies desirable. While more space efficiency is provided by higher compression ratio with DGMs based lossless compression algorithms, training of the probabilistic models time consuming. Training separate model for each different dataset to compress would scale the expensive time cost linearly. Moreover, to decode the dataset, one has to store the probabilistic model together with the codeword of the data, which requires additional space for local decoding and additional transmission cost for remote decoding. Apart from one model per dataset, another extreme on the spectrum using one probabilistic model
Work done during employment at Huawei Technologies R&D UK
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

for many different datasets. Since each dataset can follow very different distribution, using one model for all the datasets could lead to high inefficiency in terms of compression ratio.
To solve the above dilemma, we propose the setting of One-Shot Online Adaptation (OSOA) of deep generative models for lossless compression. A DGM based lossless compression algorithm under the OSOA setting (referred to as OSOA algorithm) includes one pretrained deep generative model (referred as base model) and one deterministic dynamical system. The base model should be able to capture essential structures of a class of datasets to serve as a good starting point of the adaptation process. The dynamical system the mechanism that can update the current distribution to new one based on the current batch at each step in the OSOA process. At each OSOA step, one first uses the current deep generative model to evaluate the probabilistic mass function values to compress the current data batch before using the same batch to update the model with the dynamical system, which gives the name of online adaptation. The online adaptation only conducted for one epoch and a distribution sequence will be unrolled during this process. Moreover, the dynamical system should be designed to optimise the objective functional associated with the deep generative model so that the sequence could provide better approximations we can start from a proper base model and benefit from improved compression ratio as the sequence being unrolled. As the sequence is fully determined by the base model and the dynamical system, this approach allows to not only eliminate the need of extensively training a new model on each new dataset, but also to bypass the associated model storage cost that would normally be required.
the unrolling procedure. Under this new setting,
Apart from the novel setting formulation, we showease with experiments on large datasets that a vanilla OSOA algorithm can significantly save time versus training bespoke models and save space versus using one model for all targets. Moreover, with the same adaptation step number or adaptation time, vanilla OSOA can exhibit better space efficiency, e.g.. 47% less space, than fine-tuning the pretrained model and saving the fine-tuned model. We also show that further trade-off between time and space cost is available with varies strategies, e.g., multiple updates per batch and early stopping, and motivate more sophisticated algorithms with preliminary explorations. Further, we use sample images from OSOA and baselines to justify adaptation based compression algorithms and to discuss societal considerations for DGMs based lossless compression.
The paper is organised as follows. In Sec. 2 we review background knowledge regarding deep generative models for lossless compression. In Sec. g] we formulate the setting of OSOA, discuss associated codec designing principles and propose vanilla OSOA algorithm. In Sec. we validate the setting by comparison with baselines, explore the strategies for further trade-off and discuss societal considerations. In Sec. S we discuss some related work. In Sec. 6 we summarise the paper, offer insights into our findings and point out promising future work directions.
2 Preliminary
Entropy Coding The core component underlying any lossless compression algorithm is the entropy coder, which converts between the data symbols and codewords. Popular entropy coders include Huffman coding (2I), arithmetic coding (AC) [54] and asymmetric numeral systems (ANS) (9. Huffman coding mainly involves binary trees operations, which is usually more time efficient than AC and ANS but can admit suboptimal codelength for probabilities not being power of 1/2 [30. As result, popular codees adopted by DGM based algorithms are normally based on AC or ANS, e.g., R4 19 35). The main difference between AC and ANS is that the former encodes and decodes in first-in-frrtt-uut (FIFO) style while the latter performs in a first-in-last-out (FILO) style [48. All entropy coders require the knowledge of the data symbol alphabet and the associated distribution, in order to conduct compression and decompression. It is worth noting that the distribution used for entropy coding should be discrete and the average codelength is expected to be the entropy of the distribution used for coding. Recall that for a discrete distribution with the probabilistic mass function p(x). the (Shannon) entropy is defined as Ex-p!- log p(z)), Moreover, the optimal average codelength, given by the entropy of the ground truth distribution, is achieved only if the ground truth distribution is used for coding per Shannon's 's source coding theorem 30). Specifically, compressing data from distribution p(z) with distribution q(x) will lead to the expected extra codelength (p(x))))l((a))
Coding with Explicit Deep Generative Models Since the entropy coders require probability values, implicit DGMs, e.g., generative adversarial networks (GANs) []] cannot be readily used for lossless

---

compression. For explicit DGMs, the learning principle is either maximum likelihood estimation (MLE) 41 24 I
8 arg min Ex (x)) log (x)) #E8
or maximising the evidence lower hound (ELBO) of the logarithm evidence log po
49
0. = arg mingme.eee.eeooooooo Bx) 0( x;)]
where [(0, 02 E (=lx)] log (=(=)=) + log (e Note that is discrete random variable, so p" (x) refers to the probabilistic mass function of the ground truth data distribution.
When learning with MLE, one can either directly stipulate discrete model stipulate a continuous model with the dequantization technique [50] 45). If one stipulates a discrete model, where pe (z) denotes the probabilistic mass function of the model, the objective function Eq. delegates the expected codelength when using Po (z) for entropy coding. If one stipulates a continuous model, one normally dequantizes the discrete data x with continuous noise u uniformly distributed on the unit hypercube, and gets the dequantized variable = + with distribution p" (v). After fitting the probabilistic density function po (y) of the model to the the probability density p" (y) of the dequantized distribution, one needs to discretise po(y) and use the discretised distribution for entropy coding. In this case, the MLE objective Eyrgp" log (1)] delegates an upper bound of the expected codelength 45] For how to design sophisticated dequantization schemes or how to design discrete deep generative models, we refer the readers to [T6 19 ST 17 55).
When learning with ELBO, one usually stipulates discrete models for r. i.c., (e(x)2) is probabilistic mass function, and continuous models for i.c., (=(2[x) and (e(z) are probabilistic density functions. Furthermore, one usually does not have direct access to the close form of po(x) but the generative components (x|2) and po(=). J. To use (a)22) and po (z) for efficient coding, technique called bits- back [53 15 is employed, which additionally involves the approximate posterior distribution gs (z|xx) learned together with the generative components 448, 49 26). these cases, the discretisation
precision of the latent variable will not effect the average codelength, delegated by the objective in Eq with consistent discretisation adopted for the latent distributions [88 worth noting that, since bits-back works more compatibly with ANS, bits-back ANS 47 is usually the first choice for models learned with the ELBO functional.
3 One-shot online adaptation
In this section, we formulate the setting into three stages, i.e., 1) Pretraining, 2) OSOA Encoding and 3) OSOA Decoding, and summarise the OSOA Encoding / Decoding stages Alg. I To unify the narrative of FIFO style and FILO style entropy coders, we aggregate the operations in Stage 2&3 into two modules, namely the dynamical system module D and the codec module C. The deterministic dynamical system module D contains optimiser. which can be gradient based optimiser learning based meta optimiser, and associated parameters, to update a model po.., (x) to po, (x) with data batch B, The codec module C contains entropy coder, codeword variable and methods to modify the codeword with the entropy coder, cf. following discussions and Alg. 2
Algorithm 1 One Shot Online Adaptation: Encoding and Decoding
OSOA Encoding
OSOA Decoding
1: Inbuilt attributes: pe, (z)), D
1: Inbuilt attributes: Poo (z), D,
2: Input: data (2:) }.m
2: Input: code os
3: Form data batches [Be [B, T from data W
Initialise with cy
for = to T
4: for t = 1 to T do
5: C. e.eooode_co eencode_or_ccchaeeeeeeeeeee__ cache (ps, 1 (z), Bi);
5: Bi + C. wec..eeccdeeeoooooooooooooo (pe, (x));
6: Pa, (1:) D(p (I), B.);
6: pa, (z) D(pe, (z), B:):
7: end for
end for
Output: data { from ( (B.
Output: ej from
Stage I: Pretraining base model pao (x) obtained by solving the problem defined Eq. 1o
Eq. on a pretraining dataset.
3

---

Stage 2: OSOA Encoding A sequence of distributions (2), will be unrolled through the adaptation procedure by the deterministic dynamical system with batches {B,) Specifically,
at each step 1, one 1) inputs the model pa,-1 (a:) and the data batch B, to the codec module and 2) performs the dynamical system D on po,-1 (ar) with Bd and obtains the updated model pe, (ar). In 1), the method C. encode_ _arch determines whether to directly encode the current batch (FIFO style) or save the needed information, i.c., the variable values and associated probabilistic mass function (pmf) values, for asynchronous encoding (FILO style), cf. Alg. 2 At the end of OSOA Encoding, the final state of the codeword variable ey will be output from the codec module.
Stage 3: OSOA Decoding One uses the codeword ey from the OSOA Encoding stage to initialise the codeword variable C and starts the iterative decoding process as follows. At each step t. one 1) uses the method C. decode to decode B, from the codeword variable with pa,_, (z) and 2) updates the model with the decoded batch B, by the dynamical system D. As a result, the same sequence of distributions {po, (I:) will be unrolled and all the data batches (B, 1B will also be decoded.
densmics
P1
dynomies
dynammcs
Pa
dynsmics
P+
dwnamics
Gg
c2
G
ct
batch 1
batch 2
banch
batch
batch 5
batch 5
Figure 1: An illustration of OSOA Encoding with FILO style entropy coders, where m 3 and T = 6 (bb-ANS as an example). C.push denotes the encoding operation of the ANS codec. We refer readers to Appendix[A]ie complete demos of FIFO style and FILO style entropy coders.
Methods in the codec module To recover the exact distribution sequence {pe, (x) in the decod- ing stage, one has to decode the data batches in the order of [Bi, B2, ..., Br For DGMs based algorithms with an FIFO style coder, e.g., AC, one can consecutively encode the batch sequence (BrY= in the original order and recover the correct order in the decoding stage. However, for FILO style coders, e.g., ANS, one has to temporarily save associated pmf values for encoding purpose in cache and encode them with the entropy coder in the reverse order. To reduce the size of cache memory, one can collect m consecutive batches into one chunk and reversely compress the batches within the chunk, cf. Fig. [ In this way, one effectively compresses different chunks into different code files. We refer readers to Appendix A for complete demos of OSOA with FIFO and FILO style coders. To distinguish the difference between the implementations of the encode or cache method in Alg. for coders of these two styles, we summarise the processes in Alg. 2 Note that coder encode in Alg. 2 and C. decode in Alg. [ are respectively encoding and decoding functions already implemented with DGMs for lossless compression 34 48 49 26] Due to this flexibility,
one can see that OSOA is generally applicable to DGMs based lossless compression algorithms.
Algorithm 2 The encode or__cache method in OSOA Encoding
FIFO coders
cache. appbeddpppddd (z), Be)); 4: if len(cache) = m or last_ then
1:
Inbuilt attributes: coder
2: Input: po,-, (x), B,
5: for p(x), B in rcach) do
3: coder. buder.encode eedereencodepp.. (x), Be);
6: coder enccdee(cce(p()) B);
FILO coders
7: end for
cache. empty
1: Inbuilt attributes: coder, cache,
9: end if
Input: pe._, (x), B,
Example: Vanilla OSOA Following formulations of the proposed setting, we present the most straightforward strategy to conduct OSOA, referred to as vanilla OSOA. Specifically, the base model pa, (x) pretrained on the same data modality, e.g., HiLLoC 49 pretrained on CIFARIO for image compression; and the deterministic dynamical system D is a gradient based optimiser, e.g., AdaMax (22). Stage 1. Find or train base model pa, (x) for certain data modality. Stage Perform OSOA with base model from the last stage. The dataset to compress S should be first split to T

---

batches, i.e., S ( For 1 StS T, we first use (z) to compute pmf values to encode the t-th batch. Then we use the t-th batch with the specific optimiser and certain learning rate to update and get the new model po, (r). Stage 3. Perform OSOA with base model from Stage 1. The data splitting strategy is the same as Stage 2. For 1 S t S T, we first use po, (x) to decode the I-th batch from the code. Then we use the decoded batch with the same 'D (e.g. optimiser, learning rate, etc.) as Stage 2 to update and get the new model pe, (x). Note the entropy coding part is omitted for narrative simplicity, and we refer readers to Appendix A for more details.
4 Experiments with vanilla OSOA
4.1 Vanilla OSOA versus baselines
Datasets The datasets for base model pretraining are the renowned natural image datasets CI- FARIO [28] and ImageNet32 77], including images of size 32 x 32. We obtain three target datasets randomly sampled from the large image dataset Yahoo Flickr Creative Commons 100 Million (YFCC100m) [46] to test the compression performance. We name the three subsets from YFCC100m by SET32/64/128, where SET32 means the dataset of image height and width both being 32. To remove potential artifacts introduced by previous image compression, cropping the central 256 x 256 part in 2 RGB images with size larger than 256 x 256 and down- sample the obtained dataset into our targets, as conducted in (34). We use Pillow to downsample the SET256 into SETI28, SET64 and SET32 with the high quality filter Image. ANTIALIAS. The 2 RGB images are selected only with their shapes and no other discretionary criteria.
first obtain SET256 by
Experiments configurations Since an OSOA algorithm can be regarded as general strategy to make static deep generative model dynamic, it can be used for any DGMs based lossless compression frameworks. We adopt two representative DGMs based compression frameworks, HiLLoC 44 for hierarchical VAEs and IDF++ [5T] for normalizing flows, to validate the OSOA setting. Specifically, for HilLoC, we use the ResNet VAE (RVAF) model, which is proposed in 25 and adopted for compression in 49] with 24 layers and bi-directional connections for inference (a.k.a. top-down inference). Moreover, we showcase for a proof-of-concept purpose the IAF RVAE [25], with the same configuration the RVAE model except for additional IAF layers in the inference model, making the approximate posterior more expressive. For IDF++, we use the same architecture proposed in (5T), with 24 stacked flow layer blocks, where each block contains a permutation layer and a coupling layer. For each coupling layer in the flow model, a 12 12-layer Densenet (20) with 512 feature maps is used. For narrative simplicity, we use HiLLoC and IDF++ to refer to both the frameworks and the associated models. We use an Nvidia V100 32GB GPU for HiLLoC (and IAF RVAE) and an Nvidia V100 16 GB GPU for IDF++. Capped by the GPU memory limit, the batch size should be reduced as the image size grows. We quadruple the batch size as the image size decreases, i.e., batch size 256/64/16 in HiLLoC and batch size 48/12/3 in IDF++, for SET32/64/128 respectively.
Table 1: Theoretical bits per dimension (bpd) values of HiLLoC, IAF RVAE and IDF++ models training from scratch (ReTrain) on the three target datasets SET32/64/128.
HiLLoC
IAF RVAE
IDF+
SET32
SET64
SET128
SET32
SET64
SET128
SET32
SET64
SET128
2.668
2.504
2.521
2.608
2.292
2.392
2.361
2.443
2,422
Baselines We adopt three baselines, referred to as ReTrain, PreTrain and FineTune. For ReTrain, we train a separate model for each target dataset from scratch and use the final model to compress the target datasets. For PreTrain, we directly use the pretrained models to compress the target datasets. For FineTTune, we fine tune the pretrained model on the target datasets and use the final model to compress the target datasets. Depending on how to set the number of fine-tuning epoches, we have three versions of FineTTune. For FineTTne v1, we fine tune the pretrained model for 2 epochs, as the whole OSOA Encoding & Decoding procedures involve epochs of adaptations in total. For FineTTune v2, we fine tune the pretrained model for 4 epochs for Hil (and IAF RVAE) and 3 epochs for IDF++ to make the model updating time comparable with OSOA. This is because the dynamical system module in vanilla OSOA needs strict determinism J and it could cause extra time
5

---

Table 2: Theoretical bpd values between vanilla OSOA and baselines (PreTrain, Fine vl, v2 and
v3). The bpd values of baselines less than those of vanilla OSOA are shown in green, e.g., 0.132 3.505 - 3.373. The effective bpd values by saving the models with Fine'Tune baselines, defined as 1/
#trainable Sttraiiable_parrmeterrr parameters x bits/ bits/parametes
sataastttttttllleeeee are shown in red. HiLLoC CIFARIO denotes the CIFARIO pretrained HiLLoC model.
SET
PreTrain
OSOA
Fine vl
FineTTune v2
Tune v3
Model
32
3.830
3,505
3.373 (0.132)
3,322 (0.183)
3.215 (0.290)
3.258
HiLLoC
64
3.561
3.090
2.954 (0.136)
2.907 (0.183)
2.800 (0.290)
0.815
CIFAR10
128
3.268
2.682
2.564 (0.118)
2.518 (0.164)
2.412 (0.270)
0.204
32
3.739
3.537
3.398
(0.139)
3.329 (0.208)
3.196 (0.341)
3.258
HiLLoC
64
3.430
3.109
2.950
(0.159)
2.893 (0.216)
2.769 (0.340)
0.815
ImgNet32
128
3.104
2.682
2.534 (0.148)
2.482 (0.200)
2.362 (0.320)
0.204
IAF
32
3.930
3.378
3.245 (0.133)
3.185 (0.193)
3.059 (0.319)
3.963
RVAE
64
4.078
3.028
2.816
(0.212)
2.751 (0.277)
2.640 (0.388)
0.991
CIFARIO
128
4.149
2.596
2.403 (0.193)
2.354 (0.242)
2.250 (0.346)
0.248
IAF
32
3.551
3,351
3.208
(0.143)
3.146 (0.205)
3.012 (0.339)
3.963
RVAE
64
3.325
2.932
2.769
(0.163)
2.707 (0.225)
2.582 (0.350)
0.991
ImgNet32
128
3.037
2.502
2.354 (0.148)
2,300 (0.202)
2.183 (0.319)
0.248
32
3.612
3.225
3.089
(0.136)
3.045 (0.180)
2.835 (0.390)
4.517
IDF++
64
3,471
2,873
2.725
(0.148)
2.687 (0.186)
2.481 (0.392)
1.166
CIFARIO
128
3,441
2.554
2.374 (0.180)
2.335 (0.219)
0.292
32
3.662
3.338
3.160 (0.178)
3.119 (0.219)
2.921 (0.417)
4.517
IDF++
64
3.439
2.949
2.768 (0.181)
2.729 (0.220)
2.528 (0.421)
1.166
ImgNet32
128
3,401
2.623
2.448 (0.175)
2.404 (0.219)
0.292
cost in current deep learning frameworks. The time ratio we measured with/without the determinism
1.98 (HiLLoC) in TensorFlow 1. (4] with tensorflow www-deeeemmiismmmmmm 3. 0 and 1.34 (IDF++) in Pytorch 1.6 (2). For FineTTne v3, we fine tune the pretrained model for 20 epochs as an indicator of overfitting the pretrained model on target datasets. To take the additional model storage in Fine Fine baselines into consideration, we convert the model (in float32) storage size into effective bpd values and show them in the Model column in Table Note that the bpd values shown under OSOA and baselines are of the codewords only, and the associated model bpd in the Model column need to be added to ReTrain and FineTune baselines for comparison of total storage cost. As bpd is the average number of bits needed to compress each dimension of the data, lower value indicates a higher compression ratio. The time costs of OSOA and basclines are caused by model training. network inference (pmf evaluation) and entropy coding. We predominately use the model training time for comparison, as it dominates the time cost and the model and the entropy coder are controlled factors for comparisons.
Recent work 36 6 37 show that DGMs can assign high density values on data points not in the training datasets. And pretrained models can provide reasonable compression performance on unseen datasets 49 (55) While PreTrain Table 2 further confirms this point, the extra cost comparing to best possible ones can be significant, due to the distribution discrepancy between the training data and the target data. Nevertheless, PreTrain has the best time efficiency, since no extra training is needed.
Comparing to FineTune, OSOA does not require additional model storage for decompression. Fixing the batch order, the unrolled models in OSOA are the models in the first fine-tuning epoch, which tend to fit the data worse than the final one in the whole fine-tuning process (not necessarily true, cf. negative difference values in Fig Right). Nevertheless, by comparing the decreased code space shown in green and the increased model space shown in red for Fine'Tune v1 or Fine'Tune v2 in Table one can see that with the same optimisation budget or time budget, OSOA exhibits better total space efficiency than FineTTnne For instance, with the CIFAR10 pretrained HiLLoC on SET32, OSOA takes 46.7 46.73% less space than Fine v2, with the same model training cost. To better understand the comparison between OSOA and FineTune v2 on SET 128, we take the CIFAR10

---

pretrained HiLLoC and fix the order of images. If we only compress the first 2 2 and 2 images in SET128, the FineTTune v2 admits bpd. in the code bpd + model bpd format, 2.564 0.408, 2.611 + 0.816 and 2.658 1.632. However, OSOA admits bpd, in the code bpd format since no model storage required, 2.734, 2.788 and 2.842, which are 0.238, 0.639 and 1.448 less than Fine v2 respectively. Therefore, OSOA remains clear net advantage than FineTTune with the same time budget up to reasonable large sample size even on large size images. From the comparison between OSOA and FineTTuee v3, one can see that the space advantage is still valid even if we conduct the Fine for much longer time for SET32/64. Tune v3 performs better on space efficiency on SET128, but it takes more than 4 times much time OSOA. Recent work on data lossy compression [52 introduces a model update coding term to the objective function and conducts lossless compression on the model update. However, this introduces extra layer of complexity and time cost to determine suitable prior distributions for network parameters and to balance the data compression and model compression, Since OSOA does not require extra model saving, it exhibits huge advantage over the baselines on large-scale models or data of limited size. Note that OSOA achieves the optimal space & time cost balance with conducting model updates during data decoding. Therefore, it will be more suitable to scenarios of data backup or data cold storage than scenarios with real time data usage, c.g., video streaming.
At each OSOA step, the potential improvement of the model from the current batch can only benefit the compression of following batches. Moreover, the batch gradient can have large variance and the stochastic gradient methods, e.g. SGD, Adam, etc., are not strictly descent algorithms. To investigate the online compression performance along the OSOA path, we showcase the results at the batch level in OSOA Encoding in Fig. _ Middle and Right, with the CIFAR 10 pretrained HiI_LoC on SET32 and SET128. To make the bpd values comparable, and PreTTrain and showcase the differences between the bpd values of compressing each batch with OSOA and the baselines. Here we abuse the notation and use OSOA/Fine Tune to denote the vector of bpd values of each batch in OSOA/FineTune with above fixed batch order. Then the 100th entry in the difference vector (OSOA- FineTuuee v1) is the extra cost of compressing the 100th batch with OSOA at the 100th OSOA Encoding step instead of Fine' Tune v1 (with the tneettuned model). Note that a negative difference value indicates that OSOA performs better than the corresponding baseline for that batch. From Fig. Middle and Right, we can see that the advantage of compression with OSOA instead of PreTrain enlarges and the disadvantage (w.r.t. code space) of compression with OSOA instead of Fine'Tun Tune decreases, which validates the benefits brought by adaptation with previous batches to following batches in OSOA.
the same batch order for OSOA, Fine'Tune
ReTrain batch bpd
0.50
OSOA FincTune v1
1.0
FineTare y1 OSOA
OSOA final average
OSOA FineTiaee
OSOA Fine v3
10-
OSOA barch bpd
0.25
OSOA Pretrain
OSOA- Pretrain
hpd
0.0-
11 del
-0.25
.0.5
00
10F
10a
10'
10²
0
200
400
-1.0
0
2500
5000
7500
time (s)
batches
batches
Figure 2: Left: Theoretical bpd values of each batch during training HiLLoC from scratch on SET32 (ReTrain HiLLoC) versus the batch bpd of OSOA, showing the significant time cost of training from scratch. OSOA final average is the bpd value after compressing all the batches with OSOA. Middle and Right: the differences between the theoretical bpd values of OSOA and the theoretical bpd values of the baselines of each batch in SET32 (Middle) and SET128 (Right) with the CIFAR 10 pretrained HiLLoC Negative values indicate the advantages of coding with OSOA instead of the corresponding baseline. The disadvantage of OSOA (versus Tune) tends to decrease and the advantage of OSOA (versus PreTrain) tends to increase as the online adaptation being conducted.
Note that the theoretical bpd values reported in this paper are evaluated based on the discretised distributions of models for coding. Moreover, for Hil.LoC, although the free-bits technique is used for the ResNet VAE model training, theoretical bpd evaluation does not involve free-bits. We showcase the real bpd values of HiLLoC and IDF++ on SET32 in Appendix B
7

---

4.2 Vanilla OSOA variants to prioritise space or time efficiency
OSOA with multiple updates per batch Vanilla OSOA conducts one model update step per data batch with gradient based optimisers. However, it might not be sufficient for OSOA to exploit the adaptation potential from the base model, which is especially true for scenarios with small number of data batches. For instance, by comparing Fig. Middle and Right, we can see that the performance improvement curves exhibit slower overall convergences on SET32 than SET128. To investigate the potential of OSOA in such scenarios, we follow the setting in Sec. 4. and conduct vanilla OSOA with multiple updates per batch. Note that each data batch is only used one corresponding OSOA step and the multiple updates are conducted in that OSOA step, which will not change the one-shot nature and is different from multiple-epoch adaptation. In this section, we use SET32 with CIFARIO pretrained HiLLoC and IDF++ and fix the batch size at 256 and 48 respectively. From Table 3 we can see that conducting multiple updates per batch can improve the performance for both oo and IDF++, and it can even further improve the bpd by around 0.4 for HiLLoC It worth noting that in contrast to that overfitting does not happend for HiLLoC at 500 steps per batch, overfitting happens at 100 steps per batch for IDF++. Moreover, conducting multiple updates per batch scales the time cost linearly and it provides a modification to trade off time efficiency for space efficiency.
Table 3:
The theoretical bpd of HiLLoC and IDF++ with OSOA of multiple optimisation updates per batch on test dataset SET32.
updates/batch
3
5
10
100
500
HiLLoC (CIFARIO)
3.505
3,420
3.382
3.357
3.332
3.184
3.109
IDF++ (CIFARIO)
3.225
3.137
3.096
3.080
3.046
3.105
OSOA with early stopping In vanilla OSOA, the number of adaptation steps is determined by the data size and the batch size. For very large datasets, additional bpd improvements from the latter OSOA steps may not be significant, cf. Fig Right. Due to the strict reproducibility of OSOA, if one sets a stopping criterion and uses the model at the stopping time for remaining data batches, the stopping criterion will be triggered at exactly the same step in OSOA Encoding and OSOA Decoding. Moreover, the time for model update, i.e., back propagation in the vanilla OSOA, will be saved for remaining batches. For instance, in the example of CIFAR10 pretrained HiLLoC for SET128, there are 8192 batches in total. If one stops the model adaptation at the 500th, 1000th, 2500th or 5000th batch, the final OSOA bpd will be 2.820, 2.774, 2.717 2.690 respectively, where one can accelerate the model adaptation efficiency by 8 times with the bpd cost less than 0.1.
4.3 Discussion DGMs for data lossless compression
Probabilistic modelling with DGMs for data generation encourages precise modelling of the target dataset for high fidelity generation. Different from generation purpose modelling, lossless com- pression purpose modelling only calls for high density values. The phenomena, DGMs assigning high density values for pretrained models for OOD datasets lossless compression 44 55,, indicate that data generation
(OOD) data (36]
6
37
and plausible performance of
purpose modelling and data compression purpose modelling are not strictly equivalent. And we refer the readers to [45 for an intuitive discussion on sample quality and log-likelihood values. It is discussed in (36) that DGMs weigh low-level statisties more than high-level semantics, and we show in above sections and Fig. such inductive bias can be leveraged for lossless compression purpose. Derived from PreTrain, OSOA and FineTune admit samples with consistent semantics as PreTrain, fixing the random seed, cf. Fig. (a), (b), (d) and (c). At the local feature level, c.g., sharpness and contrast, samples from the final models of OSOA and FineTune are more similar to samples from ReTrain, explaining improvements of OSOA and Fine from Pre Train. While such local feature transfer largely originates from the small learning rate used in OSOA and Fine Tune, learning rate of too small too large values will impede the performance, cf. Fig. (f). Note that (b), (d) and (e) in Fig. 3 are hardly distinguishable, but they do differ in numerical values.
Another motivation of presenting samples in Fig. 3 is to discuss societal considerations to be addressed for future real applications of DGMs based lossless compression algorithms. Since trained DGMs model the distribution of the training set, information of the training data may be leaked by samples
8

---

(a) PreTTrain
(b) Fine v3
(c) ReTraii
3.55
3,50
3.45
3.40
0.000
0.005
0.010
learning rate
(d) OSOA 1 updatc/batch
(c) OSOA 100 updates/batch
(1) OSOA bpd Ir
Figure 3: 36 images sampled from (a) PreTTrain: CIFARIO pretrained HiLLoC, (b) FineTTune v3: fine-tuning CIFARIO pretrained HiLLoC for 20 epochs on SET32, (c) ReTrain: HiLLoC trained on SET32 from scratch, (d) and (e) OSOA 1 and 100 updates/batch: the final checkpoint of vanilla OSOA with and 100 update steps per batch from CIFARIO pretrained HiLLoC, respectively. (f) The theoretical bpd values of vanilla OSOA with different learning rate values, with HiLLoC (CIFAR10),
from the trained models, e.g., the third row and fifth column in Fig. (c) showing two people. Therefore, the specially trained models should be protected from privacy violation. From this perspective, pretrained models with as few adaptation steps as possible tend to have more privacy protection for service users. Nevertheless, information of the pretraining dataset can be retained in adapted models and influence the compression performance of target datasets. As result, service providers should avoid using sensitive information in the pretraining dataset and avoid discrimination (different compression performances for data of different groups) caused by the pretraining dataset. As shown in this work, training low resolution and non-sensitive images can offer good performance on images of different resolutions and semantics. Accordingly, promising to build societally friendly and effective DGMs base lossless compression algorithms with pretraining + adaptation style frameworks, e.g., OSOA, and careful incorporation pretraining data.
Related work
OSOA de facto defines paradigm to compress the distribution (model) sequence. The high level principle of can trace back to a simple mathematical fact: a sequence can uniquely determined by an initial point and a deterministic transition dynamics. In this section, provide non-exhaustive list how this high level principle can be instantiated in compression related literature.
showcased the potential of neural networks as static context models for text compression and discussed the possibility of adaptive modelling with neural networks. [31] and DeepZip [4 [2] then instantiated the above principle for neural network based adaptive modelling with AC. This line of work focuses on the sequential modelling of entries in one data point and thus intra-data adaptive modelling: we focus on DGMs of the data distribution and thus is inter-data adaptive modelling. Moreover, our work additionally bridges the initial probabilistic model with the adaptation process which enables the adaptation of pretrained model and the benefit from pretrained models of datasets
43

---

sharing common structures. Another line of work is sequential data lossy compression like videos [52] 13.. They introduce encoder-decoder networks for compression, where the encoder network is adapted to sequential data during compression and the decoder network is used for decompression. However, the setting quite different from OSOA. First, they are the lossy compression method and could only use VAEs for compression, while ours mainly deals with lossless ones and works on any explicit generative model. Second, they mainly deal with sequential data, while ours can compress any data batches, including the sequential ones.
The model storage cost for deep learning based data lossless compression is also considered in [5]. The work [5] formulates the problem in a supervised learning paradigm, where both the sender and receiver need the base model and an auxiliary dataset for the label transmission, whereas our work formulates in the unsupervised learning paradigm and only the base model is needed. Moreover, in order for the auxiliary dataset needed in (5] to effectively reduce the bitrate of the label (data to transfer), the label data needs high mutual information with the auxiliary dataset, which can form a stronger constraint.
The same principle also applies to pseudo-random generators, where unique sample can be identified by the index of the sample generated from a shared pseudo-random source. 14] leveraged this fact and proposed an autoregressive style algorithm to compress the network parameter partition by partition with the sample indices of each partition and a predefined parameter prior. In the setting of lossy compression of Bayesian neural networks, [14] chooses one sample from the learned approximate posterior distribution to compress and thus deviates from the setting of data lossless compression where the data is given instead of chosen.
Prior the developments in the deep learning literature, this high level principle has also been investigated for data compression. Adaptive dictionary methods, c.g., LZ77 [56], dynamically maintain a dictionary of substrings to gradually recover the optimal dictionary containing the repeated patterns in the sequence. Apart from dictionaries, the probability simplex can also be dynamically maintained gradually converge the ground truth probabilities or to capture the distribution shifts, e.g., context-adaptive binary arithmetic coding (CABAC) [38 33). Furthermore, for context mixture modelling methods, the mixture weights can be adapted during compression favour the context models that make more accurate predictions. e.g., PAQ [32. Due to the functional form of deep generative models, conducting OSOA of DGMs for lossless compression uniquely leverages the inductive bias of DGMs and could admit more flexible compression purpose modelling.
6 Conclusion and future work
In this work, we proposed the novel setting of One-Shot Online Adaptation (OSOA) of deep generative models for lossless compression and discussed codec designing principles for codecs of different styles. We showcased with a vanilla OSOA algorithm that OSOA can reduce the extensive model training time and model storage space for new datasets and achieve optimal trade-off between time and space cost versus alternative solutions. Our experimental exploration indicated that more sophisticated OSOA algorithms are promising and desirable. Finally, we discussed societal considerations for deep generative models based lossless compression algorithms.
The future work can be pursued in three folds. First, since the quality of the base model is very important for reducing the OSOA cost, it is highly desirable to study how to use deep generative models to capture the most of the common information shared among a general class of different datasets. Sccond, as shown in Sec. 4.2. there is still room to improve the space and time efficiency within one epoch of adaptation, it is thus of interest to study how more advanced dynamical systems, e.g., meta-learning methods or reinforcement learning methods, can further exploit the full potential of OSOA. Third, following the discussion in Sec. 4.3 it is interesting to investigate local feature transfer algorithms with pretrained models for fast lossless compression on unseen datasets.
Acknowledgments and Disclosure of Funding
The authors thank the anonymous reviewers for their review and suggestions, which improved the quality of this manuscript. The authors thank Ning Kang and Mingtian Zhang for fruitful discussions.
10

---

References
[1]
Determinism deep learning.
s9911
[2] Pytorch reproducibility, reppoducbbitty.ttpps//ppppooooo
[3] Tensorflow determinism. http:////ggggh.oooo//////o//ooaa
[4] Martín Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, Manjunath Kudlur, Josh Levenberg. Rajat Monga, Sherry Moore, Derek G. Murray, Benoit Steiner, Paul Tucker, Vijay Vasudevan, Pete Warden, Martin Wicke, Yuan Yu, and Xiaoqiang Zheng. Tensorflow: A system for large- scale machine learning. In Proceedings of the 12th USENIX Conference on Operating Systems Design and Implementation, OSDI' 16, page 265-283 283, USA, 2016. USENIX Association.
[5] Léonard Blier and Yann Ollivier. The description length of deep learning models. In Advances Neural Information Processing Systems, volume 31, 2018.
[6] Hyunsun Choi, Eric Jang, and Alexander Alemi Waic, but why? generative ensembles for robust anomaly detection. arXiv preprint 1rXiv:8810.01300 2018.
[7] Patryk Chrabaszez, Ilya Loshchilov, and Frank Hutter. A downsampled variant of imagenet as an alternative to the cifar datasets. arXiv preprint arXiv: 2017.
[8] Yann Collet and Chip Turner Smaller and faster data compression with zstandard. Facebook Code [online], 2016.
[9] Jarek Duda. Asymmetric numeral systems: entropy coding combining speed of huffman coding with compression rate of arithmetic coding. arXiv preprint arXiv: 1311.2/311,254: 2013.
[10] Philip Gage. A new algorithm for data compression. C Users Journal, 12(2):23-38, 1994.
[11] Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. Advances Neural Information Processing Systems, 27, 2014.
[12] Mohit Goyal, Kedar Tatwawadi, Shubham Chandak, and Idoia Ochoa. Deepzip: Lossless data compression using recurrent neural networks. In Data Compression Conference, DCC 2019, Snowbird, UT, USA, March 26-29, 2019, page 575. IEEE, 2019.
[13] Amirhossein Habibian, Ties van Rozendaal, Jakub M Tomezak, and Taco S Cohen. Video compression with rate-distortion autoencoders. In Proceedings of the IEEE/CVF International Conference Computer Vision, pages 7033-7042, 2019.
[14] Marton Havasi, Robert Peharz, and José Miguel Hernández-Lobate Minimal random code learning: Getting bits back from compressed model parameters. International Conference on Learning Representations, 2019.
[15] GE Hinton and Drew van Camp. Keeping neural networks simple by minimising the description length of weights. 1993. In Proceedings of COLT1-9, pages 5-13.
[16] Jonathan Ho, Xi Chen, Aravind Srinivas, Yan Duan, and Pieter Abbeel. Flow++: Improving flow-based generative models with variational dequantization and architecture design. In International Conference on Machine Learning, pages 2722-2730. PMLR, 2019.
[17] Jonathan Ho, Evan Lohn, and Pieter Abbeel. Compression with flows via local bits-back coding. In Advances in Neural Information Processing Systems, pages 3879-3888, 2019.
[18] Emiel Hoogeboom, Taco Cohen, and Jakub Mikolaj Tomezak. Learning discrete distributions by dequantization. In Third Symposium on Advances in Approximate Bayesian Inference, 2021.
[19] Emiel Hoogeboom, Jorn Peters, Rianne van den Berg, and Max Welling. Integer discrete flows and lossless compression. Advances in Neural Information Processing Systems, pages 12134-12144, 2019.

---

[20] Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinberger. Densely connected convolutional networks. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 4700-4708, 2017.
[21] David A Huffman. method for the construction of minimum-redunnaaee codes. Proceedings of the IRF, 4009):1098-1101 1952.
[22] Diederik P. Kingma and Jimmy Ba. Adam: method for stochastic optimization. 3rd International Conference Learning Representations, ICLR 2015, 2015.
[23] Diederik P. Kingma and Max Welling. Auto-encoding variational bayes. 2nd International Conference Learning Representations, ICLR 2014.
[24] Durk Kingma and Prafulla Dhariwal. Glow: Generative flow with invertible Ixl convolutions. In Advances in Neural Information Processing Systems, pages 10215-10224, 2018.
[25] Durk P Kingma, Tim Salimans, Rafal Jozefowicz, Xi Chen, llya Sutskever, and Max Welling, Improved variational inference with inverse autoregressive flow. In D. Lee, M. Sugiyama, U. Luxburg, Guyon, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 29, pages 4743-4751. Curran Associates, Inc., 2016.
[26] Friso Kingma, Pieter Abbeel, and Jonathan Ho. Bit-swap: Recursive bits-back coding for lossless compression with hierarchical latent variables. In International Conference on Machine Learning, pages 3408-3417. PMLR, 2019.
[27] Donald Knuth. Dynamic huffman coding. Journal of algorithms, 6(2):163-180, 1985.
[28] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
[29] Manoj Kumar, Mohammad Babaeizadeh, Dumitru Erhan, Chelsea Finn, Sergey Levine, Laurent Dinh, and Durk Kingma. Videoflow: A conditional flow-based model for stochastic video generation. In International Conference Learning Representations, 2020.
[30] David JC MacKay, Information theory, inference and learning algorithms. Cambridge university press, 2003.
[31] Matthew V Mahoney, Fast text compression with neural networks. In FLAIRS conference, pages 230-234, 2000.
[32] Matthew V Mahoney. Adaptive weighing of context models for lossless data compression. Technical report, 2005.
[33] Detlev Marpe, Heiko Schwarz, and Thomas Wiegand. Context-based adaptive binary arithmetic coding in the h. 264/ave video compression standard. IEEE Transactions on circuits and systems for video technology, 13(7):620-636, 2003.
[34] Fabian Mentzer, Eirikur Agustsson, Michael Tschannen, Radu Timofte, and Luc Van Gool. Practical full resolution learned lossless image compression. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 10629-10638, 2019.
[35] Fabian Mentzer, Luc Van Gool, and Michael Tschannen. Learning better lossless compression using lossy compression. Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 6638 6647, 2020.
[36] Eric Nalisnick, Akihiro Matsukawa, Yee Whye Teh, Dilan Gorur, and Balaji Lakshminarayanan. Do deep generative models know what they don't t know? In International Conference on Learning Representations, 2019.
[37] Eric Nalisnick, Akihiro Matsukawa, Yee Whye Teh, and Balaji Lakshminarayanan. De- tecting -iitribttdit inputs to deep generative models using typicality. arXiv preprint 190.:99906.2994, 2019.
12

---

[38] William B. Pennebaker, Joan L. Mitchell, GG Langdon, and Ronald B Arps. An overview of the basic principles of the q-coder adaptive binary arithmetic coder. IBM Journal of research and development, 32(6):71 1988.
[39] Majid Rabbani. Jpeg2000: Image compression fundamentals, standards and practice. Journal of Electronic Imaging, 11(2):286, 2002.
[40] Greg Roelofs and Richard Koman. PNG: the definitive guide. O'Reilly & Associates, Inc., 1999.
[41] Tim Salimans, Andrej Karpathy, Xi Chen, and Diederik P. Kingma. Pixelcn+++: Improving the pixelenn with discretized logistic mixture likelihood and other modifications. In 5th International Conference on Learning Representations, ICLR 2017.
[42] Jürgen Schmidhuber and Stefan Heil, Predictive coding with neural nets: Application to text compression. In Advances in Neural Information Processing Systems, pages 1047-1054, 1995.
[43] Jürgen Schmidhuber and Stefan Heil. Sequential neural text compression. IEEE Transactions on Neural Nenworks, 7(1):142-146: 1996.
[44] Kedar Tatwawadi. Deepzip: Lossless compression using recurrent networks. URL https://web. pdf. 2018.
stanford. eduullass/es222//rrrrrr///
[45] Lucas Theis, Aäron van den Oord, and Matthias Bethge. A note on the evaluation of generative models. In 4th International Conference on Learming Representations, ICLR 2016.
[46] Bart Thomee, David A Shamma, Gerald Friedland, Benjamin Elizalde, Karl Ni, Douglas Poland, Damian Borth, and Li-Jia Li. Yfcc100m: The new data in multimedia research. Communications of the ACM, 59(2):64-733 2016.
[47] James Townsend. Lossless Compression with Latent Variable Models. PhD Thesis, UCL (University College London), 2021.
[48] James Townsend, Thomas Bird, and David Barber. Practical lossless compression with latent variables using bits back coding. In International Conference Learning Representations, 2019.
[49] James Townsend, Thomas Bird, Julius Kunze, and David Barber. Hilloc: lossless image compression with hierarchical latent variable models. In International Conference on Learning Representations, 2020.
[50] Benigno Uria, lain Murray, and Hugo Larochelle. Ruade: The real-valued neural autoregressive density-estimator. In Proceedings of the 26th International Conference on Neural Information Processing Systems Volume 2, 2013.
[51] Rianne den Berg, Alexey A Gritsenko, Mostafa Dehghani, Casper Kaae Sønderby, and Tim Salimans. Idf++: Analyzing and improving integer discrete flows for lossless compression. In International Conference on Learning Representations, 2020.
[52] Ties van Rozendaal, Iris A. M. Huijben, and Taco Cohen. Overfitting for fun and profit: Instance-adaptive data compression. In ICLR, 2021.
[53] Chris S Wallace. Classification by minimum message-length inference. In International Conference on Computing and Information, pages 72-81. Springer, 1990.
[54] Ian H Witten, Radford M Neal, and John G Cleary. Arithmetic coding for data compression. Communications of the ACM, 30(6):520 52005050-5400 1987.
[55] Shifeng Zhang, Chen Zhang, Ning Kang, and Zhenguo Li. ivpf: Numerical invertible volume preserving flow for efficient lossless compression. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 620-629, 2021.
[56] Jacob Ziv and Abraham Lempel. universal algorithm for sequential data compression. IEEE Transactions on information theory, 23(3):337-343, 1977.
13


Reviews:
[{"review_id": "zsfqlwG1SC_", "reviewer": "Reviewer_s1Vi", "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.\n\nThe 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.", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nQuality = 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.\n\nClarity = 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.\n\nSignificance = 2/5. Although I think the problem setting is interesting, the relatively low novelty (at least at a conceptual level) hinders overall significance.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes\n\nI 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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "kGBkn_rpXDu", "reviewer": "Reviewer_9cFX", "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.", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nThe experiments are clean and simple and show a clear benefit of OSOA. Enough details are provided to enable reproducibility. \n\nThe 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.\n\nAlthough 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.\n\nSome downsides of OSOA, that would be good to discuss at more length in the paper\nGetting deterministic training to work in practice, across different devices, will be very challenging\nNot only encoding time, but also decoding time is greatly increased because it will require training.\n\nOverall I think this is an innovative paper with a solid experimental validation, that is likely to spur further work in the DGM compression literature.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Some limitations could be better discussed (see above). ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "ivlvkCxtFg", "reviewer": "Reviewer_d4fb", "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.", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "### Strengths\nI 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. \n\n### Concerns\n- **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.\n   - 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.\n  - 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.  \n\n- **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:\n  - 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.\n  - 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.  \n\n- **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._   \n\n\n#### Reference\n[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.\n[2] https://en.wikipedia.org/wiki/Context-adaptive_binary_arithmetic_coding", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors thoroughly discuss potential societal impacts.", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "NCiLwLGA79t", "reviewer": "Reviewer_Tx3u", "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.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Originality:**\n\nAlthough 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.\n\n\n\n**Clarity:**\n\nThe 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:\n1. 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\".\n2. 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.\n3. 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.\n\n\n**Quality:**\n\nThe claims and evaluation methodology appear mostly sound. As noted above, the clarity of the paper can be improved.\nOn 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++)?\n\n\n**Significance:**\n\nThe 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. \n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "**Limitations**\n\n1. 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.\n2. 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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

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)