# Information-Theoretic Bayes Risk Lower Bounds for Realizable Models

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

## Key facts

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

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

- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [Spectrally-normalized margin bounds for neural networks](https://mlsanity.com/paper/1706.08498/) (2017)
- [Deep Double Descent: Where Bigger Models and More Data Hurt](https://mlsanity.com/paper/1912.02292/) (2019)
- [Benign Overfitting in Linear Regression](https://mlsanity.com/paper/1906.11300/) (2019)
- [A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks](https://mlsanity.com/paper/1707.09564/) (2017)
- [Information-theoretic analysis of generalization capability of learning algorithms](https://mlsanity.com/paper/1705.07809/) (2017)
- [Reasoning About Generalization via Conditional Mutual Information](https://mlsanity.com/paper/2001.09122/) (2020)
- [On the role of data in PAC-Bayes bounds](https://mlsanity.com/paper/2006.10929/) (2020)
- [A Farewell to the Bias-Variance Tradeoff? An Overview of the Theory of Overparameterized Machine Learning](https://mlsanity.com/paper/2109.02355/) (2021)
- [Fast rates in statistical and online learning](https://mlsanity.com/paper/1507.02592/) (2015)
- [Minimum Excess Risk in Bayesian Learning](https://mlsanity.com/paper/2012.14868/) (2020)
- [PAC-Bayes, MAC-Bayes and Conditional Mutual Information: Fast rate bounds that handle general VC classes](https://mlsanity.com/paper/2106.09683/) (2021)
- [Rate-Distortion Analysis of Minimum Excess Risk in Bayesian Learning](https://mlsanity.com/paper/2105.04180/) (2021)
- [Rate-Distortion Bounds on Bayes Risk in Supervised Learning](https://mlsanity.com/paper/1605.02268/) (2016)

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

- [Limitations of Information-Theoretic Generalization Bounds for Gradient Descent Methods in Stochastic Convex Optimization](https://mlsanity.com/paper/2212.13556/) (2022)

## Abstract (arXiv)

We derive information-theoretic lower bounds on the Bayes risk and generalization error of realizable machine learning models. In particular, we employ an analysis in which the rate-distortion function of the model parameters bounds the required mutual information between the training samples and the model parameters in order to learn a model up to a Bayes risk constraint. For realizable models, we show that both the rate distortion function and mutual information admit expressions that are convenient for analysis. For models that are (roughly) lower Lipschitz in their parameters, we bound the rate distortion function from below, whereas for VC classes, the mutual information is bounded above by dvclog(n). When these conditions match, the Bayes risk with respect to the zero-one loss scales no faster than Omega(dvc/n), which matches known outer bounds and minimax lower bounds up to logarithmic factors. We also consider the impact of label noise, providing lower bounds when training and/or test samples are corrupted.