Towards Empirical Sandwich Bounds on the Rate-Distortion Function

Yibo Yang, Stephan Mandt

Introduction

The Rate-Distortion (R-D) function is a foundational concept in information theory. It defines the absolute minimum number of bits (rate) required to represent a data source for a given allowable level of error (distortion). For researchers developing compression algorithms, the R-D function is the "Holy Grail"—it reveals exactly how much room for improvement remains in current methods.

However, calculating the true R-D function is notoriously difficult. Traditional methods, like the Blahut-Arimoto algorithm, are restricted to discrete data and suffer from the curse of dimensionality, becoming computationally intractable for complex, high-dimensional data like natural images or audio. Consequently, the theoretical limits for these modalities have remained unknown, forcing researchers to rely on simplified statistical models.

This paper introduces a novel framework to "sandwich" the R-D function between empirical upper and lower bounds using only raw, independent and identically distributed (i.i.d.) data samples.

Methodology: Building the Sandwich

The authors propose a two-pronged approach to bound the true $R(D)$ curve:

  1. The Upper Bound (The Ceiling): The researchers establish a formal connection between Variational Autoencoders (VAEs) and R-D theory. They demonstrate that a $\beta$-VAE naturally minimizes an upper bound on the R-D function when its likelihood model is induced by a specific distortion metric (e.g., a Gaussian likelihood for Mean Squared Error). This insight allows the use of powerful deep generative models to estimate theoretically achievable compression rates.
  2. The Lower Bound (The Floor): Establishing a lower bound is mathematically more complex. The authors utilize a "dual" characterization of the R-D function, transforming the problem into a maximization task. They introduce a novel estimator inspired by Importance Weighted Autoencoders (IWAE) and employ a linearization trick to ensure the resulting estimate remains a valid lower bound, even when approximated.

By plotting both bounds, the authors create a "sandwich" region that must contain the true, unknown $R(D)$ function.

Empirical sandwich bounds across various datasets, including Gaussian, particle physics, and speech data. The shaded red region represents the space where the true R-D function must reside.

Key Insights and Results

The framework was evaluated across diverse datasets, including synthetic Gaussians, particle physics events, speech spectrograms, GAN-generated images, and natural image benchmarks (Kodak and Tecnick).

  • Validation on Structured Data: On synthetic Gaussian sources, the upper bound perfectly recovered the known analytical $R(D)$ curve. For particle physics and speech data, the bounds were remarkably tight. This demonstrates that modern neural compressors are already surprisingly close to optimal (within ~0.5 nats) for these specific data types.
  • Intrinsic vs. Ambient Dimension: A crucial discovery is that the tightness of the lower bound depends on the intrinsic dimension of the data (its actual degrees of freedom) rather than its ambient dimension (e.g., the raw number of pixels). The authors successfully produced tight bounds for high-resolution GAN images because those images were generated from a low-dimensional latent space.
  • The "One dB" Gap in Image Compression: When applied to natural images (the Kodak dataset), the authors' ResNet-VAE upper bound outperformed state-of-the-art traditional codecs like VTM/H.266, AV1, and existing neural models. The upper bound indicates that our best current neural compression algorithms are at least 1 dB (in PSNR) away from the theoretical limit at various bitrates. This proves there is still significant room for improvement in image compression research.
Results on image datasets. The right plot shows the upper bound on the Kodak dataset outperforming state-of-the-art codecs, revealing a theoretical gap of at least 1 dB PSNR.

Limitations and Future Directions

The primary limitation of this approach is the "curse of dimensionality" affecting the lower bound. While the upper bound scales effectively to complex natural images, the lower bound becomes loose when the data possesses high intrinsic dimensionality, such as raw, uncompressed natural photos.

Furthermore, the current practical implementation of the lower bound is restricted to squared error distortion. Future work may involve developing more expressive models for the lower bound estimator and exploring alternative distortion metrics to close the "sandwich" gap for highly complex, real-world data.

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 reveals the possible room for improvement in existing 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é 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/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