mlsanityData to 14 Oct 2026

Tighter Information-Theoretic Generalization Bounds via a Novel Class of Change of Measure Inequalities

arXiv 2602.07999 ↗First posted 8 Feb 2026cs.IT cs.LG math.ITcited by 0

Not on the map. Why?

Abstract (arXiv)

Change of measure inequalities translate divergences between probability measures into explicit bounds on event probabilities, and play an important role in deriving probabilistic guarantees in learning theory, information theory, and statistics. We propose novel change of measure inequalities via a unified framework based on the data processing inequality, which is surprisingly elementary yet powerful enough to yield novel, tighter inequalities. We provide change of measure inequalities in terms of a broad family of information measures, including f-divergences (with Kullback-Leibler divergence and chi2-divergence as special cases), R'enyi divergence, and α-mutual information (with maximal leakage as a special case). We apply these results to generalization error analysis, PAC-Bayesian theory, differential privacy, and data memorization, obtaining stronger guarantees while recovering best-known results through simplified analyses.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 46 of its 102 references that are in the map. First posted on arXiv 8 Feb 2026.

Builds on

46 of 102 references.

References · 46

  1. 2020Extracting Training Data from Large Language Modelscited by 2,189
  2. 2016Understanding deep learning requires rethinking generalizationcited by 1,674
  3. 2018The Secret Sharer: Evaluating and Testing Unintended Memorization in Neural Networkscited by 864
  4. 2022Quantifying Memorization Across Neural Language Modelscited by 763
  5. 2020What Neural Networks Memorize and Why: Discovering the Long Tail via Influence Estimationcited by 497
  6. 2019Does Learning Require Memorization? A Short Tale about a Long Tailcited by 460
  7. 2017Information-theoretic analysis of generalization capability of learning algorithmscited by 303
  8. 2021User-friendly introduction to PAC-Bayes boundscited by 239
  9. 2020Reasoning About Generalization via Conditional Mutual Informationcited by 147
  10. 2022Reconstructing Training Data from Trained Neural Networkscited by 133
  11. 2019A Primer on PAC-Bayesian Learningcited by 132
  12. 2022Measuring Forgetting of Memorized Training Examplescited by 118
34 more
  1. 2019Tightening Mutual Information Based Bounds on Generalization Errorcited by 117
  2. 2020Tighter risk certificates for neural networkscited by 112
  3. 2020When is Memorization of Irrelevant Training Data Necessary for High-Accuracy Learning?cited by 104
  4. 2014Preserving Statistical Validity in Adaptive Data Analysiscited by 103
  5. 2020Sharpened Generalization Bounds based on Conditional Mutual Information and an Application to Noisy, Iterative Algorithmscited by 89
  6. 2015Algorithmic Stability for Adaptive Data Analysiscited by 88
  7. 2015Generalization in Adaptive Data Analysis and Holdout Reusecited by 83
  8. 2018Generalization Error Bounds for Noisy, Iterative Algorithmscited by 82
  9. 2018Chaining Mutual Information and Tightening Generalization Boundscited by 65
  10. 2021Information-theoretic generalization bounds for black-box learning algorithmscited by 49
  11. 2019Generalization Error Bounds Via R'enyi-, f-Divergences and Maximal Leakagecited by 48
  12. 2020Generalization Bounds via Information Density and Conditional Information Densitycited by 43
  13. 2022Quantum Differential Privacy: An Information Theory Perspectivecited by 32
  14. 2021Towards a Unified Information-Theoretic Framework for Generalizationcited by 30
  15. 2016Max-Information, Differential Privacy, and Post-Selection Hypothesis Testingcited by 27
  16. 2022Non-Vacuous Generalisation Bounds for Shallow Neural Networkscited by 22
  17. 2022Rate-Distortion Theoretic Generalization Bounds for Stochastic Learning Algorithmscited by 22
  18. 2021Local Differential Privacy Is Equivalent to Contraction of Eγ-Divergencecited by 17
  19. 2019Still no free lunches: the price to pay for tighter PAC-Bayes boundscited by 14
  20. 2021Information Complexity and Generalization Boundscited by 14
  21. 2022Tighter Expected Generalization Error Bounds via Convexity of Information Measurescited by 11
  22. 2024Information-Theoretic Generalization Bounds for Deep Neural Networkscited by 10
  23. 2023Data-dependent Generalization Bounds via Variable-Size Compressibilitycited by 9
  24. 2024Universal Exact Compression of Differentially Private Mechanismscited by 8
  25. 2022f-divergences and their applications in lossy compression and bounding generalization errorcited by 7
  26. 2022Learning Algorithm Generalization Error Bounds via Auxiliary Distributionscited by 6
  27. 2023A unified framework for information-theoretic generalization boundscited by 6
  28. 2025Trade-offs in Data Memorization via Strong Data Processing Inequalitiescited by 6
  29. 2020Upper Bounds on the Generalization Error of Private Algorithms for Discrete Datacited by 5
  30. 2024Generalization Bounds via Conditional f-Informationcited by 4
  31. 2023Generalization Error Bounds for Noisy, Iterative Algorithms via Maximal Leakagecited by 2
  32. 2025On Traceability in ℓp Stochastic Convex Optimizationcited by 2
  33. 2025Tighter CMI-Based Generalization Bounds via Stochastic Projection and Quantizationcited by 2
  34. 2025A DPI-PAC-Bayesian Framework for Generalization Boundscited by 1

Built on by

Not cited yet.