# Tighter Information-Theoretic Generalization Bounds from Supersamples

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

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 62 references that are in the map.
- First posted on arXiv 5 Feb 2023.

## Builds on (most cited first, 30 of 32)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [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)
- [Three Factors Influencing Minima in SGD](https://mlsanity.com/paper/1711.04623/) (2017)
- [Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysis](https://mlsanity.com/paper/1702.03849/) (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)
- [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)
- [Chaining Mutual Information and Tightening Generalization Bounds](https://mlsanity.com/paper/1806.03803/) (2018)
- [Information-theoretic generalization bounds for black-box learning algorithms](https://mlsanity.com/paper/2110.01584/) (2021)
- [Generalization Bounds via Information Density and Conditional Information Density](https://mlsanity.com/paper/2005.08044/) (2020)
- [Tighter expected generalization error bounds via Wasserstein distance](https://mlsanity.com/paper/2101.09315/) (2021)
- [PAC-Bayes, MAC-Bayes and Conditional Mutual Information: Fast rate bounds that handle general VC classes](https://mlsanity.com/paper/2106.09683/) (2021)
- [On the Generalization of Models Trained with SGD: Information-Theoretic Bounds and Implications](https://mlsanity.com/paper/2110.03128/) (2021)
- [Individually Conditional Individual Mutual Information Bound on Generalization Error](https://mlsanity.com/paper/2012.09922/) (2020)
- [Towards a Unified Information-Theoretic Framework for Generalization](https://mlsanity.com/paper/2111.05275/) (2021)
- [On Random Subset Generalization Error Bounds and the Stochastic Gradient Langevin Dynamics Algorithm](https://mlsanity.com/paper/2010.10994/) (2020)
- [A New Family of Generalization Bounds Using Samplewise Evaluated CMI](https://mlsanity.com/paper/2210.06422/) (2022)
- [Information-theoretic analysis for transfer learning](https://mlsanity.com/paper/2005.08697/) (2020)
- [Fast-rate PAC-Bayes Generalization Bounds via Shifted Rademacher Processes](https://mlsanity.com/paper/1908.07585/) (2019)
- [Limitations of Information-Theoretic Generalization Bounds for Gradient Descent Methods in Stochastic Convex Optimization](https://mlsanity.com/paper/2212.13556/) (2022)
- [Understanding Generalization via Leave-One-Out Conditional Mutual Information](https://mlsanity.com/paper/2206.14800/) (2022)
- [Information-Theoretic Analysis of Unsupervised Domain Adaptation](https://mlsanity.com/paper/2210.00706/) (2022)
- [Information-Theoretic Characterization of the Generalization Error for Iterative Semi-Supervised Learning](https://mlsanity.com/paper/2110.00926/) (2021)
- [Evaluated CMI Bounds for Meta Learning: Tightness and Expressiveness](https://mlsanity.com/paper/2210.06511/) (2022)
- [Two Facets of SDE Under an Information-Theoretic Lens: Generalization of SGD via Training Trajectories and via Terminal States](https://mlsanity.com/paper/2211.10691/) (2022)

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

- [Fantastic Generalization Measures are Nowhere to be Found](https://mlsanity.com/paper/2309.13658/) (2023)
- [Time-Independent Information-Theoretic Generalization Bounds for SGLD](https://mlsanity.com/paper/2311.01046/) (2023)
- [Information-theoretic Generalization Analysis for Expected Calibration Error](https://mlsanity.com/paper/2405.15709/) (2024)
- [Sample-Conditioned Hypothesis Stability Sharpens Information-Theoretic Generalization Bounds](https://mlsanity.com/paper/2310.20102/) (2023)
- [On f-Divergence Principled Domain Adaptation: An Improved Framework](https://mlsanity.com/paper/2402.01887/) (2024)
- [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)
- [How Does Distribution Matching Help Domain Generalization: An Information-theoretic Analysis](https://mlsanity.com/paper/2406.09745/) (2024)
- [Generalization in VAE and Diffusion Models: A Unified Information-Theoretic Analysis](https://mlsanity.com/paper/2506.00849/) (2025)
- [Fairness Overfitting in Machine Learning: An Information-Theoretic Perspective](https://mlsanity.com/paper/2506.07861/) (2025)
- [Information-Theoretic Generalization Bounds for Transductive Learning and its Applications](https://mlsanity.com/paper/2311.04561/) (2023)
- [Class-wise Generalization Error: an Information-Theoretic Analysis](https://mlsanity.com/paper/2401.02904/) (2024)
- [Generalization in Federated Learning: A Conditional Mutual Information Framework](https://mlsanity.com/paper/2503.04091/) (2025)
- [Information-Theoretic Generalization Bounds of Replay-based Continual Learning](https://mlsanity.com/paper/2507.12043/) (2025)
- [Leveraging Flatness to Improve Information-Theoretic Generalization Bounds for SGD](https://mlsanity.com/paper/2601.01465/) (2026)
- [Which Algorithms Have Tight Generalization Bounds?](https://mlsanity.com/paper/2410.01969/) (2024)
- [Information-theoretic Generalization Analysis for VQ-VAEs: A Role of Latent Variables](https://mlsanity.com/paper/2505.19470/) (2025)
- [When Do Early-Exit Networks Generalize? A PAC-Bayesian Theory of Adaptive Depth](https://mlsanity.com/paper/2604.15764/) (2026)
- [Information-Theoretic Generalization Bounds for Sequential Decision Making](https://mlsanity.com/paper/2605.12190/) (2026)
- [Towards the Connection between Activation Sparsity and Flat Minima](https://mlsanity.com/paper/2605.25612/) (2026)
- [An Accuracy-Information Tradeoff for Loss-Difference Conditional Mutual Information](https://mlsanity.com/paper/2610.09206/) (2026)

## Abstract (arXiv)

In this work, we present a variety of novel information-theoretic generalization bounds for learning algorithms, from the supersample setting of Steinke & Zakynthinou (2020)-the setting of the "conditional mutual information" framework. Our development exploits projecting the loss pair (obtained from a training instance and a testing instance) down to a single number and correlating loss values with a Rademacher sequence (and its shifted variants). The presented bounds include square-root bounds, fast-rate bounds, including those based on variance and sharpness, and bounds for interpolating algorithms etc. We show theoretically or empirically that these bounds are tighter than all information-theoretic bounds known to date on the same supersample setting.