mlsanityData to 14 Oct 2026

Chaining Mutual Information and Tightening Generalization Bounds

arXiv 1806.03803 ↗First posted 11 Jun 2018cs.LG cs.IT math.ITcited by 65

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 14; 2022: 20; 2023: 9; 2024: 9; 2025: 4; 2026: 9.

65 papers.

Sort:

By area:

  1. 2021User-friendly introduction to PAC-Bayes boundscited by 239
  2. 2021Information-Theoretic Generalization Bounds for Stochastic Gradient Descentcited by 84
  3. 2021Tighter expected generalization error bounds via Wasserstein distancecited by 43
  4. 2021On the Generalization of Models Trained with SGD: Information-Theoretic Bounds and Implicationscited by 31
  5. 2021Towards a Unified Information-Theoretic Framework for Generalizationcited by 30
  6. 2022A New Family of Generalization Bounds Using Samplewise Evaluated CMIcited by 28
  7. 2021Generalization Bounds using Lower Tail Exponents in Stochastic Optimizerscited by 27
  8. 2024Knowledge Overshadowing Causes Amalgamated Hallucination in Large Language Modelscited by 25
  9. 2021Fractal Structure and Generalization Properties of Stochastic Optimization Algorithmscited by 23
  10. 2023Tighter Information-Theoretic Generalization Bounds from Supersamplescited by 22
  11. 2022An Information-theoretical Approach to Semi-supervised Learning under Covariate-shiftcited by 18
  12. 2022Understanding Generalization via Leave-One-Out Conditional Mutual Informationcited by 16
38 more
  1. 2021Generalization Bounds for Noisy Iterative Algorithms Using Properties of Additive Noise Channelscited by 15
  2. 2023Generalization Bounds with Data-dependent Fractal Dimensionscited by 15
  3. 2021Characterizing and Understanding the Generalization Error of Transfer Learning with Gibbs Algorithmcited by 14
  4. 2022Generalization Error Bounds for Deep Neural Networks Trained by SGDcited by 14
  5. 2022Empirical Risk Minimization with Relative Entropy Regularizationcited by 13
  6. 2021Information-Theoretic Bounds on the Moments of the Generalization Error of Learning Algorithmscited by 12
  7. 2022Tighter Expected Generalization Error Bounds via Convexity of Information Measurescited by 11
  8. 2022Two Facets of SDE Under an Information-Theoretic Lens: Generalization of SGD via Training Trajectories and via Terminal Statescited by 11
  9. 2021Rate-Distortion Analysis of Minimum Excess Risk in Bayesian Learningcited by 10
  10. 2022Chained Generalisation Boundscited by 10
  11. 2023On the Validation of Gibbs Algorithms: Training Datasets, Test Datasets and their Aggregationcited by 10
  12. 2024Information-Theoretic Generalization Bounds for Deep Neural Networkscited by 10
  13. 2022Improved Information Theoretic Generalization Bounds for Distributed and Federated Learningcited by 8
  14. 2022Empirical Risk Minimization with Relative Entropy Regularization: Optimality and Sensitivity Analysiscited by 8
  15. 2022Towards Generalizable Graph Contrastive Learning: An Information Theory Perspectivecited by 8
  16. 2024No Free Prune: Information-Theoretic Barriers to Pruning at Initializationcited by 8
  17. 2022f-divergences and their applications in lossy compression and bounding generalization errorcited by 7
  18. 2023Generalization Analysis of Machine Learning Algorithms via the Worst-Case Data-Generating Probability Measurecited by 7
  19. 2022Fast Rate Generalization Error Bounds: Variations on a Themecited by 6
  20. 2022Learning Algorithm Generalization Error Bounds via Auxiliary Distributionscited by 6
  21. 2023A unified framework for information-theoretic generalization boundscited by 6
  22. 2023Sample-Conditioned Hypothesis Stability Sharpens Information-Theoretic Generalization Boundscited by 6
  23. 2022Information-Theoretic Analysis of Minimax Excess Riskcited by 5
  24. 2022How Does Pseudo-Labeling Affect the Generalization Error of the Semi-Supervised Gibbs Algorithm?cited by 5
  25. 2023Fast Rate Information-theoretic Bounds on Generalization Errorscited by 5
  26. 2024The Method of Gaps: Exact Expressions for the Generalization Error of Supervised Learning Algorithmscited by 5
  27. 2022DECONET: an Unfolding Network for Analysis-based Compressed Sensing with Generalization Error Boundscited by 4
  28. 2023Exactly Tight Information-Theoretic Generalization Error Bound for the Quadratic Gaussian Problemcited by 4
  29. 2024Enhancing In-Context Learning Performance with just SVD-Based Weight Pruning: A Theoretical Perspectivecited by 4
  30. 2024Generalization and Robustness of the Tilted Empirical Riskcited by 4
  31. 2024Generalization Bounds via Conditional f-Informationcited by 4
  32. 2025FMMI: Flow Matching Mutual Information Estimationcited by 4
  33. 2021Characterizing the Generalization Error of Gibbs Algorithm with Symmetrized KL informationcited by 3
  34. 2026Sharper Generalization Bounds for Transformercited by 3
  35. 2022An Entropy-Based Model for Hierarchical Learningcited by 2
  36. 2023Information-Theoretic Generalization Bounds for Transductive Learning and its Applicationscited by 2
  37. 2024Multi-Group Proportional Representation in Retrievalcited by 2
  38. 2025Beyond Real Data: Synthetic Data through the Lens of Regularizationcited by 2

50 most cited of 65 All 65 (JSON)