# Individually Conditional Individual Mutual Information Bound on Generalization Error

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

## Key facts

- Cited by 30 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Dec 2020.

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

- [Tighter expected generalization error bounds via Wasserstein distance](https://mlsanity.com/paper/2101.09315/) (2021)
- [On the Generalization of Models Trained with SGD: Information-Theoretic Bounds and Implications](https://mlsanity.com/paper/2110.03128/) (2021)
- [Towards a Unified Information-Theoretic Framework for Generalization](https://mlsanity.com/paper/2111.05275/) (2021)
- [A New Family of Generalization Bounds Using Samplewise Evaluated CMI](https://mlsanity.com/paper/2210.06422/) (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)
- [Information Theoretic Lower Bounds for Information Theoretic Upper Bounds](https://mlsanity.com/paper/2302.04925/) (2023)
- [Understanding Generalization via Leave-One-Out Conditional Mutual Information](https://mlsanity.com/paper/2206.14800/) (2022)
- [Generalization Bounds for Noisy Iterative Algorithms Using Properties of Additive Noise Channels](https://mlsanity.com/paper/2102.02976/) (2021)
- [Information Complexity of Stochastic Convex Optimization: Applications to Generalization and Memorization](https://mlsanity.com/paper/2402.09327/) (2024)
- [Tighter Expected Generalization Error Bounds via Convexity of Information Measures](https://mlsanity.com/paper/2202.12150/) (2022)
- [Data-dependent Generalization Bounds via Variable-Size Compressibility](https://mlsanity.com/paper/2303.05369/) (2023)
- [Stability Based Generalization Bounds for Exponential Family Langevin Dynamics](https://mlsanity.com/paper/2201.03064/) (2022)
- [Fast Rate Generalization Error Bounds: Variations on a Theme](https://mlsanity.com/paper/2205.03131/) (2022)
- [Learning Algorithm Generalization Error Bounds via Auxiliary Distributions](https://mlsanity.com/paper/2210.00483/) (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)
- [Fast Rate Information-theoretic Bounds on Generalization Errors](https://mlsanity.com/paper/2303.14658/) (2023)
- [Recognizable Information Bottleneck](https://mlsanity.com/paper/2304.14618/) (2023)
- [Exactly Tight Information-Theoretic Generalization Error Bound for the Quadratic Gaussian Problem](https://mlsanity.com/paper/2305.00876/) (2023)
- [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)
- [An Information-Theoretic Framework for Out-of-Distribution Generalization with Applications to Stochastic Gradient Langevin Dynamics](https://mlsanity.com/paper/2403.19895/) (2024)
- [Fairness Overfitting in Machine Learning: An Information-Theoretic Perspective](https://mlsanity.com/paper/2506.07861/) (2025)
- [Class-wise Generalization Error: an Information-Theoretic Analysis](https://mlsanity.com/paper/2401.02904/) (2024)
- [Generalization Guarantees for Representation Learning via Data-Dependent Gaussian Mixture Priors](https://mlsanity.com/paper/2502.15540/) (2025)
- [Multiview Representation Learning via Distributed Joint Latent Space Structuring](https://mlsanity.com/paper/2504.18455/) (2025)
- [Tighter Learning Guarantees on Digital Computers via Concentration of Measure on Finite Spaces](https://mlsanity.com/paper/2402.05576/) (2024)
- [Error Bounds of Supervised Classification from Information-Theoretic Perspective](https://mlsanity.com/paper/2406.04567/) (2024)
- [An Information-Theoretic Analysis of OOD Generalization in Meta-Reinforcement Learning](https://mlsanity.com/paper/2510.23448/) (2025)

## Abstract (arXiv)

We propose a new information-theoretic bound on generalization error based on a combination of the error decomposition technique of Bu et al. and the conditional mutual information (CMI) construction of Steinke and Zakynthinou. In a previous work, Haghifam et al. proposed a different bound combining the two aforementioned techniques, which we refer to as the conditional individual mutual information (CIMI) bound. However, in a simple Gaussian setting, both the CMI and the CIMI bounds are order-wise worse than that by Bu et al.. This observation motivated us to propose the new bound, which overcomes this issue by reducing the conditioning terms in the conditional mutual information. In the process of establishing this bound, a conditional decoupling lemma is established, which also leads to a meaningful dichotomy and comparison among these information-theoretic bounds.