# Chaining Mutual Information and Tightening Generalization Bounds

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

## Key facts

- Cited by 65 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Jun 2018.

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

- [User-friendly introduction to PAC-Bayes bounds](https://mlsanity.com/paper/2110.11216/) (2021)
- [Information-Theoretic Generalization Bounds for Stochastic Gradient Descent](https://mlsanity.com/paper/2102.00931/) (2021)
- [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)
- [Generalization Bounds using Lower Tail Exponents in Stochastic Optimizers](https://mlsanity.com/paper/2108.00781/) (2021)
- [Knowledge Overshadowing Causes Amalgamated Hallucination in Large Language Models](https://mlsanity.com/paper/2407.08039/) (2024)
- [Fractal Structure and Generalization Properties of Stochastic Optimization Algorithms](https://mlsanity.com/paper/2106.04881/) (2021)
- [Tighter Information-Theoretic Generalization Bounds from Supersamples](https://mlsanity.com/paper/2302.02432/) (2023)
- [An Information-theoretical Approach to Semi-supervised Learning under Covariate-shift](https://mlsanity.com/paper/2202.12123/) (2022)
- [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)
- [Generalization Bounds with Data-dependent Fractal Dimensions](https://mlsanity.com/paper/2302.02766/) (2023)
- [Characterizing and Understanding the Generalization Error of Transfer Learning with Gibbs Algorithm](https://mlsanity.com/paper/2111.01635/) (2021)
- [Generalization Error Bounds for Deep Neural Networks Trained by SGD](https://mlsanity.com/paper/2206.03299/) (2022)
- [Empirical Risk Minimization with Relative Entropy Regularization](https://mlsanity.com/paper/2211.06617/) (2022)
- [Information-Theoretic Bounds on the Moments of the Generalization Error of Learning Algorithms](https://mlsanity.com/paper/2102.02016/) (2021)
- [Tighter Expected Generalization Error Bounds via Convexity of Information Measures](https://mlsanity.com/paper/2202.12150/) (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)
- [Rate-Distortion Analysis of Minimum Excess Risk in Bayesian Learning](https://mlsanity.com/paper/2105.04180/) (2021)
- [Chained Generalisation Bounds](https://mlsanity.com/paper/2203.00977/) (2022)
- [On the Validation of Gibbs Algorithms: Training Datasets, Test Datasets and their Aggregation](https://mlsanity.com/paper/2306.12380/) (2023)
- [Information-Theoretic Generalization Bounds for Deep Neural Networks](https://mlsanity.com/paper/2404.03176/) (2024)
- [Improved Information Theoretic Generalization Bounds for Distributed and Federated Learning](https://mlsanity.com/paper/2202.02423/) (2022)
- [Empirical Risk Minimization with Relative Entropy Regularization: Optimality and Sensitivity Analysis](https://mlsanity.com/paper/2202.04385/) (2022)
- [Towards Generalizable Graph Contrastive Learning: An Information Theory Perspective](https://mlsanity.com/paper/2211.10929/) (2022)
- [No Free Prune: Information-Theoretic Barriers to Pruning at Initialization](https://mlsanity.com/paper/2402.01089/) (2024)
- [f-divergences and their applications in lossy compression and bounding generalization error](https://mlsanity.com/paper/2206.11042/) (2022)
- [Generalization Analysis of Machine Learning Algorithms via the Worst-Case Data-Generating Probability Measure](https://mlsanity.com/paper/2312.12236/) (2023)

## Abstract (arXiv)

Bounding the generalization error of learning algorithms has a long history, which yet falls short in explaining various generalization successes including those of deep learning. Two important difficulties are (i) exploiting the dependencies between the hypotheses, (ii) exploiting the dependence between the algorithm's input and output. Progress on the first point was made with the chaining method, originating from the work of Kolmogorov, and used in the VC-dimension bound. More recently, progress on the second point was made with the mutual information method by Russo and Zou '15. Yet, these two methods are currently disjoint. In this paper, we introduce a technique to combine the chaining and mutual information methods, to obtain a generalization bound that is both algorithm-dependent and that exploits the dependencies between the hypotheses. We provide an example in which our bound significantly outperforms both the chaining and the mutual information bounds. As a corollary, we tighten Dudley's inequality when the learning algorithm chooses its output from a small subset of hypotheses with high probability.