# Rate-Distortion Theoretic Generalization Bounds for Stochastic Learning Algorithms

arXiv: https://arxiv.org/abs/2203.02474 · HTML: https://mlsanity.com/paper/2203.02474/

## Key facts

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

## Builds on (most cited first, 22 of 22)

- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data](https://mlsanity.com/paper/1703.11008/) (2017)
- [A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks](https://mlsanity.com/paper/1707.09564/) (2017)
- [Stronger generalization bounds for deep nets via a compression approach](https://mlsanity.com/paper/1802.05296/) (2018)
- [Information-theoretic analysis of generalization capability of learning algorithms](https://mlsanity.com/paper/1705.07809/) (2017)
- [Reasoning About Generalization via Conditional Mutual Information](https://mlsanity.com/paper/2001.09122/) (2020)
- [Information-Theoretic Generalization Bounds for SGLD via Data-Dependent Estimates](https://mlsanity.com/paper/1911.02151/) (2019)
- [Tightening Mutual Information Based Bounds on Generalization Error](https://mlsanity.com/paper/1901.04609/) (2019)
- [Sharpened Generalization Bounds based on Conditional Mutual Information and an Application to Noisy, Iterative Algorithms](https://mlsanity.com/paper/2004.12983/) (2020)
- [Intrinsic Dimension, Persistent Homology and Generalization in Neural Networks](https://mlsanity.com/paper/2111.13171/) (2021)
- [Hausdorff Dimension, Heavy Tails, and Generalization in Neural Networks](https://mlsanity.com/paper/2006.09313/) (2020)
- [Information-theoretic generalization bounds for black-box learning algorithms](https://mlsanity.com/paper/2110.01584/) (2021)
- [Generalization Error Bounds Via R'enyi-, f-Divergences and Maximal Leakage](https://mlsanity.com/paper/1912.01439/) (2019)
- [In Defense of Uniform Convergence: Generalization via derandomization with an application to interpolating predictors](https://mlsanity.com/paper/1912.04265/) (2019)
- [Heavy Tails in SGD and Compressibility of Overparametrized Neural Networks](https://mlsanity.com/paper/2106.03795/) (2021)
- [Data-Dependent Coresets for Compressing Neural Networks with Applications to Generalization Bounds](https://mlsanity.com/paper/1804.05345/) (2018)
- [Generalization Bounds via Information Density and Conditional Information Density](https://mlsanity.com/paper/2005.08044/) (2020)
- [Compression based bound for non-compressed network: unified generalization error analysis of large compressible deep neural network](https://mlsanity.com/paper/1909.11274/) (2019)
- [Generalization bounds via distillation](https://mlsanity.com/paper/2104.05641/) (2021)
- [Towards a Unified Information-Theoretic Framework for Generalization](https://mlsanity.com/paper/2111.05275/) (2021)
- [Fractal Structure and Generalization Properties of Stochastic Optimization Algorithms](https://mlsanity.com/paper/2106.04881/) (2021)
- [Robustness to Pruning Predicts Generalization in Deep Neural Networks](https://mlsanity.com/paper/2103.06002/) (2021)

## Built on by (most cited first, 22 of 22)

- [Limitations of Information-Theoretic Generalization Bounds for Gradient Descent Methods in Stochastic Convex Optimization](https://mlsanity.com/paper/2212.13556/) (2022)
- [Rate-Distortion Theoretic Bounds on Generalization Error for Distributed Learning](https://mlsanity.com/paper/2206.02604/) (2022)
- [Minimum Description Length and Generalization Guarantees for Representation Learning](https://mlsanity.com/paper/2402.03254/) (2024)
- [Data-dependent Generalization Bounds via Variable-Size Compressibility](https://mlsanity.com/paper/2303.05369/) (2023)
- [Lessons from Generalization Error Analysis of Federated Learning: You May Communicate Less Often!](https://mlsanity.com/paper/2306.05862/) (2023)
- [f-divergences and their applications in lossy compression and bounding generalization error](https://mlsanity.com/paper/2206.11042/) (2022)
- [Implicit Compressibility of Overparametrized Neural Networks Trained with Heavy-Tailed SGD](https://mlsanity.com/paper/2306.08125/) (2023)
- [Generalization Guarantees via Algorithm-dependent Rademacher Complexity](https://mlsanity.com/paper/2307.02501/) (2023)
- [Slicing Mutual Information Generalization Bounds for Neural Networks](https://mlsanity.com/paper/2406.04047/) (2024)
- [Information-Theoretic Generalization Bounds for Transductive Learning and its Applications](https://mlsanity.com/paper/2311.04561/) (2023)
- [Generalization Guarantees for Representation Learning via Data-Dependent Gaussian Mixture Priors](https://mlsanity.com/paper/2502.15540/) (2025)
- [Non-vacuous Generalization Bounds for Deep Neural Networks without any modification to the trained models](https://mlsanity.com/paper/2503.07325/) (2025)
- [Leveraging Flatness to Improve Information-Theoretic Generalization Bounds for SGD](https://mlsanity.com/paper/2601.01465/) (2026)
- [Generalization error bounds for iterative learning algorithms with bounded updates](https://mlsanity.com/paper/2309.05077/) (2023)
- [Elastic Information Bottleneck](https://mlsanity.com/paper/2311.03955/) (2023)
- [Heterogeneity Matters even More in Distributed Learning: Study from Generalization Perspective](https://mlsanity.com/paper/2503.01598/) (2025)
- [Multiview Representation Learning via Distributed Joint Latent Space Structuring](https://mlsanity.com/paper/2504.18455/) (2025)
- [Generalization Bounds for Quantum Learning via R'enyi Divergences](https://mlsanity.com/paper/2505.11025/) (2025)
- [Minimal Communication-Cost Statistical Learning](https://mlsanity.com/paper/2406.08193/) (2024)
- [Supervised Learning as Lossy Compression: Characterizing Generalization and Sample Complexity via Finite Blocklength Analysis](https://mlsanity.com/paper/2602.04107/) (2026)
- [Tighter Information-Theoretic Generalization Bounds via a Novel Class of Change of Measure Inequalities](https://mlsanity.com/paper/2602.07999/) (2026)
- [Information-Theoretic Analysis of Next-Token Prediction under Markovian Data](https://mlsanity.com/paper/2609.34731/) (2026)

## 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.