mlsanityData to 7 Oct 2026

Sharpened Generalization Bounds based on Conditional Mutual Information and an Application to Noisy, Iterative Algorithms

arXiv 2004.12983 ↗First posted 27 Apr 2020stat.ML cs.IT cs.LGcited by 89

Not on the map. Why?

Abstract (arXiv)

The information-theoretic framework of Russo and J. Zou (2016) and Xu and Raginsky (2017) provides bounds on the generalization error of a learning algorithm in terms of the mutual information between the algorithm's output and the training sample. In this work, we study the proposal, by Steinke and Zakynthinou (2020), to reason about the generalization error of a learning algorithm by introducing a super sample that contains the training sample as a random subset and computing mutual information conditional on the super sample. We first show that these new bounds based on the conditional mutual information are tighter than those based on the unconditional mutual information. We then introduce yet tighter bounds, building on the "individual sample" idea of Bu, S. Zou, and Veeravalli (2019) and the "data dependent" ideas of Negrea et al. (2019), using disintegrated mutual information. Finally, we apply these bounds to the study of Langevin dynamics algorithm, showing that conditioning on the super sample allows us to exploit information in the optimization trajectory to obtain tighter bounds based on hypothesis tests.

Key facts. Cited by 89 papers in the map (data through 7 Oct 2026). First posted on arXiv 27 Apr 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 20; 2022: 27; 2023: 15; 2024: 8; 2025: 14; 2026: 5.

89 papers.

Sort:

By area:

  1. 2021Information-Theoretic Generalization Bounds for Stochastic Gradient Descentcited by 84
  2. 2025How much do language models memorize?cited by 53
  3. 2021Information-theoretic generalization bounds for black-box learning algorithmscited by 49
  4. 2021Tighter expected generalization error bounds via Wasserstein distancecited by 43
  5. 2021PAC-Bayes, MAC-Bayes and Conditional Mutual Information: Fast rate bounds that handle general VC classescited by 31
  6. 2021On the Generalization of Models Trained with SGD: Information-Theoretic Bounds and Implicationscited by 31
  7. 2021Towards a Unified Information-Theoretic Framework for Generalizationcited by 29
  8. 2022A New Family of Generalization Bounds Using Samplewise Evaluated CMIcited by 28
  9. 2021Generalization Bounds using Lower Tail Exponents in Stochastic Optimizerscited by 27
  10. 2021Time-independent Generalization Bounds for SGLD in Non-convex Settingscited by 27
  11. 2022Generalization Bounds via Convex Analysiscited by 27
  12. 2023Explaining Generalization Power of a DNN Using Interactive Conceptscited by 25
38 more
  1. 2022Rate-Distortion Theoretic Generalization Bounds for Stochastic Learning Algorithmscited by 22
  2. 2023Tighter Information-Theoretic Generalization Bounds from Supersamplescited by 21
  3. 2022An Information-theoretical Approach to Semi-supervised Learning under Covariate-shiftcited by 18
  4. 2022Limitations of Information-Theoretic Generalization Bounds for Gradient Descent Methods in Stochastic Convex Optimizationcited by 18
  5. 2022Understanding Generalization via Leave-One-Out Conditional Mutual Informationcited by 16
  6. 2023Information Theoretic Lower Bounds for Information Theoretic Upper Boundscited by 16
  7. 2021Generalization Bounds for Noisy Iterative Algorithms Using Properties of Additive Noise Channelscited by 15
  8. 2022Information-Theoretic Analysis of Unsupervised Domain Adaptationcited by 15
  9. 2021Information Complexity and Generalization Boundscited by 14
  10. 2021Characterizing and Understanding the Generalization Error of Transfer Learning with Gibbs Algorithmcited by 14
  11. 2022Generalization Error Bounds for Deep Neural Networks Trained by SGDcited by 14
  12. 2022Empirical Risk Minimization with Relative Entropy Regularizationcited by 13
  13. 2024Information Complexity of Stochastic Convex Optimization: Applications to Generalization and Memorizationcited by 12
  14. 2021Information-Theoretic Characterization of the Generalization Error for Iterative Semi-Supervised Learningcited by 11
  15. 2022Tighter Expected Generalization Error Bounds via Convexity of Information Measurescited by 11
  16. 2022On the Generalization for Transfer Learning: An Information-Theoretic Analysiscited by 11
  17. 2022Evaluated CMI Bounds for Meta Learning: Tightness and Expressivenesscited by 11
  18. 2022Two Facets of SDE Under an Information-Theoretic Lens: Generalization of SGD via Training Trajectories and via Terminal Statescited by 11
  19. 2021Rate-Distortion Analysis of Minimum Excess Risk in Bayesian Learningcited by 10
  20. 2022Chained Generalisation Boundscited by 10
  21. 2022What You See is What You Get: Principled Deep Learning via Distributional Generalizationcited by 10
  22. 2023On the Validation of Gibbs Algorithms: Training Datasets, Test Datasets and their Aggregationcited by 10
  23. 2024Information-Theoretic Generalization Bounds for Deep Neural Networkscited by 10
  24. 2021Disparity Between Batches as a Signal for Early Stoppingcited by 9
  25. 2022Information bottleneck theory of high-dimensional regression: relevancy, efficiency and optimalitycited by 9
  26. 2024Uniform Generalization Bounds on Data-Dependent Hypothesis Sets via PAC-Bayesian Theory on Random Setscited by 9
  27. 2022Stability Based Generalization Bounds for Exponential Family Langevin Dynamicscited by 8
  28. 2022On Leave-One-Out Conditional Mutual Information For Generalizationcited by 8
  29. 2022Weight Expansion: A New Perspective on Dropout and Generalizationcited by 6
  30. 2022Fast Rate Generalization Error Bounds: Variations on a Themecited by 6
  31. 2022Learning Algorithm Generalization Error Bounds via Auxiliary Distributionscited by 6
  32. 2022On the Importance of Gradient Norm in PAC-Bayesian Boundscited by 6
  33. 2023A unified framework for information-theoretic generalization boundscited by 6
  34. 2021Towards Understanding Generalization via Decomposing Excess Risk Dynamicscited by 5
  35. 2022Information-Theoretic Analysis of Minimax Excess Riskcited by 5
  36. 2022Generalization Bounds for Gradient Methods via Discrete and Continuous Priorcited by 5
  37. 2022How Does Pseudo-Labeling Affect the Generalization Error of the Semi-Supervised Gibbs Algorithm?cited by 5
  38. 2023Fast Rate Information-theoretic Bounds on Generalization Errorscited by 5

50 most cited of 89 All 89 (JSON)