Towards Empirical Sandwich Bounds on the Rate-Distortion Function

Yibo Yang, Stephan Mandt

Abstract

The 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. Establishing the R-D function for real-world data is of significant scientific interest, as it reveals the potential room for improving existing compression algorithms. Previous methods relied on restrictive distributional assumptions or were limited to discrete data. This paper presents the first algorithm for "sandwiching" the R-D function of general, continuous sources using only i.i.d. data samples. By estimating these bounds across various artificial and real-world datasets, we demonstrate that state-of-the-art image compression methods still have at least 1 dB of PSNR room for improvement.

Introduction

In information theory, the Rate-Distortion function $R(D)$ represents the absolute minimum number of bits required to represent a data source for a given level of allowed distortion. For researchers in lossy compression, $R(D)$ is the ultimate benchmark: if an algorithm's performance matches the $R(D)$ curve, it has reached theoretical optimality.

However, for complex, high-dimensional data like natural images or speech, the true $R(D)$ function remains unknown. Classical tools like the Blahut-Arimoto algorithm are computationally infeasible for high-dimensional continuous data. Consequently, the field has lacked a rigorous way to measure the gap between current compression performance and the theoretical limit. This work addresses this gap by providing empirical upper and lower bounds—a "sandwich"—that contains the true $R(D)$ function.

Methodology: The Empirical Sandwich

The authors propose a two-pronged approach to bound the $R(D)$ function directly from data samples.

1. The Upper Bound via $\beta$-VAE

The researchers establish a theoretical connection between Variational Autoencoders (VAEs) and information theory. They prove that a $\beta$-VAE trained with a likelihood model corresponding to a specific distortion metric (e.g., Gaussian likelihood for Mean Squared Error) minimizes an upper bound on the $R(D)$ function. By utilizing highly expressive neural networks, the $\beta$-VAE can provide a tight empirical upper bound on the minimum rate required for a given distortion.

2. The Lower Bound via Dual Formulation

Establishing a lower bound is more challenging, as it requires proving that no possible algorithm can achieve a lower rate. The authors utilize a dual mathematical characterization of $R(D)$, transforming it into an unconstrained optimization problem. To handle the resulting complexity, they employ a $k$-sample estimator inspired by Importance Weighted Autoencoders (IWAE), allowing the lower bound to be optimized using standard stochastic gradient ascent.

Experimental Validation

The methodology was validated across synthetic and real-world datasets, including high-dimensional Gaussians, particle physics data, and speech spectrograms.

Empirical R-D sandwich bounds for Gaussian, particle physics, and speech data.

As shown in the experimental results, the proposed method successfully sandwiches the $R(D)$ function. In the case of 1000-dimensional Gaussian sources, the empirical upper bound converges precisely to the known analytical solution. For more complex data like speech (33-dimensional spectrograms) and particle physics data, the bounds create a clear "red zone" where the true theoretical limit must reside, providing a concrete target for compression efficiency.

Implications for Image Compression

A primary contribution of this work is the application of these bounds to natural image datasets, such as the Kodak benchmark. By calculating the empirical upper bound for natural images, the authors can compare theoretical limits against the performance of state-of-the-art (SOTA) neural and classical codecs.

Rate-quality curves for the Kodak dataset, comparing proposed upper bounds to state-of-the-art compression methods.

The results on the Kodak dataset are striking: the empirical upper bounds indicate that there is at least 1 dB PSNR of theoretical room for improvement over current SOTA neural image compression methods. This suggests that despite rapid progress in deep learning-based compression, significant gains in efficiency are still possible.

Discussion and Limitations

A key insight from the study is the distinction between nominal and intrinsic dimensionality. The tightness of the lower bound depends heavily on the data's intrinsic complexity. While the bounds are remarkably tight for data with low intrinsic dimension (such as GAN-generated images), the lower bound becomes looser as the complexity of the data increases. This "curse of the lower bound" remains a challenge for high-resolution natural images, where the lower bound currently plateaus earlier than the upper bound.

Conclusion

This work provides a novel framework for empirically estimating the fundamental limits of lossy compression. By bridging the gap between $\beta$-VAEs and rate-distortion theory, the authors offer a practical tool for quantifying the optimality of compression algorithms. The finding that natural image compression still has significant room for improvement provides a clear motivation for continued research into more efficient neural architectures and entropy models.

Summary updated

Abstract

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.
BibTeX
@inproceedings{yang2022towards,
  author = {Yibo Yang and Stephan Mandt},
  title = {{Towards Empirical Sandwich Bounds on the Rate-Distortion Function}},
  booktitle = {International Conference on Learning Representations},
  year = {2022},
  url = {https://openreview.net/forum?id=TLBV9AiH3o},
}
Figure