OSOA: One-Shot Online Adaptation of Deep Generative Models for Lossless Compression
Year: 2021

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.

heading: 1 Introduction
text: 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, a large number of machine learning approaches, predominantly deep generative models (DGMs), have been proposed for lossless compression [34, 48, 19, 17, 51]. As indicated by Shannon’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. It is the powerful approximation ability of DGMs that enables more precise estimation of the ground truth distribution [23, 41, 24, 29] and enables DGMs based compression algorithms to outperform the conventional counter-parties in terms of the compression ratio.
However, in real production scenarios, both space and time efficiencies are desirable. While more space efficiency is provided by higher compression ratio with DGMs based lossless compression algorithms, training of the probabilistic models is time consuming. Training a 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 is using one probabilistic model
∗Work done during employment at Huawei Technologies R&D UK
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
for many different datasets. Since each dataset can follow a 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 to 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 is the mechanism that can update the current distribution to a 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 is 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 on the unrolling procedure. Under this new setting, 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.
Apart from the novel setting formulation, we showcase 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. 3, we formulate the setting of OSOA, discuss associated codec designing principles and propose a vanilla OSOA algorithm. In Sec. 4, we validate the setting by comparison with baselines, explore the strategies for further trade-off and discuss societal considerations. In Sec. 5, we discuss some related work. In Sec. 6, we summarise the paper, offer insights into our findings and point out promising future work directions.

heading: 2 Preliminary
text: 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 [21], 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 a result, popular codecs adopted by DGM based algorithms are normally based on AC or ANS, e.g., [34, 19, 35]. The main difference between AC and ANS is that the former encodes and decodes in a first-in-first-out (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(x)]. 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 as per Shannon’s source coding theorem [30]. Specifically, compressing data from distribution p(x) with distribution q(x) will lead to the expected extra codelength at KL(p(x)||q(x)). Coding with Explicit Deep Generative Models Since the entropy coders require probability values, implicit DGMs, e.g., generative adversarial networks (GANs) [11], cannot be readily used for lossless
compression. For explicit DGMs, the learning principle is either maximum likelihood estimation (MLE) [41, 24, 16]:
θ̂ = arg min θ∈Θ
Ex∼p∗(x)[− log pθ(x)] (1)
or maximising the evidence lower bound (ELBO) of the logarithm evidence log pθ(x) [23, 49]:
θ̂, φ̂ = arg minθ∈Θ,φ∈ΦEx∼p∗(x)[−L(θ, φ, x)], (2)
where L(θ, φ, x) = Eqφ(z|x)[− log qφ(z|x) + log pθ(x|z)pθ(z)]. Note that x is a 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 a discrete model or stipulate a continuous model with the dequantization technique [50, 45]. If one stipulates a discrete model, where pθ(x) denotes the probabilistic mass function of the model, the objective function in Eq. 1 delegates the expected codelength when using pθ(x) for entropy coding. If one stipulates a continuous model, one normally dequantizes the discrete data x with a continuous noise u uniformly distributed on the unit hypercube, and gets the dequantized variable y = x + u with distribution p∗(y). After fitting the probabilistic density function pθ(y) of the model to the the probability density p∗(y) of the dequantized distribution, one needs to discretise pθ(y) and use the discretised distribution for entropy coding. In this case, the MLE objective Ey∼p∗(y)[− log pθ(y)] 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 [16, 18, 19, 51, 17, 55].
When learning with ELBO, one usually stipulates discrete models for x, i.e., pθ(x|z) is a probabilistic mass function, and continuous models for z, i.e., qφ(z|x) and pθ(z) are probabilistic density functions. Furthermore, one usually does not have direct access to the close form of pθ(x) but the generative components pθ(x|z) and pθ(z). To use pθ(x|z) and pθ(z) for efficient coding, a technique called bitsback [53, 15] is employed, which additionally involves the approximate posterior distribution qφ(z|x) learned together with the generative components [48, 49, 26]. In these cases, the discretisation precision of the latent variable will not effect the average codelength, delegated by the objective in Eq 2, with consistent discretisation adopted for the latent distributions [48]. It is 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.

