# Rate-Distortion Bounds on Bayes Risk in Supervised Learning

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 May 2016.

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

- [Rate-Distortion Analysis of Minimum Excess Risk in Bayesian Learning](https://mlsanity.com/paper/2105.04180/) (2021)
- [An Information-Theoretic Framework for Supervised Learning](https://mlsanity.com/paper/2203.00246/) (2022)
- [Information-Theoretic Bayes Risk Lower Bounds for Realizable Models](https://mlsanity.com/paper/2111.04579/) (2021)
- [Supervised Learning as Lossy Compression: Characterizing Generalization and Sample Complexity via Finite Blocklength Analysis](https://mlsanity.com/paper/2602.04107/) (2026)
- [Estimation-Prediction Tradeoff in Causal Probabilistic Temporal Graphs](https://mlsanity.com/paper/2606.28225/) (2026)

## Abstract (arXiv)

We present an information-theoretic framework for bounding the number of labeled samples needed to train a classifier in a parametric Bayesian setting. We derive bounds on the average Lp distance between the learned classifier and the true maximum a posteriori classifier, which are well-established surrogates for the excess classification error due to imperfect learning. We provide lower and upper bounds on the rate-distortion function, using Lp loss as the distortion measure, of a maximum a priori classifier in terms of the differential entropy of the posterior distribution and a quantity called the interpolation dimension, which characterizes the complexity of the parametric distribution family. In addition to expressing the information content of a classifier in terms of lossy compression, the rate-distortion function also expresses the minimum number of bits a learning machine needs to extract from training data to learn a classifier to within a specified Lp tolerance. We use results from universal source coding to express the information content in the training data in terms of the Fisher information of the parametric family and the number of training samples available. The result is a framework for computing lower bounds on the Bayes Lp risk. This framework complements the well-known probably approximately correct (PAC) framework, which provides minimax risk bounds involving the Vapnik-Chervonenkis dimension or Rademacher complexity. Whereas the PAC framework provides upper bounds the risk for the worst-case data distribution, the proposed rate-distortion framework lower bounds the risk averaged over the data distribution. We evaluate the bounds for a variety of data models, including categorical, multinomial, and Gaussian models. In each case the bounds are provably tight orderwise, and in two cases we prove that the bounds are tight up to multiplicative constants.