# Improving Lossless Compression Rates via Monte Carlo Bits-Back Coding

arXiv: https://arxiv.org/abs/2102.11086 · HTML: https://mlsanity.com/paper/2102.11086/

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 67 references that are in the map.
- First posted on arXiv 22 Feb 2021.

## Builds on (most cited first, 30 of 31)

- [Neural Discrete Representation Learning](https://mlsanity.com/paper/1711.00937/) (2017)
- [Categorical Reparameterization with Gumbel-Softmax](https://mlsanity.com/paper/1611.01144/) (2016)
- [Variational Inference with Normalizing Flows](https://mlsanity.com/paper/1505.05770/) (2015)
- [Density estimation using Real NVP](https://mlsanity.com/paper/1605.08803/) (2016)
- [WaveNet: A Generative Model for Raw Audio](https://mlsanity.com/paper/1609.03499/) (2016)
- [Generating Diverse High-Fidelity Images with VQ-VAE-2](https://mlsanity.com/paper/1906.00446/) (2019)
- [The Concrete Distribution: A Continuous Relaxation of Discrete Random Variables](https://mlsanity.com/paper/1611.00712/) (2016)
- [NICE: Non-linear Independent Components Estimation](https://mlsanity.com/paper/1410.8516/) (2014)
- [Variational image compression with a scale hyperprior](https://mlsanity.com/paper/1802.01436/) (2018)
- [End-to-end Optimized Image Compression](https://mlsanity.com/paper/1611.01704/) (2016)
- [Joint Autoregressive and Hierarchical Priors for Learned Image Compression](https://mlsanity.com/paper/1809.02736/) (2018)
- [NVAE: A Deep Hierarchical Variational Autoencoder](https://mlsanity.com/paper/2007.03898/) (2020)
- [Importance Weighted Autoencoders](https://mlsanity.com/paper/1509.00519/) (2015)
- [PixelCNN++: Improving the PixelCNN with Discretized Logistic Mixture Likelihood and Other Modifications](https://mlsanity.com/paper/1701.05517/) (2017)
- [A Recurrent Latent Variable Model for Sequential Data](https://mlsanity.com/paper/1506.02216/) (2015)
- [Variational Sequential Monte Carlo](https://mlsanity.com/paper/1705.11140/) (2017)
- [Filtering Variational Objectives](https://mlsanity.com/paper/1705.09279/) (2017)
- [Practical Lossless Compression with Latent Variables using Bits Back Coding](https://mlsanity.com/paper/1901.04866/) (2019)
- [Integer Discrete Flows and Lossless Compression](https://mlsanity.com/paper/1905.07376/) (2019)
- [Improving Inference for Neural Image Compression](https://mlsanity.com/paper/2006.04240/) (2020)
- [Auto-Encoding Sequential Monte Carlo](https://mlsanity.com/paper/1705.10306/) (2017)
- [Minimal Random Code Learning: Getting Bits Back from Compressed Model Parameters](https://mlsanity.com/paper/1810.00440/) (2018)
- [Importance Weighting and Variational Inference](https://mlsanity.com/paper/1808.09034/) (2018)
- [Bit-Swap: Recursive Bits-Back Coding for Lossless Compression with Hierarchical Latent Variables](https://mlsanity.com/paper/1905.06845/) (2019)
- [Hamiltonian Variational Auto-Encoder](https://mlsanity.com/paper/1805.11328/) (2018)
- [Compressing Images by Encoding Their Latent Representations with Relative Entropy Coding](https://mlsanity.com/paper/2010.01185/) (2020)
- [Reinterpreting Importance-Weighted Autoencoders](https://mlsanity.com/paper/1704.02916/) (2017)
- [HiLLoC: Lossless Image Compression with Hierarchical Latent Variable Models](https://mlsanity.com/paper/1912.09953/) (2019)
- [IDF++: Analyzing and Improving Integer Discrete Flows for Lossless Compression](https://mlsanity.com/paper/2006.12459/) (2020)
- [Computationally Efficient Neural Image Compression](https://mlsanity.com/paper/1912.08771/) (2019)

## Built on by (most cited first, 19 of 19)

- [An Introduction to Neural Data Compression](https://mlsanity.com/paper/2202.06533/) (2022)
- [Deep Generative Models through the Lens of the Manifold Hypothesis: A Survey and New Connections](https://mlsanity.com/paper/2404.02954/) (2024)
- [Differentiable Annealed Importance Sampling and the Perils of Gradient Noise](https://mlsanity.com/paper/2107.10211/) (2021)
- [What is the Relationship between Tensor Factorizations and Circuits (and How Can We Exploit it)?](https://mlsanity.com/paper/2409.07953/) (2024)
- [Lossless Compression with Probabilistic Circuits](https://mlsanity.com/paper/2111.11632/) (2021)
- [Sparse Probabilistic Circuits via Pruning and Growing](https://mlsanity.com/paper/2211.12551/) (2022)
- [Towards Empirical Sandwich Bounds on the Rate-Distortion Function](https://mlsanity.com/paper/2111.12166/) (2021)
- [Partition and Code: learning how to compress graphs](https://mlsanity.com/paper/2107.01952/) (2021)
- [Generalization Gap in Amortized Inference](https://mlsanity.com/paper/2205.11640/) (2022)
- [Scaling Continuous Latent Variable Models as Probabilistic Integral Circuits](https://mlsanity.com/paper/2406.06494/) (2024)
- [Probabilistic Integral Circuits](https://mlsanity.com/paper/2310.16986/) (2023)
- [Lossless compression with state space models using bits back coding](https://mlsanity.com/paper/2103.10150/) (2021)
- [Lossless Compression with Latent Variable Models](https://mlsanity.com/paper/2104.10544/) (2021)
- [Compressing Multisets with Large Alphabets using Bits-Back Coding](https://mlsanity.com/paper/2107.09202/) (2021)
- [Parallel Neural Local Lossless Compression](https://mlsanity.com/paper/2201.05213/) (2022)
- [Test-time adaptation for image compression with distribution regularization](https://mlsanity.com/paper/2410.12191/) (2024)
- [Random Edge Coding: One-Shot Bits-Back Coding of Large Labeled Graphs](https://mlsanity.com/paper/2305.09705/) (2023)
- [Latent Discretization for Continuous-time Sequence Compression](https://mlsanity.com/paper/2212.13659/) (2022)
- [Verified Reversible Programming for Verified Lossless Compression](https://mlsanity.com/paper/2211.09676/) (2022)

## Abstract (arXiv)

Latent variable models have been successfully applied in lossless compression with the bits-back coding algorithm. However, bits-back suffers from an increase in the bitrate equal to the KL divergence between the approximate posterior and the true posterior. In this paper, we show how to remove this gap asymptotically by deriving bits-back coding algorithms from tighter variational bounds. The key idea is to exploit extended space representations of Monte Carlo estimators of the marginal likelihood. Naively applied, our schemes would require more initial bits than the standard bits-back coder, but we show how to drastically reduce this additional cost with couplings in the latent space. When parallel architectures can be exploited, our coders can achieve better rates than bits-back with little additional cost. We demonstrate improved lossless compression rates in a variety of settings, especially in out-of-distribution or sequential data compression.