# Towards Empirical Sandwich Bounds on the Rate-Distortion Function

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 81 references that are in the map.
- First posted on arXiv 23 Nov 2021.

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

- [Microsoft COCO: Common Objects in Context](https://mlsanity.com/paper/1405.0312/) (2014)
- [Auto-Encoding Variational Bayes](https://mlsanity.com/paper/1312.6114/) (2013)
- [Categorical Reparameterization with Gumbel-Softmax](https://mlsanity.com/paper/1611.01144/) (2016)
- [Large Scale GAN Training for High Fidelity Natural Image Synthesis](https://mlsanity.com/paper/1809.11096/) (2018)
- [The Concrete Distribution: A Continuous Relaxation of Discrete Random Variables](https://mlsanity.com/paper/1611.00712/) (2016)
- [Variational image compression with a scale hyperprior](https://mlsanity.com/paper/1802.01436/) (2018)
- [Conditional Image Generation with PixelCNN Decoders](https://mlsanity.com/paper/1606.05328/) (2016)
- [End-to-end Optimized Image Compression](https://mlsanity.com/paper/1611.01704/) (2016)
- [Masked Autoregressive Flow for Density Estimation](https://mlsanity.com/paper/1705.07057/) (2017)
- [Joint Autoregressive and Hierarchical Priors for Learned Image Compression](https://mlsanity.com/paper/1809.02736/) (2018)
- [Improving Variational Inference with Inverse Autoregressive Flow](https://mlsanity.com/paper/1606.04934/) (2016)
- [Learned Image Compression with Discretized Gaussian Mixture Likelihoods and Attention Modules](https://mlsanity.com/paper/2001.01568/) (2020)
- [On Variational Bounds of Mutual Information](https://mlsanity.com/paper/1905.06922/) (2019)
- [Importance Weighted Autoencoders](https://mlsanity.com/paper/1509.00519/) (2015)
- [The Intrinsic Dimension of Images and Its Impact on Learning](https://mlsanity.com/paper/2104.08894/) (2021)
- [Lossy Image Compression with Compressive Autoencoders](https://mlsanity.com/paper/1703.00395/) (2017)
- [Channel-wise Autoregressive Entropy Models for Learned Image Compression](https://mlsanity.com/paper/2007.08739/) (2020)
- [Nonlinear Transform Coding](https://mlsanity.com/paper/2007.03034/) (2020)
- [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)
- [Universally Quantized Neural Compression](https://mlsanity.com/paper/2006.09952/) (2020)
- [Bit-Swap: Recursive Bits-Back Coding for Lossless Compression with Hierarchical Latent Variables](https://mlsanity.com/paper/1905.06845/) (2019)
- [Compressing Images by Encoding Their Latent Representations with Relative Entropy Coding](https://mlsanity.com/paper/2010.01185/) (2020)
- [Compression with Flows via Local Bits-Back Coding](https://mlsanity.com/paper/1905.08500/) (2019)
- [Algorithms for the Communication of Samples](https://mlsanity.com/paper/2110.12805/) (2021)
- [Hierarchical Autoregressive Modeling for Neural Video Compression](https://mlsanity.com/paper/2010.10258/) (2020)
- [Improving Lossless Compression Rates via Monte Carlo Bits-Back Coding](https://mlsanity.com/paper/2102.11086/) (2021)
- [Evaluating Lossy Compression Rates of Deep Generative Models](https://mlsanity.com/paper/2008.06653/) (2020)
- [Finding the Mode of a Kernel Density Estimate](https://mlsanity.com/paper/1912.07673/) (2019)

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

- [An Introduction to Neural Data Compression](https://mlsanity.com/paper/2202.06533/) (2022)
- [Lossy Image Compression with Quantized Hierarchical VAEs](https://mlsanity.com/paper/2208.13056/) (2022)
- [QARV: Quantization-Aware ResNet VAE for Lossy Image Compression](https://mlsanity.com/paper/2302.08899/) (2023)
- [Computationally-Efficient Neural Image Compression with Shallow Decoders](https://mlsanity.com/paper/2304.06244/) (2023)
- [SC2 Benchmark: Supervised Compression for Split Computing](https://mlsanity.com/paper/2203.08875/) (2022)
- [Unity by Diversity: Improved Representation Learning in Multimodal VAEs](https://mlsanity.com/paper/2403.05300/) (2024)
- [Neural Estimation of the Rate-Distortion Function With Applications to Operational Source Coding](https://mlsanity.com/paper/2204.01612/) (2022)
- [Approaching Rate-Distortion Limits in Neural Compression with Lattice Transform Coding](https://mlsanity.com/paper/2403.07320/) (2024)
- [Estimating the Rate-Distortion Function by Wasserstein Gradient Descent](https://mlsanity.com/paper/2310.18908/) (2023)
- [Fundamental Limits of Two-layer Autoencoders, and Achieving Them with Gradient Methods](https://mlsanity.com/paper/2212.13468/) (2022)
- [Theoretical Bound-Guided Hierarchical VAE for Neural Image Codecs](https://mlsanity.com/paper/2403.18535/) (2024)
- [A Rate-Distortion-Classification Approach for Lossy Image Compression](https://mlsanity.com/paper/2405.03500/) (2024)
- [Optimal Neural Compressors for the Rate-Distortion-Perception Tradeoff](https://mlsanity.com/paper/2503.17558/) (2025)
- [Alternating Minimization Schemes for Computing Rate-Distortion-Perception Functions with f-Divergence Perception Constraints](https://mlsanity.com/paper/2408.15015/) (2024)

## Abstract (arXiv)

Rate-distortion (R-D) function, a key quantity in information theory, characterizes the fundamental limit of how much a data source can be compressed subject to a fidelity criterion, by any compression algorithm. As researchers push for ever-improving compression performance, establishing the R-D function of a given data source is not only of scientific interest, but also sheds light on the possible room for improving compression algorithms. Previous work on this problem relied on distributional assumptions on the data source (Gibson, 2017) or only applied to discrete data (Blahut, 1972; Arimoto, 1972). By contrast, this paper makes the first attempt at an algorithm for sandwiching the R-D function of a general (not necessarily discrete) source requiring only i.i.d. data samples. We estimate R-D sandwich bounds for a variety of artificial and real-world data sources, in settings far beyond the feasibility of any known method, and shed light on the optimality of neural data compression (Ball'e et al., 2021; Yang et al., 2022). Our R-D upper bound on natural images indicates theoretical room for improving state-of-the-art image compression methods by at least one dB in PSNR at various bitrates. Our data and code can be found at https://github.com/mandt-lab/empirical-RD-sandwich.