# Rate-Distortion Analysis of Minimum Excess Risk in Bayesian Learning

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 31 references that are in the map.
- First posted on arXiv 10 May 2021.

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

- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [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)
- [How much does your data exploration overfit? Controlling bias via information usage](https://mlsanity.com/paper/1511.05219/) (2015)
- [Sharpened Generalization Bounds based on Conditional Mutual Information and an Application to Noisy, Iterative Algorithms](https://mlsanity.com/paper/2004.12983/) (2020)
- [Chaining Mutual Information and Tightening Generalization Bounds](https://mlsanity.com/paper/1806.03803/) (2018)
- [Minimum Excess Risk in Bayesian Learning](https://mlsanity.com/paper/2012.14868/) (2020)
- [Rate Distortion For Model Compression: From Theory To Practice](https://mlsanity.com/paper/1810.06401/) (2018)
- [Information-Theoretic Understanding of Population Risk Improvement with Model Compression](https://mlsanity.com/paper/1901.09421/) (2019)
- [Rate-Distortion Bounds on Bayes Risk in Supervised Learning](https://mlsanity.com/paper/1605.02268/) (2016)

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

- [Information-theoretic Generalization Analysis for Expected Calibration Error](https://mlsanity.com/paper/2405.15709/) (2024)
- [f-divergences and their applications in lossy compression and bounding generalization error](https://mlsanity.com/paper/2206.11042/) (2022)
- [Information-Theoretic Analysis of Minimax Excess Risk](https://mlsanity.com/paper/2202.07537/) (2022)
- [Information-theoretic Analysis of Test Data Sensitivity in Uncertainty](https://mlsanity.com/paper/2307.12456/) (2023)
- [Lossless Transformations and Excess Risk Bounds in Statistical Inference](https://mlsanity.com/paper/2307.16735/) (2023)
- [Information-Theoretic Bayes Risk Lower Bounds for Realizable Models](https://mlsanity.com/paper/2111.04579/) (2021)
- [Information-Theoretic Minimax Regret Bounds for Reinforcement Learning based on Duality](https://mlsanity.com/paper/2410.16013/) (2024)
- [An Information-Theoretic Analysis of The Cost of Decentralization for Learning and Inference Under Privacy Constraints](https://mlsanity.com/paper/2110.05014/) (2021)
- [Excess risk analysis for epistemic uncertainty with application to variational inference](https://mlsanity.com/paper/2206.01606/) (2022)
- [How Wrong Can a Good Predictor Be? Diverging Updates with Vanishing Predictive KL](https://mlsanity.com/paper/2609.11132/) (2026)

## Abstract (arXiv)

In parametric Bayesian learning, a prior is assumed on the parameter W which determines the distribution of samples. In this setting, Minimum Excess Risk (MER) is defined as the difference between the minimum expected loss achievable when learning from data and the minimum expected loss that could be achieved if W was observed. In this paper, we build upon and extend the recent results of (Xu & Raginsky, 2020) to analyze the MER in Bayesian learning and derive information-theoretic bounds on it. We formulate the problem as a (constrained) rate-distortion optimization and show how the solution can be bounded above and below by two other rate-distortion functions that are easier to study. The lower bound represents the minimum possible excess risk achievable by any process using R bits of information from the parameter W. For the upper bound, the optimization is further constrained to use R bits from the training set, a setting which relates MER to information-theoretic bounds on the generalization gap in frequentist learning. We derive information-theoretic bounds on the difference between these upper and lower bounds and show that they can provide order-wise tight rates for MER under certain conditions. This analysis gives more insight into the information-theoretic nature of Bayesian learning as well as providing novel bounds.