# Information-Theoretic Analysis of Minimax Excess Risk

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 46 references that are in the map.
- First posted on arXiv 15 Feb 2022.

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

- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [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)
- [Information-Theoretic Generalization Bounds for SGLD via Data-Dependent Estimates](https://mlsanity.com/paper/1911.02151/) (2019)
- [Tightening Mutual Information Based Bounds on Generalization Error](https://mlsanity.com/paper/1901.04609/) (2019)
- [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)
- [Generalization Bounds via Information Density and Conditional Information Density](https://mlsanity.com/paper/2005.08044/) (2020)
- [Minimum Excess Risk in Bayesian Learning](https://mlsanity.com/paper/2012.14868/) (2020)
- [Rate-Distortion Analysis of Minimum Excess Risk in Bayesian Learning](https://mlsanity.com/paper/2105.04180/) (2021)
- [Chaining Meets Chain Rule: Multilevel Entropic Regularization and Training of Neural Nets](https://mlsanity.com/paper/1906.11148/) (2019)
- [Average-Case Information Complexity of Learning](https://mlsanity.com/paper/1811.09923/) (2018)
- [Continuity of Generalized Entropy and Statistical Learning](https://mlsanity.com/paper/2012.15829/) (2020)
- [Fast-Rate Loss Bounds via Conditional Information Measures with Applications to Neural Networks](https://mlsanity.com/paper/2010.11552/) (2020)
- [On the Information Complexity of Proper Learners for VC Classes in the Realizable Case](https://mlsanity.com/paper/2011.02970/) (2020)

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

- [Understanding Generalization via Leave-One-Out Conditional Mutual Information](https://mlsanity.com/paper/2206.14800/) (2022)
- [Lossless Transformations and Excess Risk Bounds in Statistical Inference](https://mlsanity.com/paper/2307.16735/) (2023)
- [Information-Theoretic Minimax Regret Bounds for Reinforcement Learning based on Duality](https://mlsanity.com/paper/2410.16013/) (2024)
- [Bounds on the Excess Minimum Risk via Generalized Information Divergence Measures](https://mlsanity.com/paper/2505.24117/) (2025)
- [Generalization Theory for Through-the-Wall Radar Human Activity Recognition](https://mlsanity.com/paper/2607.08144/) (2026)

## Abstract (arXiv)

Two main concepts studied in machine learning theory are generalization gap (difference between train and test error) and excess risk (difference between test error and the minimum possible error). While information-theoretic tools have been used extensively to study the generalization gap of learning algorithms, the information-theoretic nature of excess risk has not yet been fully investigated. In this paper, some steps are taken toward this goal. We consider the frequentist problem of minimax excess risk as a zero-sum game between the algorithm designer and the world. Then, we argue that it is desirable to modify this game in a way that the order of play can be swapped. We then prove that, under some regularity conditions, if the world and designer can play randomly the duality gap is zero and the order of play can be changed. In this case, a Bayesian problem surfaces in the dual representation. This makes it possible to utilize recent information-theoretic results on minimum excess risk in Bayesian learning to provide bounds on the minimax excess risk. We demonstrate the applicability of the results by providing information theoretic insight on two important classes of problems: classification when the hypothesis space has finite VC-dimension, and regularized least squares.