# Understanding Generalization via Leave-One-Out Conditional Mutual Information

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 40 references that are in the map.
- First posted on arXiv 29 Jun 2022.

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

- [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)
- [Sharpened Generalization Bounds based on Conditional Mutual Information and an Application to Noisy, Iterative Algorithms](https://mlsanity.com/paper/2004.12983/) (2020)
- [Generalization in Adaptive Data Analysis and Holdout Reuse](https://mlsanity.com/paper/1506.02629/) (2015)
- [In Search of Robust Measures of Generalization](https://mlsanity.com/paper/2010.11924/) (2020)
- [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)
- [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)
- [Refined Error Bounds for Several Learning Algorithms](https://mlsanity.com/paper/1512.07146/) (2015)
- [A Limitation of the PAC-Bayes Framework](https://mlsanity.com/paper/2006.13508/) (2020)
- [Jensen-Shannon Information Based Characterization of the Generalization Error of Learning Algorithms](https://mlsanity.com/paper/2010.12664/) (2020)
- [Chained Generalisation Bounds](https://mlsanity.com/paper/2203.00977/) (2022)
- [A Direct Sum Result for the Information Complexity of Learning](https://mlsanity.com/paper/1804.05474/) (2018)
- [Information-Theoretic Analysis of Minimax Excess Risk](https://mlsanity.com/paper/2202.07537/) (2022)

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

- [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)
- [Information Complexity of Stochastic Convex Optimization: Applications to Generalization and Memorization](https://mlsanity.com/paper/2402.09327/) (2024)
- [The One-Inclusion Graph Algorithm is not Always Optimal](https://mlsanity.com/paper/2212.09270/) (2022)
- [On Leave-One-Out Conditional Mutual Information For Generalization](https://mlsanity.com/paper/2207.00581/) (2022)
- [Sample-Conditioned Hypothesis Stability Sharpens Information-Theoretic Generalization Bounds](https://mlsanity.com/paper/2310.20102/) (2023)
- [Comparing Comparators in Generalization Bounds](https://mlsanity.com/paper/2310.10534/) (2023)
- [Exactly Tight Information-Theoretic Generalization Error Bound for the Quadratic Gaussian Problem](https://mlsanity.com/paper/2305.00876/) (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)
- [Generalization in VAE and Diffusion Models: A Unified Information-Theoretic Analysis](https://mlsanity.com/paper/2506.00849/) (2025)
- [Information-Theoretic Generalization Bounds for Transductive Learning and its Applications](https://mlsanity.com/paper/2311.04561/) (2023)
- [Which Algorithms Have Tight Generalization Bounds?](https://mlsanity.com/paper/2410.01969/) (2024)
- [Generalization Bounds of Stochastic Gradient Descent in Homogeneous Neural Networks](https://mlsanity.com/paper/2602.22936/) (2026)
- [On Kernel Eigen-alignments of KRR: Reconstruction and Generalization](https://mlsanity.com/paper/2605.15240/) (2026)

## Abstract (arXiv)

We study the mutual information between (certain summaries of) the output of a learning algorithm and its n training data, conditional on a supersample of n+1 i.i.d. data from which the training data is chosen at random without replacement. These leave-one-out variants of the conditional mutual information (CMI) of an algorithm (Steinke and Zakynthinou, 2020) are also seen to control the mean generalization error of learning algorithms with bounded loss functions. For learning algorithms achieving zero empirical risk under 0-1 loss (i.e., interpolating algorithms), we provide an explicit connection between leave-one-out CMI and the classical leave-one-out error estimate of the risk. Using this connection, we obtain upper and lower bounds on risk in terms of the (evaluated) leave-one-out CMI. When the limiting risk is constant or decays polynomially, the bounds converge to within a constant factor of two. As an application, we analyze the population risk of the one-inclusion graph algorithm, a general-purpose transductive learning algorithm for VC classes in the realizable setting. Using leave-one-out CMI, we match the optimal bound for learning VC classes in the realizable setting, answering an open challenge raised by Steinke and Zakynthinou (2020). Finally, in order to understand the role of leave-one-out CMI in studying generalization, we place leave-one-out CMI in a hierarchy of measures, with a novel unconditional mutual information at the root. For 0-1 loss and interpolating learning algorithms, this mutual information is observed to be precisely the risk.