mlsanityData to 7 Oct 2026

Formal limitations of sample-wise information-theoretic generalization bounds

arXiv 2205.06915 ↗First posted 13 May 2022cs.LG stat.MLcited by 3

Not on the map. Why?

Abstract (arXiv)

Some of the tightest information-theoretic generalization bounds depend on the average information between the learned hypothesis and a single training example. However, these sample-wise bounds were derived only for expected generalization gap. We show that even for expected squared generalization gap no such sample-wise information-theoretic bounds exist. The same is true for PAC-Bayes and single-draw bounds. Remarkably, PAC-Bayes, single-draw and expected squared generalization gap bounds that depend on information in pairs of examples exist.

Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Builds on 20 of its 29 references that are in the map. First posted on arXiv 13 May 2022.

Builds on

20 of 29 references.

References · 20

  1. 2016Understanding deep learning requires rethinking generalizationcited by 1,657
  2. 2017Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Datacited by 527
  3. 2019Fantastic Generalization Measures and Where to Find Themcited by 507
  4. 2017Information-theoretic analysis of generalization capability of learning algorithmscited by 299
  5. 2021User-friendly introduction to PAC-Bayes boundscited by 234
  6. 2020Reasoning About Generalization via Conditional Mutual Informationcited by 145
  7. 2019Information-Theoretic Generalization Bounds for SGLD via Data-Dependent Estimatescited by 118
  8. 2019Tightening Mutual Information Based Bounds on Generalization Errorcited by 117
  9. 2020Tighter risk certificates for neural networkscited by 112
  10. 2020Sharpened Generalization Bounds based on Conditional Mutual Information and an Application to Noisy, Iterative Algorithmscited by 89
  11. 2020In Search of Robust Measures of Generalizationcited by 79
  12. 2020PAC-Bayes Analysis Beyond the Usual Boundscited by 63
8 more
  1. 2021Information-theoretic generalization bounds for black-box learning algorithmscited by 49
  2. 2019Generalization Error Bounds Via R'enyi-, f-Divergences and Maximal Leakagecited by 48
  3. 2020Generalization Bounds via Information Density and Conditional Information Densitycited by 43
  4. 2021Tighter expected generalization error bounds via Wasserstein distancecited by 43
  5. 2020Individually Conditional Individual Mutual Information Bound on Generalization Errorcited by 30
  6. 2020On Random Subset Generalization Error Bounds and the Stochastic Gradient Langevin Dynamics Algorithmcited by 28
  7. 2020Jensen-Shannon Information Based Characterization of the Generalization Error of Learning Algorithmscited by 19
  8. 2021Information-Theoretic Bounds on the Moments of the Generalization Error of Learning Algorithmscited by 12

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 2; 2023: 0; 2024: 0; 2025: 0; 2026: 1.

3 papers.

  1. 2022A New Family of Generalization Bounds Using Samplewise Evaluated CMIcited by 28
  2. 2022Limitations of Information-Theoretic Generalization Bounds for Gradient Descent Methods in Stochastic Convex Optimizationcited by 18
  3. 2026Block-Sample MAC-Bayes Generalization Boundscited by 0