heading: 3 One-shot online adaptation
text: 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 in Alg. 1. 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 an optimiser, which can be a gradient based optimiser or a learning based meta optimiser, and associated parameters, to update a model pθt−1(x) to pθt(x) with a data batch Bt. The codec module C contains an entropy coder, a 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 1: Inbuilt attributes: pθ0(x), D, C 2: Input: data {xi}Ni=1 3: Form data batches {Bt}Tt=1 from data {xi}Ni=1 4: for t = 1 to T do 5: C.encode_or_cache(pθt−1(x), Bt); 6: pθt(x) = D(pθt−1(x), Bt); 7: end for 8: Output: cf from C.
OSOA Decoding 1: Inbuilt attributes: pθ0(x), D, C 2: Input: code cf 3: Initialise C with cf 4: for t = 1 to T do 5: Bt ← C.decode(pθt−1(x)); 6: pθt(x) = D(pθt−1(x), Bt); 7: end for 8: Output: data {xi}Ni=1 from {Bt}Tt=1
Stage 1: Pretraining A base model pθ0(x) is obtained by solving the problem defined in Eq. 1 or Eq. 2 on a pretraining dataset.
Stage 2: OSOA Encoding A sequence of distributions {pθt(x)}Tt=1 will be unrolled through the adaptation procedure by the deterministic dynamical system D with batches {Bt}Tt=1. Specifically, at each step t, one 1) inputs the model pθt−1(x) and the data batch Bt to the codec module and 2) performs the dynamical system D on pθt−1(x) with Bt and obtains the updated model pθt(x). In 1), the method C.encode_or_cache determines whether to directly encode the current batch (FIFO style) or save the needed information, i.e., 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 cf will be output from the codec module.
Stage 3: OSOA Decoding One uses the codeword cf from the OSOA Encoding stage to initialise the codeword variable in C and starts the iterative decoding process as follows. At each step t, one 1) uses the method C.decode to decode Bt from the codeword variable with pθt−1(x) and 2) updates the model with the decoded batch Bt by the dynamical system D. As a result, the same sequence of distributions {pθt(x)}Tt=1 will be unrolled and all the data batches {Bt}Tt=1 will also be decoded.
Methods in the codec module To recover the exact distribution sequence {pθt(x)}Tt=1 in the decoding stage, one has to decode the data batches in the order of {B1, B2, ..., BT }. For DGMs based algorithms with an FIFO style coder, e.g., AC, one can consecutively encode the batch sequence {Bt}Tt=1 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. 1. 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. 1 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. 1 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 1: Inbuilt attributes: coder 2: Input: pθt−1(x), Bt 3: coder.encode(pθt−1(x), Bt); FILO coders 1: Inbuilt attributes: coder, cache, m 2: Input: pθt−1(x), Bt
3: cache.append((pθt−1(x), Bt)); 4: if len(cache) = m or last_batch then 5: for p(x), B in reversed(cache) do 6: coder.encode(p(x), B); 7: end for 8: cache.empty() 9: end if
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 pθ0(x) is pretrained on the same data modality, e.g., HiLLoC [49] pretrained on CIFAR10 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 pθ0(x) for certain data modality. Stage 2. Perform OSOA with base model from the last stage. The dataset to compress S should be first split to T
batches, i.e., S = {Bt}Tt=1. For 1 ≤ t ≤ T , we first use pθt−1(x) 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 pθt(x). Stage 3. Perform OSOA with base model from Stage 1. The data splitting strategy is the same as Stage 2. For 1 ≤ t ≤ T , we first use pθt−1(x) to decode the t-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 pθt(x). Note the entropy coding part is omitted for narrative simplicity, and we refer readers to Appendix A for more details.

heading: 4 Experiments with vanilla OSOA

