# Estimating the Rate-Distortion Function by Wasserstein Gradient Descent

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 69 references that are in the map.
- First posted on arXiv 29 Oct 2023.

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

- [Deep Unsupervised Learning using Nonequilibrium Thermodynamics](https://mlsanity.com/paper/1503.03585/) (2015)
- [Variational Inference: A Review for Statisticians](https://mlsanity.com/paper/1601.00670/) (2016)
- [Normalizing Flows for Probabilistic Modeling and Inference](https://mlsanity.com/paper/1912.02762/) (2019)
- [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)
- [Stein Variational Gradient Descent: A General Purpose Bayesian Inference Algorithm](https://mlsanity.com/paper/1608.04471/) (2016)
- [Learning Generative Models with Sinkhorn Divergences](https://mlsanity.com/paper/1706.00292/) (2017)
- [Lossy Image Compression with Compressive Autoencoders](https://mlsanity.com/paper/1703.00395/) (2017)
- [Nonlinear Transform Coding](https://mlsanity.com/paper/2007.03034/) (2020)
- [Sampling as optimization in the space of measures: The Langevin dynamics as a composite optimization problem](https://mlsanity.com/paper/1802.08089/) (2018)
- [Statistical bounds for entropic optimal transport: sample complexity and the central limit theorem](https://mlsanity.com/paper/1905.11882/) (2019)
- [Improving Inference for Neural Image Compression](https://mlsanity.com/paper/2006.04240/) (2020)
- [An Introduction to Neural Data Compression](https://mlsanity.com/paper/2202.06533/) (2022)
- [Mean-Field Langevin Dynamics: Exponential Convergence and Annealing](https://mlsanity.com/paper/2202.01009/) (2022)
- [Learning Gaussian Mixtures Using the Wasserstein-Fisher-Rao Gradient Flow](https://mlsanity.com/paper/2301.01766/) (2023)
- [Spread Divergence](https://mlsanity.com/paper/1811.08968/) (2018)
- [Sandwiching the marginal likelihood using bidirectional Monte Carlo](https://mlsanity.com/paper/1511.02543/) (2015)
- [Distribution Compression in Near-linear Time](https://mlsanity.com/paper/2111.07941/) (2021)
- [Towards Empirical Sandwich Bounds on the Rate-Distortion Function](https://mlsanity.com/paper/2111.12166/) (2021)
- [Displacement smoothness of entropic optimal transport](https://mlsanity.com/paper/2210.00225/) (2022)
- [Convergence Rates for Regularized Optimal Transport via Quantization](https://mlsanity.com/paper/2208.14391/) (2022)
- [Neural Estimation of the Rate-Distortion Function With Applications to Operational Source Coding](https://mlsanity.com/paper/2204.01612/) (2022)
- [On a Relation Between the Rate-Distortion Function and Optimal Transport](https://mlsanity.com/paper/2307.00246/) (2023)

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

- [Fundamental Limits of Prompt Compression: A Rate-Distortion Framework for Black-Box Language Models](https://mlsanity.com/paper/2407.15504/) (2024)
- [Unity by Diversity: Improved Representation Learning in Multimodal VAEs](https://mlsanity.com/paper/2403.05300/) (2024)
- [Hilbert's projective metric for functions of bounded growth and exponential convergence of Sinkhorn's algorithm](https://mlsanity.com/paper/2311.04041/) (2023)
- [Forward-Euler time-discretization for Wasserstein gradient flows can be wrong](https://mlsanity.com/paper/2406.08209/) (2024)
- [Alternating Minimization Schemes for Computing Rate-Distortion-Perception Functions with f-Divergence Perception Constraints](https://mlsanity.com/paper/2408.15015/) (2024)

## Abstract (arXiv)

In the theory of lossy compression, the rate-distortion (R-D) function R(D) describes how much a data source can be compressed (in bit-rate) at any given level of fidelity (distortion). Obtaining R(D) for a given data source establishes the fundamental performance limit for all compression algorithms. We propose a new method to estimate R(D) from the perspective of optimal transport. Unlike the classic Blahut--Arimoto algorithm which fixes the support of the reproduction distribution in advance, our Wasserstein gradient descent algorithm learns the support of the optimal reproduction distribution by moving particles. We prove its local convergence and analyze the sample complexity of our R-D estimator based on a connection to entropic optimal transport. Experimentally, we obtain comparable or tighter bounds than state-of-the-art neural network methods on low-rate sources while requiring considerably less tuning and computation effort. We also highlight a connection to maximum-likelihood deconvolution and introduce a new class of sources that can be used as test cases with known solutions to the R-D problem.