# Information-theoretic generalization bounds for black-box learning algorithms

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

## Key facts

- Cited by 49 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 42 references that are in the map.
- First posted on arXiv 4 Oct 2021.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Membership Inference Attacks against Machine Learning Models](https://mlsanity.com/paper/1610.05820/) (2016)
- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [Fantastic Generalization Measures and Where to Find Them](https://mlsanity.com/paper/1912.02178/) (2019)
- [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)
- [Algorithmic Stability for Adaptive Data Analysis](https://mlsanity.com/paper/1511.02513/) (2015)
- [Information-Theoretic Generalization Bounds for Stochastic Gradient Descent](https://mlsanity.com/paper/2102.00931/) (2021)
- [Generalization Error Bounds for Noisy, Iterative Algorithms](https://mlsanity.com/paper/1801.04295/) (2018)
- [Generalization Error Bounds Via R'enyi-, f-Divergences and Maximal Leakage](https://mlsanity.com/paper/1912.01439/) (2019)
- [Calibrating Noise to Variance in Adaptive Data Analysis](https://mlsanity.com/paper/1712.07196/) (2017)
- [On Random Subset Generalization Error Bounds and the Stochastic Gradient Langevin Dynamics Algorithm](https://mlsanity.com/paper/2010.10994/) (2020)
- [Membership Inference Attacks on Deep Regression Models for Neuroimaging](https://mlsanity.com/paper/2105.02866/) (2021)
- [Estimating informativeness of samples with Smooth Unique Information](https://mlsanity.com/paper/2101.06640/) (2021)
- [On-Average KL-Privacy and its equivalence to Generalization for Max-Entropy Mechanisms](https://mlsanity.com/paper/1605.02277/) (2016)

## Built on by (most cited first, 30 of 49)

- [A New Family of Generalization Bounds Using Samplewise Evaluated CMI](https://mlsanity.com/paper/2210.06422/) (2022)
- [Knowledge Overshadowing Causes Amalgamated Hallucination in Large Language Models](https://mlsanity.com/paper/2407.08039/) (2024)
- [Rate-Distortion Theoretic Generalization Bounds for Stochastic Learning Algorithms](https://mlsanity.com/paper/2203.02474/) (2022)
- [Tighter Information-Theoretic Generalization Bounds from Supersamples](https://mlsanity.com/paper/2302.02432/) (2023)
- [Limitations of Information-Theoretic Generalization Bounds for Gradient Descent Methods in Stochastic Convex Optimization](https://mlsanity.com/paper/2212.13556/) (2022)
- [Fantastic Generalization Measures are Nowhere to be Found](https://mlsanity.com/paper/2309.13658/) (2023)
- [Understanding Generalization via Leave-One-Out Conditional Mutual Information](https://mlsanity.com/paper/2206.14800/) (2022)
- [Generalization Bounds with Data-dependent Fractal Dimensions](https://mlsanity.com/paper/2302.02766/) (2023)
- [Rate-Distortion Theoretic Bounds on Generalization Error for Distributed Learning](https://mlsanity.com/paper/2206.02604/) (2022)
- [Information Complexity of Stochastic Convex Optimization: Applications to Generalization and Memorization](https://mlsanity.com/paper/2402.09327/) (2024)
- [Time-Independent Information-Theoretic Generalization Bounds for SGLD](https://mlsanity.com/paper/2311.01046/) (2023)
- [On the Generalization for Transfer Learning: An Information-Theoretic Analysis](https://mlsanity.com/paper/2207.05377/) (2022)
- [Evaluated CMI Bounds for Meta Learning: Tightness and Expressiveness](https://mlsanity.com/paper/2210.06511/) (2022)
- [Minimum Description Length and Generalization Guarantees for Representation Learning](https://mlsanity.com/paper/2402.03254/) (2024)
- [Information-Theoretic Generalization Bounds for Deep Neural Networks](https://mlsanity.com/paper/2404.03176/) (2024)
- [Information-theoretic Generalization Analysis for Expected Calibration Error](https://mlsanity.com/paper/2405.15709/) (2024)
- [Data-dependent Generalization Bounds via Variable-Size Compressibility](https://mlsanity.com/paper/2303.05369/) (2023)
- [On Leave-One-Out Conditional Mutual Information For Generalization](https://mlsanity.com/paper/2207.00581/) (2022)
- [A unified framework for information-theoretic generalization bounds](https://mlsanity.com/paper/2305.11042/) (2023)
- [Sample-Conditioned Hypothesis Stability Sharpens Information-Theoretic Generalization Bounds](https://mlsanity.com/paper/2310.20102/) (2023)
- [Recognizable Information Bottleneck](https://mlsanity.com/paper/2304.14618/) (2023)
- [Understanding the Generalization Ability of Deep Learning Algorithms: A Kernelized Renyi's Entropy Perspective](https://mlsanity.com/paper/2305.01143/) (2023)
- [Comparing Comparators in Generalization Bounds](https://mlsanity.com/paper/2310.10534/) (2023)
- [Slicing Mutual Information Generalization Bounds for Neural Networks](https://mlsanity.com/paper/2406.04047/) (2024)
- [Generalization Bounds via Conditional f-Information](https://mlsanity.com/paper/2410.22887/) (2024)
- [Formal limitations of sample-wise information-theoretic generalization bounds](https://mlsanity.com/paper/2205.06915/) (2022)
- [How Does Distribution Matching Help Domain Generalization: An Information-theoretic Analysis](https://mlsanity.com/paper/2406.09745/) (2024)
- [Fairness Overfitting in Machine Learning: An Information-Theoretic Perspective](https://mlsanity.com/paper/2506.07861/) (2025)
- [Fisher information flow in artificial neural networks](https://mlsanity.com/paper/2509.02407/) (2025)
- [Information-Theoretic Generalization Bounds for Transductive Learning and its Applications](https://mlsanity.com/paper/2311.04561/) (2023)

## Abstract (arXiv)

We derive information-theoretic generalization bounds for supervised learning algorithms based on the information contained in predictions rather than in the output of the training algorithm. These bounds improve over the existing information-theoretic bounds, are applicable to a wider range of algorithms, and solve two key challenges: (a) they give meaningful results for deterministic algorithms and (b) they are significantly easier to estimate. We show experimentally that the proposed bounds closely follow the generalization gap in practical scenarios for deep learning.