mlsanityData to 7 Oct 2026

Sample-Conditioned Hypothesis Stability Sharpens Information-Theoretic Generalization Bounds

arXiv 2310.20102 ↗First posted 31 Oct 2023stat.ML cs.IT cs.LGcited by 5

Not on the map. Why?

Abstract (arXiv)

We present new information-theoretic generalization guarantees through the a novel construction of the "neighboring-hypothesis" matrix and a new family of stability notions termed sample-conditioned hypothesis (SCH) stability. Our approach yields sharper bounds that improve upon previous information-theoretic bounds in various learning scenarios. Notably, these bounds address the limitations of existing information-theoretic bounds in the context of stochastic convex optimization (SCO) problems, as explored in the recent work by Haghifam et al. (2023).

Key facts. Cited by 5 papers in the map (data through 7 Oct 2026). Builds on 44 of its 70 references that are in the map. First posted on arXiv 31 Oct 2023.

Builds on

44 of 70 references.

References · 44

  1. 2016Understanding deep learning requires rethinking generalizationcited by 1,657
  2. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 547
  3. 2019Online Learning: A Modern Introduction Using Convex Optimizationcited by 407
  4. 2017Information-theoretic analysis of generalization capability of learning algorithmscited by 299
  5. 2021User-friendly introduction to PAC-Bayes boundscited by 234
  6. 2020Stability of Stochastic Gradient Descent on Nonsmooth Convex Lossescited by 172
  7. 2020Reasoning About Generalization via Conditional Mutual Informationcited by 145
  8. 2019Information-Theoretic Generalization Bounds for SGLD via Data-Dependent Estimatescited by 118
  9. 2019Tightening Mutual Information Based Bounds on Generalization Errorcited by 117
  10. 2019High probability generalization bounds for uniformly stable algorithms with nearly optimal ratecited by 97
  11. 2019Sharper bounds for uniformly stable algorithmscited by 91
  12. 2020Sharpened Generalization Bounds based on Conditional Mutual Information and an Application to Noisy, Iterative Algorithmscited by 89
32 more
  1. 2021Information-Theoretic Generalization Bounds for Stochastic Gradient Descentcited by 84
  2. 2017Generalization Bounds of SGLD for Non-convex Learning: Two Theoretical Viewpointscited by 82
  3. 2018Generalization Error Bounds for Noisy, Iterative Algorithmscited by 79
  4. 2018Chaining Mutual Information and Tightening Generalization Boundscited by 65
  5. 2019On Generalization Error Bounds of Noisy Gradient Methods for Non-Convex Learningcited by 57
  6. 2018Generalization Bounds for Uniformly Stable Algorithmscited by 56
  7. 2020Proper Learning, Helly Number, and an Optimal SVM Boundcited by 52
  8. 2021Information-theoretic generalization bounds for black-box learning algorithmscited by 49
  9. 2021Tighter expected generalization error bounds via Wasserstein distancecited by 43
  10. 2021Stability and Deviation Optimal Risk Bounds with Convergence Rate O(1/n)cited by 42
  11. 2019PAC-Bayes Un-Expected Bernstein Inequalitycited by 36
  12. 2021PAC-Bayes, MAC-Bayes and Conditional Mutual Information: Fast rate bounds that handle general VC classescited by 31
  13. 2021On the Generalization of Models Trained with SGD: Information-Theoretic Bounds and Implicationscited by 31
  14. 2020Individually Conditional Individual Mutual Information Bound on Generalization Errorcited by 30
  15. 2017A PAC-Bayesian Analysis of Randomized Learning with Application to Stochastic Gradient Descentcited by 29
  16. 2021Towards a Unified Information-Theoretic Framework for Generalizationcited by 29
  17. 2020On Random Subset Generalization Error Bounds and the Stochastic Gradient Langevin Dynamics Algorithmcited by 28
  18. 2022A New Family of Generalization Bounds Using Samplewise Evaluated CMIcited by 28
  19. 2020A Limitation of the PAC-Bayes Frameworkcited by 24
  20. 2019Hypothesis Set Stability and Generalizationcited by 23
  21. 2018PAC-Bayes bounds for stable algorithms with instance-dependent priorscited by 21
  22. 2023Tighter Information-Theoretic Generalization Bounds from Supersamplescited by 21
  23. 2022Limitations of Information-Theoretic Generalization Bounds for Gradient Descent Methods in Stochastic Convex Optimizationcited by 18
  24. 2022Understanding Generalization via Leave-One-Out Conditional Mutual Informationcited by 16
  25. 2023Information Theoretic Lower Bounds for Information Theoretic Upper Boundscited by 16
  26. 2022Information-Theoretic Analysis of Unsupervised Domain Adaptationcited by 15
  27. 2022Two Facets of SDE Under an Information-Theoretic Lens: Generalization of SGD via Training Trajectories and via Terminal Statescited by 11
  28. 2022Stability Based Generalization Bounds for Exponential Family Langevin Dynamicscited by 8
  29. 2022On Leave-One-Out Conditional Mutual Information For Generalizationcited by 8
  30. 2022Fast Rate Generalization Error Bounds: Variations on a Themecited by 6
  31. 2023Fast Rate Information-theoretic Bounds on Generalization Errorscited by 5
  32. 2023Exactly Tight Information-Theoretic Generalization Error Bound for the Quadratic Gaussian Problemcited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 3; 2025: 1; 2026: 1.

5 papers.

  1. 2024Information Complexity of Stochastic Convex Optimization: Applications to Generalization and Memorizationcited by 12
  2. 2024On f-Divergence Principled Domain Adaptation: An Improved Frameworkcited by 6
  3. 2024Generalization Bounds via Conditional f-Informationcited by 3
  4. 2025Generalization in Federated Learning: A Conditional Mutual Information Frameworkcited by 2
  5. 2026Leveraging Flatness to Improve Information-Theoretic Generalization Bounds for SGDcited by 2