mlsanityData to 14 Oct 2026

Towards a Unified Information-Theoretic Framework for Generalization

arXiv 2111.05275 ↗First posted 9 Nov 2021cs.IT cs.LG math.ITcited by 30

Not on the map. Why?

Abstract (arXiv)

In this work, we investigate the expressiveness of the "conditional mutual information" (CMI) framework of Steinke and Zakynthinou (2020) and the prospect of using it to provide a unified framework for proving generalization bounds in the realizable setting. We first demonstrate that one can use this framework to express non-trivial (but sub-optimal) bounds for any learning algorithm that outputs hypotheses from a class of bounded VC dimension. We prove that the CMI framework yields the optimal bound on the expected risk of Support Vector Machines (SVMs) for learning halfspaces. This result is an application of our general result showing that stable compression schemes Bousquet al. (2020) of size k have uniformly bounded CMI of order O(k). We further show that an inherent limitation of proper learning of VC classes contradicts the existence of a proper learner with constant CMI, and it implies a negative resolution to an open problem of Steinke and Zakynthinou (2020). We further study the CMI of empirical risk minimizers (ERMs) of class H and show that it is possible to output all consistent classifiers (version space) with bounded CMI if and only if H has a bounded star number (Hanneke and Yang (2015)). Moreover, we prove a general reduction showing that "leave-one-out" analysis is expressible via the CMI framework. As a corollary we investigate the CMI of the one-inclusion-graph algorithm proposed by Haussler et al. (1994). More generally, we show that the CMI framework is universal in the sense that for every consistent algorithm and data distribution, the expected risk vanishes as the number of samples diverges if and only if its evaluated CMI has sublinear growth with the number of samples.

Key facts. Cited by 30 papers in the map (data through 14 Oct 2026). Builds on 21 of its 45 references that are in the map. First posted on arXiv 9 Nov 2021.

Builds on

21 of 45 references.

References · 21

  1. 2017Information-theoretic analysis of generalization capability of learning algorithmscited by 303
  2. 2020Reasoning About Generalization via Conditional Mutual Informationcited by 147
  3. 2019Information-Theoretic Generalization Bounds for SGLD via Data-Dependent Estimatescited by 119
  4. 2019Tightening Mutual Information Based Bounds on Generalization Errorcited by 117
  5. 2015How much does your data exploration overfit? Controlling bias via information usagecited by 95
  6. 2020Sharpened Generalization Bounds based on Conditional Mutual Information and an Application to Noisy, Iterative Algorithmscited by 89
  7. 2021Information-Theoretic Generalization Bounds for Stochastic Gradient Descentcited by 84
  8. 2018Generalization Error Bounds for Noisy, Iterative Algorithmscited by 82
  9. 2015The Optimal Sample Complexity of PAC Learningcited by 72
  10. 2018Chaining Mutual Information and Tightening Generalization Boundscited by 65
  11. 2014Minimax Analysis of Active Learningcited by 61
  12. 2020Proper Learning, Helly Number, and an Optimal SVM Boundcited by 53
9 more
  1. 2015Sample compression schemes for VC classescited by 47
  2. 2020Generalization Bounds via Information Density and Conditional Information Densitycited by 43
  3. 2020Stable Sample Compression Schemes: New Applications and an Optimal SVM Margin Boundcited by 32
  4. 2020Individually Conditional Individual Mutual Information Bound on Generalization Errorcited by 30
  5. 2020On Random Subset Generalization Error Bounds and the Stochastic Gradient Langevin Dynamics Algorithmcited by 28
  6. 2015Refined Error Bounds for Several Learning Algorithmscited by 25
  7. 2020A Limitation of the PAC-Bayes Frameworkcited by 25
  8. 2018A Direct Sum Result for the Information Complexity of Learningcited by 6
  9. 2018Average-Case Information Complexity of Learningcited by 4

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 9; 2023: 12; 2024: 2; 2025: 5; 2026: 2.

30 papers.

Sort:

By area:

  1. 2022A New Family of Generalization Bounds Using Samplewise Evaluated CMIcited by 28
  2. 2022Generalization Bounds via Convex Analysiscited by 27
  3. 2023Explaining Generalization Power of a DNN Using Interactive Conceptscited by 25
  4. 2022Rate-Distortion Theoretic Generalization Bounds for Stochastic Learning Algorithmscited by 22
  5. 2023Tighter Information-Theoretic Generalization Bounds from Supersamplescited by 22
  6. 2022Limitations of Information-Theoretic Generalization Bounds for Gradient Descent Methods in Stochastic Convex Optimizationcited by 19
  7. 2023More PAC-Bayes bounds: From bounded losses, to losses with general tail behaviors, to anytime validitycited by 17
  8. 2022Understanding Generalization via Leave-One-Out Conditional Mutual Informationcited by 16
  9. 2022Rate-Distortion Theoretic Bounds on Generalization Error for Distributed Learningcited by 14
  10. 2023Online-to-PAC Conversions: Generalization Bounds via Regret Analysiscited by 14
  11. 2024Information Complexity of Stochastic Convex Optimization: Applications to Generalization and Memorizationcited by 14
  12. 2023Data-dependent Generalization Bounds via Variable-Size Compressibilitycited by 9
18 more
  1. 2023Bayes meets Bernstein at the Meta Level: an Analysis of Fast Rates in Meta-Learning with PAC-Bayescited by 8
  2. 2022Max-Margin Works while Large Margin Fails: Generalization without Uniform Convergencecited by 6
  3. 2023A unified framework for information-theoretic generalization boundscited by 6
  4. 2023Sample-Conditioned Hypothesis Stability Sharpens Information-Theoretic Generalization Boundscited by 6
  5. 2022Data Models for Dataset Drift Controls in Machine Learning With Optical Imagescited by 5
  6. 2023Local Risk Bounds for Statistical Aggregationcited by 3
  7. 2025Generalization in VAE and Diffusion Models: A Unified Information-Theoretic Analysiscited by 3
  8. 2023Information-Theoretic Generalization Bounds for Transductive Learning and its Applicationscited by 2
  9. 2024Mathematical Formalism for Memory Compression in Selective State Space Modelscited by 2
  10. 2025Revisiting Generalization Power of a DNN in Terms of Symbolic Interactionscited by 2
  11. 2025Generalization Guarantees for Representation Learning via Data-Dependent Gaussian Mixture Priorscited by 2
  12. 2022Black-Box Generalization: Stability of Zeroth-Order Learningcited by 1
  13. 2023Fast and Multiphase Rates for Nearest Neighbor Classifierscited by 1
  14. 2025Multiview Representation Learning via Distributed Joint Latent Space Structuringcited by 1
  15. 2023Mathematical Challenges in Deep Learningcited by 0
  16. 2025An Information-Theoretic Analysis of OOD Generalization in Meta-Reinforcement Learningcited by 0
  17. 2026Tighter Information-Theoretic Generalization Bounds via a Novel Class of Change of Measure Inequalitiescited by 0
  18. 2026An Accuracy-Information Tradeoff for Loss-Difference Conditional Mutual Informationcited by 0