mlsanityData to 7 Oct 2026

Rate-Distortion Theoretic Generalization Bounds for Stochastic Learning Algorithms

arXiv 2203.02474 ↗First posted 4 Mar 2022stat.ML cs.IT cs.LGcited by 22

Not on the map. Why?

Abstract (arXiv)

Understanding generalization in modern machine learning settings has been one of the major challenges in statistical learning theory. In this context, recent years have witnessed the development of various generalization bounds suggesting different complexity notions such as the mutual information between the data sample and the algorithm output, compressibility of the hypothesis space, and the fractal dimension of the hypothesis space. While these bounds have illuminated the problem at hand from different angles, their suggested complexity notions might appear seemingly unrelated, thereby restricting their high-level impact. In this study, we prove novel generalization bounds through the lens of rate-distortion theory, and explicitly relate the concepts of mutual information, compressibility, and fractal dimensions in a single mathematical framework. Our approach consists of (i) defining a generalized notion of compressibility by using source coding concepts, and (ii) showing that the `compression error rate' can be linked to the generalization error both in expectation and with high probability. We show that in the `lossless compression' setting, we recover and improve existing mutual information-based bounds, whereas a `lossy compression' scheme allows us to link generalization to the rate-distortion dimension -- a particular notion of fractal dimension. Our results bring a more unified perspective on generalization and open up several future research directions.

Key facts. Cited by 22 papers in the map (data through 7 Oct 2026). Builds on 22 of its 65 references that are in the map. First posted on arXiv 4 Mar 2022.

Builds on

22 of 65 references.

References · 22

  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. 2017A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networkscited by 309
  4. 2018Stronger generalization bounds for deep nets via a compression approachcited by 306
  5. 2017Information-theoretic analysis of generalization capability of learning algorithmscited by 299
  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. 2020Sharpened Generalization Bounds based on Conditional Mutual Information and an Application to Noisy, Iterative Algorithmscited by 89
  10. 2021Intrinsic Dimension, Persistent Homology and Generalization in Neural Networkscited by 70
  11. 2020Hausdorff Dimension, Heavy Tails, and Generalization in Neural Networkscited by 62
  12. 2021Information-theoretic generalization bounds for black-box learning algorithmscited by 49
10 more
  1. 2019Generalization Error Bounds Via R'enyi-, f-Divergences and Maximal Leakagecited by 48
  2. 2019In Defense of Uniform Convergence: Generalization via derandomization with an application to interpolating predictorscited by 44
  3. 2021Heavy Tails in SGD and Compressibility of Overparametrized Neural Networkscited by 44
  4. 2018Data-Dependent Coresets for Compressing Neural Networks with Applications to Generalization Boundscited by 43
  5. 2020Generalization Bounds via Information Density and Conditional Information Densitycited by 43
  6. 2019Compression based bound for non-compressed network: unified generalization error analysis of large compressible deep neural networkcited by 39
  7. 2021Generalization bounds via distillationcited by 33
  8. 2021Towards a Unified Information-Theoretic Framework for Generalizationcited by 29
  9. 2021Fractal Structure and Generalization Properties of Stochastic Optimization Algorithmscited by 23
  10. 2021Robustness to Pruning Predicts Generalization in Deep Neural Networkscited by 10

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 3; 2023: 7; 2024: 3; 2025: 5; 2026: 4.

22 papers.

Sort:

  1. 2022Limitations of Information-Theoretic Generalization Bounds for Gradient Descent Methods in Stochastic Convex Optimizationcited by 18
  2. 2022Rate-Distortion Theoretic Bounds on Generalization Error for Distributed Learningcited by 14
  3. 2024Minimum Description Length and Generalization Guarantees for Representation Learningcited by 11
  4. 2023Data-dependent Generalization Bounds via Variable-Size Compressibilitycited by 9
  5. 2023Lessons from Generalization Error Analysis of Federated Learning: You May Communicate Less Often!cited by 8
  6. 2022f-divergences and their applications in lossy compression and bounding generalization errorcited by 7
  7. 2023Implicit Compressibility of Overparametrized Neural Networks Trained with Heavy-Tailed SGDcited by 5
  8. 2023Generalization Guarantees via Algorithm-dependent Rademacher Complexitycited by 4
  9. 2024Slicing Mutual Information Generalization Bounds for Neural Networkscited by 4
  10. 2023Information-Theoretic Generalization Bounds for Transductive Learning and its Applicationscited by 2
  11. 2025Generalization Guarantees for Representation Learning via Data-Dependent Gaussian Mixture Priorscited by 2
  12. 2025Non-vacuous Generalization Bounds for Deep Neural Networks without any modification to the trained modelscited by 2
10 more
  1. 2026Leveraging Flatness to Improve Information-Theoretic Generalization Bounds for SGDcited by 2
  2. 2023Generalization error bounds for iterative learning algorithms with bounded updatescited by 1
  3. 2023Elastic Information Bottleneckcited by 1
  4. 2025Heterogeneity Matters even More in Distributed Learning: Study from Generalization Perspectivecited by 1
  5. 2025Multiview Representation Learning via Distributed Joint Latent Space Structuringcited by 1
  6. 2025Generalization Bounds for Quantum Learning via R'enyi Divergencescited by 1
  7. 2024Minimal Communication-Cost Statistical Learningcited by 0
  8. 2026Supervised Learning as Lossy Compression: Characterizing Generalization and Sample Complexity via Finite Blocklength Analysiscited by 0
  9. 2026Tighter Information-Theoretic Generalization Bounds via a Novel Class of Change of Measure Inequalitiescited by 0
  10. 2026Information-Theoretic Analysis of Next-Token Prediction under Markovian Datacited by 0