heading: 4.1 Vanilla OSOA versus baselines
text: Datasets The datasets for base model pretraining are the renowned natural image datasets CIFAR10 [28] and ImageNet32 [7], including images of size 32× 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, we first obtain SET256 by cropping the central 256× 256 part in 217 RGB images with size larger than 256× 256 and downsample the obtained dataset into our targets, as conducted in [34]. We use Pillow to downsample the SET256 into SET128, SET64 and SET32 with the high quality filter Image.ANTIALIAS. The 217 RGB images are selected only with their shapes and no other discretionary criteria.
Experiments configurations Since an OSOA algorithm can be regarded as a general strategy to make a 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 [49] for hierarchical VAEs and IDF++ [51] for normalizing flows, to validate the OSOA setting. Specifically, for HiLLoC, we use the ResNet VAE (RVAE) 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 as 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 [51], 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-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.
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 FineTune, 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 FineTune. For FineTune v1, we fine tune the pretrained model for 2 epochs, as the whole OSOA Encoding & Decoding procedures involve 2 epochs of adaptations in total. For FineTune v2, we fine tune the pretrained model for 4 epochs for HiLLoC (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 [1] and it could cause extra time
cost in current deep learning frameworks. The time ratio we measured with/without the determinism is 1.98 (HiLLoC) in TensorFlow 1.14 [4] with tensorflow-determinism 0.3.0 [3] and 1.34 (IDF++) in Pytorch 1.6 [2]. For FineTune 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 FineTune baselines into consideration, we convert the model (in float32) storage size into effective bpd values and show them in the Model column in Table 2. 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, a lower value indicates a higher compression ratio. The time costs of OSOA and baselines 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 in 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 2 Right). Nevertheless, by comparing the decreased code space shown in green and the increased model space shown in red for FineTune v1 or FineTune v2 in Table 2, one can see that with the same optimisation budget or time budget, OSOA exhibits better total space efficiency than FineTune. For instance, with the CIFAR10 pretrained HiLLoC on SET32, OSOA takes 46.73% less space than FineTune v2, with the same model training cost. To better understand the comparison between OSOA and FineTune v2 on SET128, we take the CIFAR10
pretrained HiLLoC and fix the order of images. If we only compress the first 216, 215 and 214 images in SET128, the FineTune 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 FineTune v2 respectively. Therefore, OSOA remains a clear net advantage than FineTune with the same time budget up to a reasonable large sample size even on large size images. From the comparison between OSOA and FineTune v3, one can see that the space advantage is still valid even if we conduct the FineTune for much longer time for SET32/64. FineTune v3 performs better on space efficiency on SET128, but it takes more than 4 times as much time as 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 an 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, e.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 a 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. 2 Middle and Right, with the CIFAR10 pretrained HiLLoC on SET32 and SET128. To make the bpd values comparable, we use the same batch order for OSOA, FineTune and PreTrain 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/FineTune 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 - FineTune v1) is the extra cost of compressing the 100th batch with OSOA at the 100th OSOA Encoding step instead of FineTune v1 (with the fine-tuned model). Note that a negative difference value indicates that OSOA performs better than the corresponding baseline for that batch. From Fig. 2 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 FineTune decreases, which validates the benefits brought by adaptation with previous batches to following batches in OSOA.
Note that the theoretical bpd values reported in this paper are evaluated based on the discretised distributions of models for coding. Moreover, for HiLLoC, 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.

heading: 4.2 Vanilla OSOA variants to prioritise space or time efficiency
text: 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. 2 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.1 and conduct vanilla OSOA with multiple updates per batch. Note that each data batch is only used in 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 CIFAR10 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 HiLLoC and IDF++, and it can even further improve the bpd by around 0.4 for HiLLoC. It is 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.
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 so significant, cf. Fig 2 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 or 2.690 respectively, where one can accelerate the model adaptation efficiency by 8 times with the bpd cost less than 0.1.

heading: 4.3 Discussion on DGMs for data lossless compression
text: Probabilistic modelling with DGMs for data generation encourages precise modelling of the target dataset for high fidelity generation. Different from generation purpose modelling, lossless compression purpose modelling only calls for high density values. The phenomena, DGMs assigning high density values for out-of-distribution (OOD) data [36, 6, 37] and plausible performance of pretrained models for OOD datasets lossless compression [49, 55], indicate that data generation 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 statistics more than high-level semantics, and we show in above sections and Fig. 3 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. 3 (a), (b), (d) and (e). At the local feature level, e.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 FineTune from PreTrain. While such local feature transfer largely originates from the small learning rate used in OSOA and FineTune, learning rate of too small or too large values will impede the performance, cf. Fig. 3 (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
from the trained models, e.g., the third row and fifth column in Fig. 3 (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 a 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 on low resolution and non-sensitive images can offer good performance on images of different resolutions and semantics. Accordingly, it is promising to build societally friendly and effective DGMs base lossless compression algorithms with pretraining + adaptation style frameworks, e.g., OSOA, and careful incorporation of pretraining data.

heading: 5 Related work
text: OSOA de facto defines a paradigm to compress the distribution (model) sequence. The high level principle of it can trace back to a simple mathematical fact: a sequence can be uniquely determined by an initial point and a deterministic transition dynamics. In this section, we provide a non-exhaustive list of how this high level principle can be instantiated in compression related literature.
[43, 42] 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 [44, 12] 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 is 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 a pretrained model and the benefit from pretrained models of datasets
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 is 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 a 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 to the developments in the deep learning literature, this high level principle has also been investigated for data compression. Adaptive dictionary methods, e.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 to gradually converge to 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 to 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.

heading: 6 Conclusion and future work
text: 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. Second, 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.

Review summaries:
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.

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.

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.

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.